210707 그리디 알고리즘(Greedy, 탐욕)

동적 프로그래밍(DP) 을 사용할 때 너무 많은 작업을 하는 경우가 발생하기에 보완하는 목적으로 생김

차이점 : 그리디 알고리즘은 미래를 생각하지 않고 각 단계에서 최선의 선택을 하는 방법

 

활동 선택 문제 (Activity Selection Problem)

활동 선택 문제란, 한번에 하나의 활동만 처리할 수 있는 하나의 방에서 주어진 활동들에서 최대한 많은 활동을 처리할 수 있는 스케줄을 짜는 문제입니다.

문제를 해결하는 아이디어로는 보통 평범하게는 활동시간이 짧은 순으로 정렬하여 짧은 것부터 선택하는 등의 방법들을 생각할 수 있지만, 최적의 방법은 끝나는 시간순으로 선택하면 됩니다. 

예시 

 

 

허프만 부호화 (Huffman Coding)

 

문자의 빈도나 확률 정보 등을 이용하여 통계적으로 압축하는 방법

 

1. 압축할 문자열에서 각 문자의 빈도 수 계산
2. 빈도 수를 우선 순위로 최소 힙을 구성한다
3. 빈도 수가 가장 작은 두 노드를 삭제하고, 삭제한 두 노드로 트리 구성 (작은 것을 왼쪽 자식, 큰 것을 오른쪽 자식)
4. 노드가 하나 남을 때까지 반복, 마지막 노드가 루트 노드가 된다

이 과정을 통해 출현 빈도가 높은 문자는 더 빠른 탐색 시간을 갖게 된다.

 

• 예시 문제

 

• 해결법

슈도코드

Huffman( C [ 1...n ] ){
	Q =c;
    for( i =1 to n-1 ){
    	Z= new internal tree node;
        Z.left = X = Q.extractMin() //최소 가능성 추출
        Z.right = Y = Q.extractMin() //최소 가능성 추출
        Z.prob = X.prob + Y.prob //부모 노드에 자식 노드 확률 합 저장
        Q.insert(Z)
    }
    return Q의 마지막 원소의 left
}