728x90 반응형 Algorithm26 Get Middle in ListNode(ListNode에서 중간 값 찾기) 연결 리스트의 중간 노드를 찾기 위해 두 개의 포인터(느린 포인터와 빠른 포인터)를 사용합니다. 초기화: slow 포인터는 리스트의 시작 노드인 head로, fast 포인터는 리스트의 두 번째 노드인 head.next로 초기화합니다.이동: slow 포인터는 한 번에 한 노드씩 앞으로 이동하고, fast 포인터는 한 번에 두 노드씩 앞으로 이동합니다.종료 조건: fast 포인터가 리스트의 끝에 도달하거나 끝을 넘어가면 루프가 종료됩니다. 이 시점에서 slow 포인터는 리스트의 중간에 위치하게 됩니다.private ListNode GetMiddle(ListNode head) { if (head == null) return head; ListNode slow = head, fast = head.ne.. 2024. 6. 28. 순열(Permutation)-c# 순열(Permutation)은 주어진 집합의 원소들을 나열하는 모든 경우의 수를 말합니다 using System; class Program { static void Main() { string[] set = { "A", "B", "C" }; Permute(set, 0, set.Length - 1); } static void Permute(string[] set, int start, int end) { if (start == end) { PrintArray(set); return; } for (int i = start; i 2023. 12. 17. 동전 교환(거스름돈) 알고리즘 최소 갯수로 동전 교환하는 방법 전체 금액보다 작은 동전중에서 가장 큰 동전부터 차례차례 채워 나간다. 현재의 동전만큼을 뺀 거스름돈에서 현재 동전하나를 추가하여 만드므로 그 전의 거스름돈에 1을 더하면 된다. dp[j] = min(dp[j],dp[j-coin[i]]+1); 이미 구해진 거스름돈이 더 적은 값을 가지고 있다면 현재의 값을 유지하면 된다. for i 2019. 5. 6. 최대 연속 부분수열의 합 연속된 원소를 더한 부분 수열의 최댓값을 구하는 문제 수의 합을 반복적으로 구한다. 이 때 합이 음수이면 그 다음 수부터 다시 시작한다. 합의 최댓값을 도출한다. -3 3 5 -3 -7 9 -2 10 -5 -2 -3 경우 음수이므로 반영안한다. 현재 합 : 0 합의 최댓값 : 0 3 경우 현재 합 : 3 합의 최댓값 : 3 5 경우 현재 합 : 8 합의 최댓값 : 8 -3 경우 현재 합 : 5 합의 최댓값 : 8 -7 경우 현재 합 : -2 -> 0 음수이므로 0으로 갱신 합의 최댓값 : 8 9 경우 현재 합 : 9 합의 최댓값 : 9 -2 경우 현재 합 : 7 합의 최댓값 : 9 10 경우 현재 합 : 17 합의 최댓값 : 17 -5 경우 현재 합 : 12 합의 최댓값 : 17 -2 경우 현재 합 : .. 2019. 5. 5. 최장 공통 부분 수열 최장 공통 부분 수열은 LCS라고 부른다. 주어진 여러 개의 수열 모두의 부분수열이 되는 수열들 중에 가장 긴 것을 찾는 문제다. 수도코드 lcs(m,n) for i 2019. 5. 5. 최장 증가 부분 수열 최장 증가 부분 수열(LIS) 동적 계획법으로 풀 수 있는 유명한 알고리즘 문제이다. 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분수열을 만들 수 있다. 이 때 만들어진 부분수열 중 오름차순으로 정렬된 가장 긴 수열을 최장 증가 부분 수열이라고 한다. O(n^2) 방법 for (int i = 0; i arr[j]) { if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; } } } } 매 순간마다 자기보다 작은 구간에 최댓값을 찾는 쿼리를 날려 최댓값 +1을 업데이트하는 방식으로 처리를 한다면, N번을 확인하.. 2019. 5. 5. BFS와 DFS 너비 우선 탐색(BFS , Breadth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 사용하는 경우 : 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선택 ex) A,B사이에 존재하는 경로를 찾는 경우, A에서 가까운 곳 부터 탐색 그래프 탐색의 경우, 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. -> 이를 검사하지 않을 경우, 무한루프에 빠질 위험이 있다. BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐를 사용한다. ->프림과 다익스트라 알고리즘과 유사하다. BFS(G,k) q.push(G.root) root.visit = true while !q.isEmpty() node r = q.fron.. 2019. 5. 2. 이전 1 2 3 4 다음 728x90 반응형
