[알고리즘] 5. Greedy

1. Greedy 알고리즘이란?

개념

- 현재 순간에 최적이라고 생각되는 선택을 반복하며 문제를 해결하는 방식

- 과거의 선택이나 미래 결과는 고려하지 않음

- 단순해 보이지만, 특정 문제에서는 매우 효율적이고 최적해를 보장함

 

구조

1. 선택 selection : 현재 가장 좋아 보이는 항목 선택
2. 유효성 확인 feasibility check: 지금까지 선택한 것들이 전체 해결 가능성 있는지 검사
3. 해결 여부 확인 solution check: 현재 선택 집합이 전체 문제의 해인지 확인

 

예제 - 동전 거스름돈 문제 (coin change problem)

: 금액 n을 최소 개수의 동전 {25, 10, 5, 1}로 표현하기 ex) 30 -> 25+5

 

- Brute-force 방식: 가능한 모든 조합 다 시도해보기, 매우느림 -> 계산량 많음

- Greedy 방식

coinGreedy(n) {
  if (n >= 25) → n-25 호출하고 a++;
  else if (n >= 10) → n-10 호출하고 b++;
  else if (n >= 5) → n-5 호출하고 c++;
  else → d = n;
}

-> 항상 가장 큰 동전부터 선택, 시간복잡도 O(n), BUT 항상 최적해는 아님.

 

- 반례: 동전 집합이 {1, 3, 4, 5}이고 금액이 7이면?

방법	결과	동전 수
Greedy	5 + 1 + 1	3개
Optimal	4 + 3	✅ 2개 (최적해)

 

 

2. Huffman Coding 허프만 부호화

: 문자 집합을 가장 적은 비트 수로 인코딩, 각 문자를 고유한 이진코드로 변환

고정길이 코드 vs 가변길이 코드

코드	문자당 비트 수	예시
고정 길이 (C1)	항상 동일	a:00, b:01, c:10
허프만 코드 (C3)	자주 등장하는 문자는 짧게	a:00, b:1110 등

ex. 문자열 ababcbbbc -> 고정코드 18bits , 허프만코드 13bits -> 허프만 코드가 효율적!

 

허프만 알고리즘

1. 각 문자의 빈도 기반으로 우선순위 큐 구성
2. 가장 낮은 빈도 2개를 뽑아 합친 노드 생성
3. 새로운 노드를 다시 큐에 삽입
4. 이 과정을 n-1번 반복 -> 이진트리 완성

- 결과: Prefix Code 생성

- 최종 인코딩은 트리 구조에서 왼쪽=0, 오른쪽=1 따라가며 부여

 

Knapsack Problem 배낭문제

- 문제정의

• 배낭용량: W
• 아이템: 각 무게 wi, 이익 pi
• 목표: 무게 제한 내에서 최대 이익 얻기

- 종류

• 0/1 Knapsack: 각 아이템은 한 번만 선택가능
• Fractional Knapsack: 일부만 선택 가능 (ex. 금가루)

- Greedy vs Dynamic Programming

• Greedy: 0/1은 실패, Fractional은 그리디로 항상 최적해
  • 0/1: 가장 무거운 것, 가장 이익 큰 것만 고르면 최적해가 안된다.
  • Fractional: 단위 무게당 이익이 큰 순서로 정렬 -> 가득 찰 때까지 넣고, 남는 공간엔 마지막 아이템 일부만 넣기
• Dynamic Programming: 0/1 Knapsack의 시간복잡도 O(nW)
  • P[i][w]: 아이템 i개까지 고려할 때 최대 이익 (무게 w까지)
  • 점화

if (wi ≤ w)
  P[i][w] = max(P[i-1][w], pi + P[i-1][w - wi])
else
  P[i][w] = P[i-1][w]