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. 만약 바꿨을 때 더 나은 해답이 나온다면, 탐욕적 선택이 잘못되었음을 의미한다.

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

     

    반응형

    댓글