16. 탐욕적 알고리즘 (Greedy Algorithms) Codility Lesson 한국어 정리본 (JavaScript ver.)
탐욕적 알고리즘(Greedy Algorithm)이란?
탐욕적 알고리즘은 각 단계에서 가장 최선의 선택을 하는 방식으로 최적해를 찾는 방법 이다. 전체 최적해를 고려하지 않고, 매 순간 최적의 선택을 하기 때문에 구현이 간단하지만, 항상 최적해를 보장하는 것은 아니다.
탐욕적 알고리즘이 적용될 수 있는 대표적인 문제들:
- 동전 거스름돈 문제 (Coin Change Problem)
- 회의실 배정 문제 (Activity Selection Problem)
- 배낭 문제 (Knapsack Problem)
- 작업 스케줄링 문제 (Activity Selection)
- 최소 신장 트리 (MST, Minimum Spanning Tree)
- 허프만 코딩 (Huffman Coding)
탐욕 알고리즘의 특징
- 빠른 실행 시간: O(n log n) 또는 O(n)로 해결 가능
- 국소적 최적해 기반: 현재 상태에서 가장 좋은 선택을 한다.
- 최적해를 항상 보장하지 않음: 동전 거스름돈 문제처럼 일부 경우에는 최적해를 구할 수 없다.
4. 탐욕적 알고리즘의 한계
탐욕적 알고리즘은 매 순간 최적의 선택을 하지만, 항상 전체 최적해를 보장하는 것은 아니다. 따라서 다음과 같은 경우에는 사용하기 어렵다:
- 최적 부분 구조(Otimal Substructure) 가 없는 경우 (예: 배낭 문제, 일부 동전 거스름돈 문제)
- 결정해야 할 요소들이 서로 영향을 미치는 경우
이러한 문제에서는 동적 프로그래밍(DP)이나 백트래킹(Backtracking) 같은 다른 방법이 필요할 수 있다.
1. O(n) 시간 복잡도의 거스름돈 문제 해결
거스름돈 문제는 주어진 동전들로 특정 금액을 최소 개수의 동전으로 만드는 문제 이다. 탐욕적 알고리즘은 가장 큰 동전부터 선택하는 방식으로 해결할 수 있다.
JavaScript 코드:
function coinChange(coins, amount) {
coins.sort((a, b) => b - a); // 내림차순 정렬
let count = 0;
for (let coin of coins) {
while (amount >= coin) {
amount -= coin;
count++;
}
}
return amount === 0 ? count : -1;
}
시간 복잡도: O(n) (동전 개수만큼 반복)
주의: 이 방법은 항상 최적해를 보장하지 않는다. 예를 들어, 동전이 [1, 3, 4]이고 amount = 6일 때, 탐욕적 접근법은 [4, 1, 1]을 선택하지만, 최적해는 [3, 3]이다.
2. O(n log n) 시간 복잡도의 회의실 배정 문제
회의실 배정 문제는 가능한 한 많은 회의를 수용하기 위해, 회의가 겹치지 않도록 배정하는 문제 이다. 종료 시간이 가장 빠른 회의부터 선택하면 최적해를 보장할 수 있다.
JavaScript 코드:
function maxMeetings(start, end) {
let n = start.length;
let meetings = [];
for (let i = 0; i < n; i++) {
meetings.push([start[i], end[i]]);
}
meetings.sort((a, b) => a[1] - b[1]); // 종료 시간 기준 정렬
let count = 0, lastEnd = 0;
for (let [s, e] of meetings) {
if (s >= lastEnd) {
count++;
lastEnd = e;
}
}
return count;
}
시간 복잡도: O(n log n) (정렬 후 선형 탐색)
3. O(E log V) 시간 복잡도의 다익스트라 알고리즘
다익스트라 알고리즘(Dijkstra’s Algorithm)은 가중치가 있는 그래프에서 출발점으로부터 모든 정점까지의 최단 경로를 찾는 알고리즘 이다. 탐욕적 방법을 사용하여 매 단계에서 최단 거리를 선택한다.
JavaScript 코드:
class PriorityQueue {
constructor() {
this.queue = [];
}
enqueue(value, priority) {
this.queue.push({ value, priority });
this.queue.sort((a, b) => a.priority - b.priority);
}
dequeue() {
return this.queue.shift().value;
}
isEmpty() {
return this.queue.length === 0;
}
}
function dijkstra(graph, start) {
let distances = {};
let pq = new PriorityQueue();
for (let node in graph) {
distances[node] = Infinity;
}
distances[start] = 0;
pq.enqueue(start, 0);
while (!pq.isEmpty()) {
let current = pq.dequeue();
for (let neighbor in graph[current]) {
let newDist = distances[current] + graph[current][neighbor];
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
pq.enqueue(neighbor, newDist);
}
}
}
return distances;
}
시간 복잡도: O(E log V) (우선순위 큐를 이용한 구현)
4. 카누 문제 (Canoeist Problem)
문제
무게가 다른 n명의 카누 선수가 있고, 각 카누에는 최대 두 명까지 탈 수 있다. 모든 선수를 최소한의 카누에 배치하는 것이 목표이다.
접근 방법
- 가장 무거운 선수(heavy)를 찾고, 함께 탈 수 있는 가장 무거운 가벼운 선수(light)를 찾는다.
- 무거운 선수와 가벼운 선수를 함께 태운다.
- 위 과정이 불가능하면 무거운 선수만 따로 태운다.
JavaScript 코드 (탐욕 알고리즘)
function greedyCanoeist(weights, maxWeight) {
weights.sort((a, b) => a - b); // 무게 기준 정렬
let canoes = 0;
let i = 0, j = weights.length - 1;
while (i <= j) {
if (weights[i] + weights[j] <= maxWeight) {
i++; // 가벼운 사람과 함께 태운다.
} j--; // 무거운 사람은 무조건 태움
canoes++;
}
return canoes;
}시간 복잡도: O(n log n) (정렬) + O(n) (탐색) = O(n log n)
5. 탐욕 알고리즘의 증명 (Greedy Algorithm Proof)
탐욕 알고리즘이 항상 최적해를 보장하려면, 선택한 결정이 전체 문제에서도 최적해를 보장해야 한다. 이를 수학적 귀납법으로 증명할 수 있다.
- 첫 번째 선택이 최적해의 일부라면, 나머지 문제도 최적해를 포함할 수 있어야 한다.
- 기존의 최적해에서 첫 번째 선택을 다른 값으로 바꾸어도 동일한 성능을 유지할 수 있어야 한다.
- 만약 바꿨을 때 더 나은 해답이 나온다면, 탐욕적 선택이 잘못되었음을 의미한다.
위 증명이 성립하면 탐욕 알고리즘을 사용해도 최적해를 보장할 수 있다.