Greedy Algorithms
그리디 알고리즘, 탐욕 알고리즘
- 지금 당장의 최선의 선택지만을 골라가며 해를 도출해나가는 방법을 채택한 알고리즘을 의미한다.
(당장, 눈앞의 이익만을 좇는다.)
- 그리디 알고리즘은 대체로 좋은 결과를 기대할 수 없지만,
특정 문제에서는 그리디 알고리즘이 최적해를 보장해주기도 한다.
(예를 들어, 매트로이드와 같은 특수 구조에서는 그리디 알고리즘이 최적해를 보장한다.)
- 그리디 알고리즘은 최적화 문제를 대상으로 적용할 수 있는데,
최적해를 찾을 수 있다면, 최적해를 찾는데 목표를 두고,
최적해를 주어진 시간에 찾아낼 수 없다면, 그런대로 괜찮은 해를 찾는데 목표를 둔다.
* Constructive Algorithm (구축형 알고리즘)
- 불완전한 상태에서 온전한 최적해로 나아가는 형태로 계산하는 알고리즘을 의미한다.
* Improvement Algorithm (개선형 알고리즘)
- 알고리즘의 초기부터 온전한 해로 시작하여, 최적해에 가까운 해가 발견되면, 수정해나가는 알고리즘을 의미한다.
Matroid Structure (매트로이드 공간 구조) (URL)
- Greedy Algorithm이 Optimal Solution을 가려낼 수 있는 경우인지를 판별할 수 있게 하는 수학적 공간이다.
- 단, Greedy한 방법을 적용할 수 있는 모든 경우를 판별해낼 수 있는 것은 아니라서,
어떤 문제의 공간이 매트로이드 구조를 이루면, Greedy Algorithm이 최적해를 도출해낼 수 있지만,
Greedy Algorithm이 최적해를 도출할 수 있는 모든 문제가 매트로이드 구조를 띄는 것은 아니다.
- 원래 Matrix에서 행들의 독립성을 일반화 및 추상화하면서 출현한 탓에 Matroid란 이름을 갖게 되었다.
Examples where Optimal Solution is not guaranteed with Greedy Algorithms
(그리디 알고리즘으로 최적해가 보장되지 않는 예시)
- 그리디 알고리즘은 대부분의 경우에서 최적해를 보장하지 못한다.
Path for Optimal Sum in Binary Tree Problem (이진 트리의 최적합 경로 문제)
- 각각의 노드가 Positive Weighted Node로 구성된 이진 트리에서,
루트에서 임의의 리프 노드까지의 경로들 중, 가중치의 합이 최대인 경로를 계산하는 문제이다.
- 이때, 가중치는 Parent에서 왼쪽, 오른쪽 분기 여부를 결정짓는 요인이 아니다.
(즉, 가중치와 노드의 Key는 다른 개념이라 간주한다.)
- 그러므로, Parent에 다다라서야 Child의 가중치 값을 확인할 수 있다.
(직관적으로, Greedy 알고리즘처럼 그때마다 최선책을 골라가는 방법으로는 최적해를 찾을 수 없음을 알 수 있다.)
- 즉, DFS와 같은 Backtracking 탐색을 통해 최적해를 계산해내야 하고,
이에 대한 수행 시간의 상한은 트리의 노드의 개수에 비례할 것이다.
Zero/One Knapsack Problem (0/1 배낭 채우기 문제) (URL)
- 부피가 \(M\)인 배낭과 이 배낭에 넣을 물건 \(n\)개가 있고,
이 물건 \(i\)의 부피는 \(W_i\)이며, 이 물건을 배낭에 넣을 경우 \(P_i\)만큼의 가치가 있다고 하자.
- 배낭 채우기 문제는 담을 물건들의 전체 부피 합이 \(M\)을 넘기지 않으면서,
가치의 합(=\(\sum P_i\))을 최대로 하는 경우를 계산하는 문제이다.
- 이때, 담을 물건을 분할할 수 없다.
("0/1"의 의미가 물건을 "안 담는다/담는다"의 의미이고, 잘라서 넣는 것은 허용되지 않는다.)
- 0/1 배낭 채우기 문제는 NP-Hard군에 속하는 난제이다.
※ 물건을 분할하여 담을 수 있게 완화한 문제를 Fractional Knapsack Problem이라 부르며,
흥미롭게도, 이 문제는 Greedy Algorithm이 최적해를 보장한다.
Coin Exchange Problem (동전 교환 문제) (URL)
- 어떤 금액을 가장 적은 개수의 동전을 사용하여 만들어내야 한다고 할 때,
얼마짜리의 동전을 몇 개로 구성해야 하는지를 계산하는 문제이다.
- 동전의 액면가가 500원, 100원, 50원, 10원처럼,
동전의 액면가가 커지면서 바로 아래 단위의 액면가의 배수로 구성되는 경우,
Greedy한 방법으로 최적해를 도출해낼 수 있다.
ex) 3,250원은 500원 6개, 100원 2개, 50원 1개로 구성된다.
- 동전의 액면가가 500원, 400원, 100원, 75원, 50원처럼,
동전의 액면가가 증가해도 바로 아래 단위의 액면가와 배수 관계를 보이지 않는 경우,
Greedy한 방법으로는 최적해를 계산해낼 수 없고,
이는 Optimal Substructure를 보이고 있어, Dynamic Programming (URL) 기법을 적용하여 계산해내야 한다.
ex) 1,300원을 Greedy한 방법으로 구성할 경우, 500원 2개, 100원 3개로 구성할 것이지만,
이 문제의 답은 500원 1개, 400원 2개이다.
Examples where Optimal Solution is guaranteed with Greedy Algorithms
(그리디 알고리즘으로 최적해가 보장되는 예시)
- 드물지만, 그리디 알고리즘이 최적해를 도출해낼 수 있는 경우가 있다.
Minimum Spanning Tree (최소 신장 트리)
* Prim's Algorithm (프림 알고리즘) (URL)
- Graph상에서 Minimum Spanning Tree(최소 신장 트리)를 구성하는 방법 중 하나이다.
- 시작 정점으로부터 Weight값이 가장 작은 간선과 연결된 정점을 선택해가며 신장 트리를 구성한다.
- 이때, 선택한 정점으로 인해 Cycle이 생긴다면, 해당 정점은 집합에 포함시키지 않는다.
* Kruskal's Algorithm (크루스칼 알고리즘) (URL)
- Graph상에서 Minimum Spanning Tree(최소 신장 트리)를 구성하는 방법 중 하나이다.
- Weight값이 가장 작은 간선(=Light Edge; 경량 간선)들을 집합에 포함시켜 가면서 신장 트리를 구성한다.
- 이때, 선택한 간선으로 인해 Cycle이 생긴다면, 해당 간선은 집합에 포함시키지 않는다.
- \(n\)개의 정점으로 최소 신장 트리를 구성한다면,
Kruskal's 알고리즘에서는 \(n-1\)개의 간선을 선택할 때까지 연산을 진행해야 한다.
- \(n\)개의 정점들을 모두 노드가 하나인 개별적인 트리로 본다면,
Kruskal's 알고리즘에서는 \(n\)개의 트리로 구성된 Forest에서 두 트리를 하나로 합쳐가며
하나의 트리로 만들어나가는 과정을 수행한다.
Dijkstra's Shortest Path Algorithm (다익스트라 최단 경로 알고리즘) (URL)
- 0 이상의 Weight만을 허용하는 Weighted Graph상에서 Shortest Path를 찾아내는 알고리즘이다.
(가중치가 음수인 경우는 Bellman-Ford Algorithm (URL)으로 해결할 수 있다.)
- 다익스트라 알고리즘은 시작 정점에서 다른 모든 정점까지의 간선들을 Greedy선택하며 계산해나간다.
- Prim's Algorithm (URL)과 유사한 알고리즘 구조를 갖고 있다.
Fractional Knapsack Problem (분할 가능한 배낭 채우기 문제) (URL)
- 부피가 \(M\)인 배낭과 이 배낭에 넣을 물건 \(n\)개가 있고,
이 물건 \(i\)의 부피는 \(W_i\)이며, 이 물건을 배낭에 넣을 경우 \(P_i\)만큼의 가치가 있다고 하자.
- 배낭 채우기 문제는 담을 물건들의 전체 부피 합이 \(M\)을 넘기지 않으면서,
가치의 합(=\(\sum P_i\))을 최대로 하는 경우를 계산하는 문제이다.
- 이때, 배낭에 담을 물건을 분할할 수 있기 때문에,
단위 부피당 가치가 가장 큰 물건을 순서대로 담으며, 어떤 물건을 넣으려는 순간 배낭의 \(M\)을 초과하게 될 경우,
남은 용량에 딱 들어갈 만큼만 물건을 잘라서 담는다.
(당장 눈앞의 이득만을 취하는 점에서 "Greedy하다" 할 수 있다.)
※ 물건을 분할할 수 없고, 배낭에 물건을 담을 수 있다/없다의 선택지만 있는 문제를
0/1 Knapsack Problem이라 부르는데, 흥미롭게도 이 문제는 Greedy Algorithm이 최적해를 보장하지 못한다.
Meeting Room Scheduling Problem (회의실 배정 문제) (URL)
- 하나의 회의실을 여러 팀이 사용하고자 할 때,
회의들이 서로 겹치지 않게 하면서 최대한 많은 회의를 수용할 수 있도록 스케줄링하는 문제이다.
- 보통, 구현의 편의를 위해 한 팀의 회의 종료 시간과 다른 팀의 회의 시작 시간은 겹칠 수 있다고 가정한다.
(즉, 11시에 회의가 끝나고 곧바로 11시에 다른 팀이 회의를 시작하는 것이 가능하다.)
- \(n\)개의 회의가 요청된다 하고, 각각의 팀은 (회의 시작 시간, 회의 종료 시간) Pair를 넘겨준다.
- Greedy 알고리즘에서는 요청된 회의 시간들을 회의 종료 시간을 기준으로 오름차순으로 정렬한 다음,
종료 시간이 빠른 회의에 회의실을 배정한다.
(이때, 선택한 회의가 기존에 배정된 회의와 겹친다면, 배정을 포기하고 넘어간다.)
- 종료 시간이 빠른 회의를 선택하며 나간다는 점에서 "Greedy하다"고 표현할 수 있다.
(직관과 달리, 회의 시간이 짧은 회의들을 선택해나가는 것이 아니다.)
Huffman Coding Algorithm (허프만 암호화 알고리즘) (URL)
A* Algorithm (A* 알고리즘) (URL)
- 그래프의 시작 정점에서 도착 정점에 이르는 최단 경로를 계산하는 알고리즘이자,
상태 공간 트리의 탐색에도 사용되는 알고리즘이다.
- A* 알고리즘에서는
Best-First Search(최적 우선 탐색) 방법과, 도착 정점까지 경로의 추정치를 사용하여 다음 정점을 선택한다.
(장래의 탐색 정보를 활용하기 때문에, Dijkstra's 알고리즘과 같은 단순한 탐색 알고리즘에 비해 훨씬 효율적이다.)
- Dijkstra's 알고리즘에서는 모든 정점에 대해 최단 거리를 구하는 반면,
A* 알고리즘에서는 특정 도착 정점에 대한 최단 거리를 비교적 빠르게 구할 수 있다.
Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
