그리디 알고리즘(탐욕적인 알고리즘)은 결정을 해야할 때마다 그 순간에 가장 좋다고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달하는 알고리즘입니다.
이 알고리즘의 맹점은, 그 당시에는 최적이지만 전부 모아서 최종적인 해답을 만들었을 때 그 해답이 최적이라는 보장은 없다는 것입니다. 그래서 이 알고리즘을 사용할 때에는 항상 최적의 해답을 주는 지를 반드시 검증해야합니다.
이 알고리즘의 설계 절차는 다음과 같습니다.
0. 선정 과정 : 현재 상태에서 가장 좋은 해답을 찾아 해답모음에 추가시킨다
1. 적정성점검 : 새로 얻은 해답 모음이 적절한지를 결정한다
2. 해답점검 : 새로 얻은 해답 모음이 최적의 해인지를 결정한다
이론적인 내용에 대해 보다 자세히 알고 싶다면 아래 Greedy Algorithm에 대한 영문 위키피디아를 첨부해 놓을테니 원문을 참조하시기 바랍니다!
en.wikipedia.org/wiki/Greedy_algorithm
Greedy algorithm - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search computer science heuristics that makes the locally optimal choice at each stage Greedy algorithms determine minimum number of coins to give while making change. These are the steps mos
en.wikipedia.org
이번 포스팅에서는 그리디 알고리즘의 예를 살펴보며 직접 구현해보도록 하겠습니다.
목차
0. 그리디 - 거스름돈
동전의 개수가 최소가 되도록 거스름 돈을 주는 문제입니다.
이 문제의 경우 중고등학교 수학시간에 간혹 나왔던 문제가 아닐까 싶습니다(ㅋㅋㅋㅋㅋㅋ)
이 알고리즘의 방식은, 거스름돈을 x라 하고 가치가 가장 높은 동전부터 x가 초과되지 않도록 계속 내줍니다.
이 과정을 가치가 높은 동전부터 내림 순으로 총액이 정확히 x가 될 때까지 반복합니다.
현재 우리나라 동전을 가지고 이 알고리즘을 구현하면 항상 동전의 개수는 최소가 됩니다. 그러므로 이 알고리즘은 최적입니다! (반드시 이런 검증 과정을 거쳐야합니다!!)
만약 12원짜리 동전을 새로 발행했다고 하면, 이 알고리즘은 최적이 되지 않습니다.
직접 예를 통해 살펴보시죠!
1. 그리디 - Prim 알고리즘
이 알고리즘을 배우기 전에, 최소비용신장트리라는 것에 대해서 알아봅시다.
신장트리는 비방향성 그래프 G에서 순환경로를 제거하면서 연결된 부분그래프가 되도록 이음선을 제거하면 신장트리가 됩니다. 즉 신장트리는 G 안에 있는 모든 정점을 다 포함하면서, 트리가 되는 연결된 부분그래프입니다. (순환이 되지 않습니다!!!)
t(G)는 연결된 그래프의 신장트리의 개수가 되고,
완전그래프는 모든 노드간에 에지가 존재하는 그래프를 뜻합니다.
노드가 n개인 완전그래프 Kn의 엣지 개수는 nC2이고, 트리는 n-1이고, Kn으로부터 생성할 수 있는 에지수가 n-1인 그래프의 개수는 (nC2)Cn-1 입니다.
보다 자세한 내용은 아래 사진을 참고하세요!
그렇다면 최소비용신장트리(minimum spanning tree)는 뭘까요?
바로 신장트리가 되는 G의 부분그래프중에서 가중치가 최소가 되는 부분그래프를 뜻합니다.
특히 순환경로가 없어야합니다. 만약 순환경로가 있다면 순환을 끊어주면 더 작은 비용의 신장트리가 되기 때문입니다.
이런 최소비용신장트리를 구할 때, 역시 brute-force 알고리즘을 사용할 수 있습니다. 예상하는 그대로, 정말 효율은 바닥입니다. n에 대해 최대 n^(n-2)번의 연산과정이 필요합니다.
이 문제는 다행히도 탐욕적인 알고리즘을 사용할 수 있습니다. 사이클만 생기지 않는다면 순간의 최적해가 전체 최적해와 일치하게 되는 것이죠.
이제 Prim의 알고리즘부터 살펴봅시다.
프림알고리즘은 가중치가 있는 연결된 무방향성 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 트리를 찾는 알고리즘입니다.
변의 개수가 E, 꼭지점의 개수가 V라면, Binary heap을 이용했을 때를 기준으로 O(ElogV)만큼의 시간복잡도를 가집니다. 또한 충분히 빽빽하면 피보나치힙을 이용하면 O(E+VlogV)까지 시간복잡도를 줄일 수 있습니다.
이 알고리즘은 아래의 순서대로 동작합니다.
0. 그래프에서 하나의 꼭짓점을 선택하여 트리를 만든다
1. 그래프의 모든 변이 들어 있는 집합을 만든다
2. 모든 꼭짓점이 트리에 포함되어 있지 않은 동안 1번 트리와 연결된 변 가운데 트리 속의 두 꼭짓점을 연결하지 않는 갖아 가중치가 작은 변을 트리에 추가한다
간단히 말해서, 내가 방문한 꼭짓점에서 연결할 수 있는 가장 최소한의 비용을 가진 경로를 선택하는 방식입니다.
방문한 꼭짓점을 담은 트리를 하나 만들고, 갈 수 있는 경로를 계속 찾으면서 경로를 새로고침 해나가는 것이죠.
아래 그림을 통해 더 자세히 살펴보시죠.
이제 알고리즘을 실제로 만들어봅시다.
프림알고리즘의 시간복잡도는 n-1번 반복되는 repeat 루프 안에 for문이 존재하므로 O(n^2)가 됩니다.
2. 그리디 - Kruskal 알고리즘
크루스칼 알고리즘은 가중치를 오름차순으로 정렬한 후에 가중치가 낮은 선부터 연결하는 알고리즘입니다.
대신 연결할 때 트리가 유지되어야하기 때문에 Cycle이 생긴다면 이음선을 추가하지 않습니다.
이해하는 것은 어렵지 않지만, 알고리즘을 분석할 때 신경을 써야 하는 부분이 있습니다. 정렬할 때 걸리는 시간을 꼭 확인해야합니다.
크루스칼 알고리즘의 특성상 에지들의 가중치를 오름차순으로 정렬하기 때문에 여기서 O(mlgm)만큼의 시간이 소요됩니다. 그리고 n개를 초기화하는데 드는시간, 반복문 안에서 수행하는 시간을 모두 고려했을 때 m≥n-1이기 때문에 정렬에 가장 오랜 시간이 걸리게 됩니다. 이 부분만 조심하면 분석은 크게 어렵지 않습니다.
다만 최악의 경우 모든 정점과 연결이 될 수 있어서 O(n^2)이 된다는 점을 기억해두면 좋습니다!
크루스칼과 프림의 알고리즘을 비교해보면, sparse한 그래프와 dense한 그래프에서 각각 장단점을 가지고 있는 것을 볼 수 있습니다. 또한 프림의 경우 위에서 언급했듯이 피보나치힙을 사용하면 시간복잡도를 더 줄일 수 있다는 점을 확인합시다!
3. 그리디 - Dijkstra 알고리즘
이 방면 최고존엄(..) 이라고 할 수 있는 다익스트라 알고리즘입니다.
흔히 단일출발점 최단경로문제라고도 불립니다. 가중치가 있는 방향성 그래프에서 한 정점에서 다른 모든 정점으로 가는 최단경로를 구하는 문제입니다.
이 알고리즘의 기본 로직은 시작 정점을 기준으로 정점들을 추가하면서 최단거리를 갱신하는 것입니다. (그렇기에 시작은 간선은 inf부터 시작합니다!)
먼저 출발지점에서 가장 비용이 낮은 경로를 선택합니다. 그리고 그 정점과 연결합니다. 그리고 정점을 집합에 추가합니다.
그 다음엔 새롭게 연결된 정점을 통해 생성된 경로와 기존 경로간의 비용을 비교하여 더 낮은 쪽을 선택합니다. 대신 이미 확인한 정점은 더 이상 확인하지 않습니다. 그리고 모든 정점을 방문했다면 종료합니다. 이것이 다익스트라 알고리즘의 전부입니다.
다익스트라 알고리즘 역시 힙으로 구현하는 것보다 피보나찌 힙으로 구현하면 시간복잡도에서의 추가적인 이득을 볼 수 있습니다.
4. 그리디 - Huffman 코드
허프만코드는 최적 이진 코드를 만듭니다.
최적 이진 코드를 알기 위해서는 Fixed-length binary code, Variable-length binary code, Optimal binary code, prefix code를 알아야합니다.
Fixed-length binary code는 코드의 길이가 고정된 코드입니다. ex) a=00, b=01, c=11
Variable-length binary code는 코드의 길이가 변하는 코드입니다. ex) a=10, b=0, c=11
여기서 문제점이 하나 발생하는데, 00과 0을 구분할 수 없다는 것입니다.
Optimal binary code는 주어진 파일에 있는 문자들을 이진 코드로 표현하는 데 필요한 비트의 개수가 최소가 되는 코드입니다. 이는 뒤에서 더 자세히 살펴보죠.
Prefix code는 한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수 없습니다. ex) a=10, b=0, c=11
이것의 장점은, 앞으로 읽을 비트를 확인하지 않아도 코드를 해석할 수 있다는 점입니다.
첫 글자로 0이 나오면 무조건 다음꺼 읽으면 되겠네? 하고 생각하면 된다는 것이죠.
이제 Huffman code에 대해서 알아봅시다.
Huffman 코드는 특정 파일에 대해 가장 최적의 Prefix code를 말합니다.
이 Huffman 코드를 구축하는 방법 역시 존재합니다.
첫 번째로 빈도수를 데이터로 갖는 n개의 노드를 생성하고,
두 번째로 빈도수의 합이 최소가 되는 노드를 merge시켜 이진트리로 구축하고,
마지막으로 모든 노드가 하나의 이진트리가 될 때까지 반복하는 것입니다.
우선순위 큐를 통해서 Huffman code를 구축해봅시다.
5. 그리디 - knapsack Problem
이번에는 가방에 가장 가치있는 것들을 넣는 경우의 수를 구하는 알고리즘입니다.
겉으로만 보면 이것도 참 쉬워보이지만, 실제로는 그렇지 않습니다.
물론 brute-force로 해결할 수 있지만 2^n개의 부분집합을 가지고 있습니다..
그래서 이 문제를 해결하기 위해서는 그리디를 써야하는데, 그리디도 특별한 그리디를 생각해야 하기에 꽤 어렵습니다.
가장 비싼 물건부터 채우는 경우 최적이 아니고, 가장 가벼운 물건부터 채워도 최적이 아닙니다. 모게당 가치가 가장 높은 물건부터 채우는 것도 최적이 아닙니다. 빈틈이 생기기 때문이죠. (운영체제시간에 best fit / worst fit 등 빈 공간 관리를 배우셨다면 한층 이해하기 쉬우실 겁니다.)
하지만 물건을 자를 수 있다면? 단위무게당 값어치가 큰 것부터 넣고, 더 이상 넣을 수 없으면 배낭에 남은 무게만큼 잘라서 넣으면 됩니다.
여기서 특정 항목까지 정해진 최고의 이익은 변하지 않기에 동적계획적으로도 접근이 가능합니다.
하지만 이렇게 동적계획방법을 사용할 때 생기는 단점이, 계산에 필요없는 공간을 사용하게 된다는 것입니다. 특정 값을 구할 때 전체 값이 필요하지는 않을 것입니다. 따라서 사용하는 메모리의 관리가 필요합니다.
그래서 등장한 것이, 필요한 부분만 계산하자는 것입니다. 현실은 필요 없는 부분을 최대한 줄여서(딱 P[n-1][W와 P[n-1][W-w_n] 두 항만 계산하면 됩니다. 시간을 단축시키는 것을 통해 n*n!에서 2^n시간까지 줄일 수 있습니다.
그리고 현재 이 알고리즘은 지수보다 더 나은 알고리즘으로 해결하지 못하고 있습니다. 또한 지수보다 더 줄일 수 없다고 증명하지도 못하고 있는 무시무시한 NP문제가 되겠습니다!
최근댓글