728x90 반응형 Algorithm25 순열(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. 이진 탐색 vs 이진 탐색 트리 근본적으로 같은 원리에 의한 탐색 구조 이진 탐색 배열에 저장된 데이터를 탐색 - 동적으로 크기가 변하는 데이터 집합 탐색에는 부적합 - 삽입과 삭제가 상당히 힘들다 시간 복잡도 O(logN) 처음에 입력된 갯수가 N 이라 하면, 첫 시행 후에 반이 버려지게 되서 1/2 * N, 두번째 시행 후에 또 반이 버려져서 1/2 * 1/2 * N, 세번째 시행 후에 또 그 반이 버려져서 1/2 * 1/2 * 1/2 * N, K번 시행후에는 (1/2)^K * N 이렇게 수행을 계속하다가 탐색이 끝나면 자료가 한개 남개 된다. 따라서 (1/2)^K * N ≒ 1 K = logN 이진 탐색 트리 연결 리스트 데이터에 대한 탐색 - 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조 - 삽입, 삭제가 빈번히 이.. 2019. 4. 30. 이전 1 2 3 4 다음 728x90 반응형
