알고리즘 이론32 다이나믹 프로그래밍(Dynamic Programming) 다이나믹 프로그래밍은 동적계획법이라고도 불리며 짧게 DP라고 많이 사용합니다. DP의 중점은 "작은 문제를 해결하고 이를 이용해 큰 문제를 해결하자 / 큰 문제를 작은 문제로 쪼개서 해결하자."입니다. DP를 배우지는 않으셨더라도 피보나치 수를 재귀로 구하는 방법은 한번쯤 들어보셨을 거라 생각합니다. 이를 DP를 사용하는 방법으로 한 번 바꿔보겠습니다. int fibo(int n){ if(n==1 || n==0) return n; return fibo(n-1) + fibo(n-2); } 일단 기존 방법의 재귀 소스코드는 위와 같습니다. 4번째 피보나치 수를 구하려면 위와 같이 함수를 호출하게 되는데 2번째 피보나치 수를 구하는 함수를 중복해서 호출하게 됩니다. 2번째 피보나치 수는 상황에 따라서 변하는 .. 2020. 2. 22. KMP 알고리즘 만든 사람이 Knuth, Morris, Pratt 여서 Knuth–Morris–Pratt(KMP) 알고리즘이라 합니다. 문자열 알고리즘 중 하나로 문자열 에서 다른 문자열을 검색하는 알고리즘입니다. 단순하게 문자열(S) "ABCABDABCABC" 에서 문자열(P) "ABCABC"를 검색해봅시다. S, P 모두 가장 앞에서부터 같은지 비교합니다. (1) ~ (5) 는 문자가 같기 때문에 다음 문자를 비교합니다. (6) D, C는 다르기 때문에 문자열 P를 찾을 수 없습니다. 이제 S 문자열의 인덱스 1부터 다시 비교합니다. (1) B, A는 다르기 때문에 문자열 P를 찾을 수 없습니다. 문자열 P를 찾을 때까지 이를 반복합니다. 문자열 S 인덱스 6부터 시작하는 부분문자열에서 문자열 P를 찾을 수 있었습니.. 2020. 2. 9. 크루스칼 알고리즘(Kruskal’s algorithm) 신장 트리(Spanning Tree)란, 연결 그래프의 부분 그래프이며 모든 정점과 간선의 부분 집합으로 구성되는 트리입니다. 이 때, 모든 정점에는 하나 이상의 간선에 연결되어 있어야 합니다. 최소 신장 트리(Minimum Spanning Tree. MST)는 만들 수 있는 신장 트리 중에서 간선 비용의 합이 최소인 신장 트리를 말합니다. MST의 간선 개수는 정점의 수 - 1개입니다. 간선들의 비용 합이 최소인 경우는 여러 개 나올 수 있으므로 하나 이상 존재합니다. 이러한 MST를 만드는 대표적인 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 선택하여 확장하는 방법이고, 크루스칼 알고리즘은 간선을 선택하여 확장하는 방법입니다. 이번 포스팅에서는 크루스칼(Kruska.. 2020. 2. 6. 프림 알고리즘(Prim's algorithm) 신장 트리(Spanning Tree)란, 연결 그래프의 부분 그래프이며 모든 정점과 간선의 부분 집합으로 구성되는 트리입니다. 이 때, 모든 정점에는 하나 이상의 간선에 연결되어 있어야 합니다. 최소 신장 트리(Minimum Spanning Tree. MST)는 만들 수 있는 신장 트리 중에서 간선 비용의 합이 최소인 신장 트리를 말합니다. MST의 간선 개수는 정점의 수 - 1개입니다. 간선들의 비용 합이 최소인 경우는 여러 개 나올 수 있으므로 하나 이상 존재합니다. 이런 MST를 만드는 대표적인 방법으로는 프림 알고리즘과 크루스칼 알고리즘이 있습니다. 프림 알고리즘은 정점을 성택하여 확장하는 방법이고, 크루스칼 알고리즘은 간선을 선택하여 확장하는 방법입니다. 이번 포스팅에서는 프림(Prim) 알고리.. 2020. 2. 6. 세그먼트 트리(Segment Tree) 세그먼트 트리는 구간의 값을 저장하는 트리입니다. 1~N인 수열이 있을 때, "인덱스가 a~b인 수들의 합을 구하고 싶다." 혹은, "a~b번째 수들 중 최소 값이나 최대값을 구하고 싶다." 같은 경우 사용합니다. 세그먼트 트리는 이진 트리 모습을 가지며 자식 노드는 부모 노드의 범위를 반 씩 가지고 있습니다. 즉, 부모 노드가 1~5까지의 구간합을 가지고 있다면 자식 노드의 왼쪽 자식은 1~3의 구간 합을 가지고 오른쪽 자식은 4~5까지의 구간 합으로 나눠가집니다. 수열의 크기(N)가 5인 수열 A = {1, 2, 3, 4, 5}의 구간 합을 구하고자 할 때 사용하는 세그먼트 트리를 생성해 봅시다. 인덱스(i)는 접근이 쉽게 0이 아닌 1부터 시작하였습니다. 처음 상태의 세그먼트 트리는 다음과 같습니다.. 2020. 2. 2. 트리 순회(전위 순회, 중위 순회, 후위 순회) 트리를 배우면 같이 배우게 되는 개념 중 하나죠. 트리 순회에 대해 알아보겠습니다. 트리 순회에는 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder) 가 있습니다. 텍스트 추가 [그림 1]은 예시로 그린 트리 입니다. 전위 순회는 [루트 - 왼쪽 자식 - 오른쪽 자식] 순으로 순회합니다. 중위 순회는 [왼쪽 자식 - 루트 - 오른쪽 자식] 순으로 순회합니다. 후위 순회는 [왼쪽 자식 - 오른쪽 자식 - 루트] 순으로 순회합니다. 이것만 안다면 차근차근 해나가면 됩니다. 일단 전위 순회입니다. 루트 - 왼쪽 - 오른쪽 순으로 순회한다면 결과는 CBAEDFG 가 됩니다. 개인적으로 제일 쉽다고 생각하는 순회방법입니다. 만약 잘 이해가 되지 않는다면 [그림 3]처럼 모든 .. 2019. 10. 4. 이전 1 2 3 4 5 6 다음
