Greedy

번역할 때는 탐욕법이라고 번역을 하기도 하고, 그냥 그리디 알고리즘이라고도 부른다.
여기서 그리디는 뒷일 생각하지 않고 가장 좋아보이는 것부터 하나씩 순서대로 처리하는 것이다.

부분 가방 문제 등이 해당한다.

명확한 기준 하나를 정하고 그 기준에 따라 미리 정렬을 한 다음에 하나씩 처리해나가는 방식이 있다.
하나씩 순서대로 처리하기 때문에 :

• 문제 크기가 순차적으로 줄어드는 구조이다.
• 전체의 시간 복잡도가 정렬의 시간 복잡도에 의해 결정된다.

최적화 문제를 다룬다는 점에서 비슷한 점이 있는 Dynamic Programming과 비교해보자.

• DP는 결정 트리에서 분기하는 경우들을 다 따져본다. 근본적으로는 여러가지 가능성을 전부 고려한다고 볼 수 있다.
  • 그리디는 분기를 고려하지 않는다. 분기를 고려 할 필요가 없는 상황에서 그리디를 적용 할 수 있다. 어떤 문제를 어떤 상황에서 푸는지에 따라서 차이가 있다.
    • 시험을 볼 때는 시간 제한이 있으니 풀 수 있는 것들을 우선 푸는 수험생을 생각해보면 된다.

특징

• 구현이 쉽고 빠르다.
• 문제에 따라 해당 결과는 최적이 아닐 수도 있다. 특정한 문제에 대해 아주 빠르고 최적화 된 문제에서 효과를 볼 수 있다.
• 첫 번째 선택을 했을 때, 그 다음 선택이 좋은 선택이 되는 것을 방해하지 않는 기준을 찾게 된다.

대표 사례

허프만 인코딩에 대해 알아보자. 허프만 인코딩은 파일을 압축 할 수 있는 방법 중에 하나인데, 복잡한 내용을 단순하게 치환하는 원리이다.

abccbeaa 라는 8글자의 코드가 있다고 하자. 컴퓨터에서는 ASCII 코드로 인해 한 글자는 8개의 비트로 표현되는데, 이 부분에서 필요한 부분만 고려하자는 것이다. 그래서 한 테이블에 모든걸 나타내보면 이렇게 된다 :

 

문자	코드	길이	허프만 적용 코드	적용된 길이	특이사항
a	00110001	8	000	3
b	00110010	8	001	3
c	00110011	8	010	3
d	00110100	8	011	3
e	00110101	8	110	3

길이가 8인 코드는 3으로 치환 될 수 있다. 그럼 길이 8을 가진 글자 8개로 64비트를 사용하던 전체 길이는 3 * 8, 24비트로 줄어든다.
데이터가 복잡해질 수록 압축효과는 떨어지지만 유의미한 효과는 여전히 있다.

여기서 그리디가 들어가는 것이 뭐냐? 바로 글자의 사용 빈도를 보고 따지자는 것이다. 예를 들어 이러한 내용을 고려 할 수 있다 :

a	45%의 비중	01100001	허프만으로, 0
d	16%의 비중	01100100	허프만으로, 101
b	13%의 비중	01100010	허프만으로, 111

근데 재밌는건 이런 예제이다.

a	0
b	1
c	01

01을 딱 보고 C인지  ab인지 알 길이 있는가? 이런 상황을 막기 위해 그리디를 이용한 인코딩은 규칙을 따른다 :

• 모든 글자는 이진수로 변환한다.
• 더 많이 나타나는 글자가 더 짧은 허프만 인코딩 코드를 가진다.
• 코드 앞부분이 겹치면 안된다.

prefix 부분, 즉 앞 부분만 겹치면 된다.

 

글자의 빈도에 따라 결정하는 허프만 트리

a : 43%

c : 28%

d : 16%

b : 13%

우선순위 큐에서 가장 낮은 두개를 묶는다. 합치고 다시 넣는다.

a : 43%

d + b : 29%

c : 28%

빈도가 가장 작은 것 두 개를 꺼내서 계속 묶는다.

b + c + d : 57%

a : 43%

트리 형태로 보자.

 

하나의 트리가 된 허프만 트리가 된다.
100% 입장에서 왼쪽 자식이면 0 추가, 오른쪽 자식이면 1을 추가한다. 그러면 이렇게 결론이 나온다!

a	0
c	11
d	100
b	101

이런식으로 리프 노드에 위치한 각각 글자에 배정이 가능하다. prefix 고정을 위해 살짝 오른쪽으로 쏠린 형태가 만들어진다.
이또한 최적화 문제이기에,글자의 빈도가 낮은 순서로 만들어가기에 그리디의 대표 예제로 간주 할 수 있다.