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)

탐욕 알고리즘이 항상 최적해를 보장하려면, 선택한 결정이 전체 문제에서도 최적해를 보장해야 한다. 이를 수학적 귀납법으로 증명할 수 있다.

1. 첫 번째 선택이 최적해의 일부라면, 나머지 문제도 최적해를 포함할 수 있어야 한다.
2. 기존의 최적해에서 첫 번째 선택을 다른 값으로 바꾸어도 동일한 성능을 유지할 수 있어야 한다.
3. 만약 바꿨을 때 더 나은 해답이 나온다면, 탐욕적 선택이 잘못되었음을 의미한다.

위 증명이 성립하면 탐욕 알고리즘을 사용해도 최적해를 보장할 수 있다.