학부 수업 "알고리즘설계와분석"에서 배운 내용을 정리합니다.

Greedy Algorithm의 기본 개념과 Interval Scheduling, Huffman Coding 등 대표적인 문제를 학습해보자.

1️⃣ Greedy Algorithm 기본 개념

Greedy Algorithm은 매 단계에서 지역적으로 최선의 선택(local optimum) 을 하는 알고리즘이다.

핵심 아이디어

전체 문제를 한꺼번에 고려하지 않고, 현재 순간의 최선만 고른다. 이러한 지역적 선택이 전역 최적해(global optimum)를 보장하지는 않지만, 특정 문제에서는 최적해를 찾을 수 있으며 계산이 매우 효율적이다.

특징

2️⃣ Interval Scheduling Problem

문제 정의

n개의 활동 A₁, A₂, ..., Aₙ이 주어지고, 각 활동은 시작시간 sᵢ와 종료시간 fᵢ를 가진다. 활동들이 시간적으로 겹치지 않게 하면서 선택 가능한 최대 활동 개수를 찾는 문제다.

💡 조건

어떤 두 활동도 시간적으로 겹치면 안 된다. 즉, [sᵢ, fᵢ) ∩ [sⱼ, fⱼ) = ∅

🔥 Brute-force 접근

모든 가능한 활동 조합을 고려하면 경우의 수가 2ⁿ 또는 n! 수준으로 폭발한다. 시간 복잡도가 지수적(exponential)이므로 비효율적이다.

Greedy 전략 탐색

2-1 가장 빨리 시작하는 활동 선택

전략: 가장 일찍 시작하는 활동을 선택한다.

결과: ❌ 비최적. 가장 일찍 시작하는 활동이 다른 많은 활동들과 겹쳐서 최대 개수를 선택하지 못할 수 있다.

2-2 가장 짧은 활동 선택

전략: 가장 짧은 활동을 선택한다.

결과: ❌ 비최적. 짧지만 중간에 위치해서 다른 활동들을 막을 수 있다.

2-3 충돌이 가장 적은 활동 선택

전략: 다른 활동과 겹치는 횟수가 가장 적은 활동을 선택한다.

결과: ❌ 비최적. 각 활동마다 나머지 n-1개 활동과 비교해야 하므로 O(n²) 계산이 필요하고, 최적 해를 보장하지도 않는다.

2-4 가장 빨리 끝나는 활동 선택 (Earliest Finish Time)

전략: 가장 일찍 끝나는 활동부터 차례로 선택한다.

결과: ✅ 최적. 가장 빨리 끝나는 활동을 선택하면 남은 시간 구간이 가장 넓게 남아 이후 활동을 가장 많이 배치할 수 있다.

🔥 Stay-Ahead Argument

우리가 선택한 첫 번째 활동은 모든 다른 해의 첫 활동보다 일찍 끝난다. 따라서 다음 활동을 고를 때 항상 더 많은 후보를 가질 수 있으며, 이 성질이 계속 유지되므로 최종 해는 항상 최적이다.

최적 알고리즘

알고리즘 절차

1. 모든 활동을 종료시간 기준 오름차순으로 정렬한다.
2. 첫 번째 활동을 선택한다.
3. 이후 선택된 활동과 겹치지 않는 (즉, start_time ≥ last_finish_time) 활동 중 가장 빨리 끝나는 것을 고른다.
4. 남은 활동이 없을 때까지 반복한다.

의사코드

def GreedyIntervalScheduling(activities):
    # 활동들을 종료 시간 기준으로 정렬
    activities.sort(key=lambda a: a.finish)
    R = []
    last_finish = 0

    for a in activities:
        if a.start >= last_finish:
            R.append(a)
            last_finish = a.finish

    return R

시간 복잡도

Greedy임에도 불구하고 이 문제에서는 항상 최적해를 보장한다.

3️⃣ Huffman Coding

문제 배경

파일을 비트로 표현할 때 필요한 비트 수를 최소화하는 것이 목표다. 문자가 4개라면 각 문자를 log₂(4) = 2비트로 표현할 수 있다.

💡 고정 길이 인코딩의 한계

예: A = 00, B = 01, C = 10, D = 11

모든 문자를 2비트로 표현하지만, 실제 파일에서 문자의 등장 빈도는 다르다. 자주 등장하는 문자를 짧은 비트로, 드물게 등장하는 문자를 긴 비트로 표현하면 더 효율적이다.

가변 길이 인코딩의 문제점

만약 A = 0, B = 01, C = 10, D = 11로 설정하면 겉보기엔 압축이 성공한 것처럼 보이지만 디코딩이 불가능하다.

예를 들어 01을 받았을 때, 첫 0이 A일 수도 있고 전체 01이 B일 수도 있다. 이런 코드는 모호하며(ambiguous) uniquely decodable하지 않다.

Prefix-Free Code

Prefix-free code는 어떤 코드워드도 다른 코드워드의 접두사가 되지 않는 코드다.

예시:

A = 0
B = 100
C = 101
D = 11

여기서 0, 100, 101, 11은 서로 접두사 관계가 없으므로 유일하게 해독 가능하다.

🔥 Binary Tree 표현

Prefix-free code는 이진 트리로 나타낼 수 있다.

• 왼쪽 가지 = 0, 오른쪽 가지 = 1
• 모든 문자는 리프(leaf)에 위치
• 리프까지 내려가면 해당 문자를 출력하고 다시 루트로 돌아감

예를 들어 비트열 010011101...을 해독하면:

• 0 → A
• 100 → B
• 11 → D
• 101 → C

Huffman Tree 구성

알고리즘 원리

빈도가 낮은 두 문자를 합쳐서 새 노드로 만든다. 그 합친 노드를 다시 힙에 넣고 반복한다.

알고리즘 절차

1. 문자들과 그 빈도를 최소 힙(min heap) 에 넣는다.
2. 가장 작은 두 빈도 x, y를 꺼내 새 노드 z를 생성한다. f(z) = f(x) + f(y)
3. 새 z를 힙에 다시 삽입한다.
4. 힙에 하나만 남을 때까지 반복한다.

남은 트리가 바로 Huffman Tree다.

시간 복잡도

• make-heap: O(n)
• extract-min × 2(n-1)회 + insert: O(n log n)

전체 O(n log n)

Full Binary Tree 구조

Huffman Tree는 반드시 다음을 만족한다:

• 모든 내부 노드는 자식 2개를 가진다.
• 리프 노드는 문자 1개를 가진다.
• 전체 노드 수 = 2n - 1 (리프 n개일 때)

🔥 코드 생성 방식

루트에서 리프까지의 경로가 그 문자의 코드워드가 된다. 왼쪽 간선은 0, 오른쪽 간선은 1이다.

최적성 증명

가장 빈도 낮은 두 문자를 먼저 결합하는 것이 항상 최적이다. 두 최소빈도 f₁, f₂가 트리의 가장 깊은 곳에 배치되어야 최적이며, 만약 더 큰 빈도의 문자가 더 깊게 들어가면 f × depth 합이 커져 비효율적이다.

따라서 Greedy하게 최소 2개씩 결합하는 Huffman 알고리즘이 전역적으로 최적이다.

Huffman Tree 전송

문자열을 인코딩해서 전송할 때, 수신자가 디코딩하려면 동일한 Huffman Tree를 알아야 한다. 따라서 전송해야 할 정보는 두 가지다.

트리 구조 전송

Full binary tree이므로 preorder 순회하면서 내부 노드는 0, 리프 노드는 1로 표시하면 구조 복원이 가능하다.

트리의 노드 수 = 2n - 1이므로 구조 전송 비용은 2n - 1 비트다.

리프 문자 목록 전송

리프 수 = n, 각 문자를 표현하는 데 log₂ n 비트가 필요하므로 총 n log n 비트가 필요하다.

🔥 전체 Huffman Tree 전송 비용

(2n - 1) + n log n 비트

ASCII 환경에서의 효율성

문자 256개가 있고 최대 빈도와 최소 빈도의 차이가 2배 미만이라면, 빈도 차이가 너무 작아 깊이 차이가 거의 없다. Huffman Tree가 사실상 완전 이진 트리처럼 되어 각 문자 코드 길이가 약 8비트가 되므로, Huffman Coding이 고정 8비트 ASCII보다 전혀 이득이 없다.

4️⃣ Greedy Algorithm의 한계

0-1 Knapsack Problem

문제: 배낭의 용량 W가 주어지고, 각 물건은 무게 wᵢ와 가치 vᵢ를 가진다. 가치를 최대화하면서 무게 합이 W 이하가 되도록 물건을 선택해야 한다.

Greedy 전략: 가치/무게 비율(vᵢ / wᵢ)이 가장 큰 순서로 담는다.

결과: ❌ 0-1 버전에서는 부분적으로 담을 수 없기 때문에 Greedy가 실패한다. Dynamic Programming으로 풀어야 한다.

💡 Fractional Knapsack

물건을 부분적으로 담을 수 있는 Fractional Knapsack에서는 Greedy가 최적해를 찾는다. 비율순 정렬 후 담으면 O(n log n)에 해결 가능하다.

정리