Greedy Algorithm, 탐욕 알고리즘

• 미래를 내다보지 않고, 당장 눈 앞에 보이는 최적의 선택을 하는 방식
• 간단하고 빠르지만, 최적의 답이 보장되지 않음

Greedy 알고리즘이 최적의 답을 보장하는 경우

• 최적 부분 구조 (Optimal Structure)
• 탐욕적 선택 속성 (Greedy Choice Property)
  • 각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최선의 선택
• 귀류법 (대우 명제 증명)
  • Greedy의 답이 해가 아니라고 가정 → 모순 발생
  • $T$ 시간 내에 최대한 많은 일을 하는 문제.
  • Greedy로 나온 $a_1, a_2, a_3$이 해가 아니고, 다른 $b_1, b_2, b_3, b_4$가 해라고 가정
  • $a_1 + a_2+ a_3 \leq b_1 + b_2+b_3$ 이다. Why?
  • Greedy 속성으로 최소의 시간으로만 해를 뽑았기에
  • 그렇다면, $b_1+ b_2+ b_3+ b_4\leq T$ 인가?
  • $a_1 + a_2+ a_3 + a_4 > T$ , $a_4\leq b_4$이다.
  • $b_1+ b_2+ b_3+ b_4\leq T$ =⇒ 모순 발생
  • 그러므로 $a_1, a_2, a_3$가 해다.

회의실 배정 문제 (Activity Selection Problem)

회의실이 하나 뿐인데, 이 회의실을 쓰고 싶은 팀은 많다. 회의가 서로 겹치지 않고 최대한 많은 회의를 배정해야한다.

• 기준

  1. 수업시간이 가장 짧은 회의부터 선택

     

  2. 가장 적게 겹치는 회의부터 선택

  3. 가장 빨리 시작하는 회의부터 선택

     

  4. 가장 빨리 끝나는 회의부터 선택

     ⇒ 끝나는 시간을 기준으로 오름차순 정렬 → $O(nlogn)$

     끝나는 시간이 같다면 먼저 시작하는 회의를 선택

def Greedy(T):
    T.sort(key=lambda T: T[0])
    T.sort(key=lambda T: T[1])
    L = [0]
    k = 0
    i = 1
    while i < len(T):
        if T[i][0] >= T[k][1] and k != i:
            L.append(i)
            k = i
        else:
            i += 1
    return L

⇒ 수행시간 : 정렬 + 회의 개수 = $O(nlogn) +O(n)$ = $O(nlogn)$

허프만 코드(Huffman Coding) 문제

ASCII는 문자 하나에 고정길이 비트가 할당 → 문자가 몇개든 개당 똑같은 메모리 필요.

문자들이 나타나는 빈도수(frequency)가 다르기에 자주 사용되는 문자에게는 짧은 길이의 코드를, 자주 등장하지 않는 문자에는 조금 더 긴 코드를 할당하는 게 전체 필요한 비트 수를 줄일 수 있다. ⇒가변 길이 코드

• prefix-free code : 어떤 문자의 이진 코드가 다른 문자의 prefix(앞부분)와 같지 않은 코드 ⇒ 문자 코드의 비용은 코드 길이 * 빈도수