Greedy algorithm

Concept : locally optimal 선택을 하는것이 결과적으로 globally optimal solution을 만든다.

Fractional 0–1 knapsack problem

0–1 knapsack problem은 greedy로 풀지못하는 반면, Fractional 0–1 knapsack problem은 greedy로 풀 수 있다. value/weight가 높은것 먼저 삽입하면 된다. 공간이 남으면 fraction of item을 삽입하면 됨.

Activity Selection Problem : Greedy Algorithm

1)시작-종료 시간이 있을때 종료시간에 따라서 오름차 순으로 정렬.

2)정렬된 리스트에서 가장 먼저 끝나는 활동 선택.

3)이미 선택된 활동의 종료시간과 겹치지 않으면서 가장 먼저 끝나는 다음 활동을 선택.

4) 모든 활동을 확인할 때까지 반복.

Greedy Construction of Huffman Code

1단계 : 빈도수를 오름차순으로 정렬

2단계 왼쪽 두개를 묶고 정렬, 이걸 반복한다.

최종적으로codeword는 각각 트리에서 0,1로 마킹하고 root에서부터 leaf로 내려오면서 읽는다.

[codeword] a: 0, b: 101, c: 100, d: 111, e: 1101, f:1100

시간복잡도 :

naive algorithm)

빈도수에 따라서 정렬하는데 O(nlogn),

각 스테이지마다 새롭게 생긴 node를 정렬하는데 O(n), 병합하는데 O(1) 소요.

T(n) = T(n-1) + O(n) => O(n²)

priority queue algorithm)

가장 최저값을 두번 뽑기 : 2* O(logn)

합치기 : O(1)

삽입하기 : O(logn)

T(n) = T(n-1) +O(logn) => O(nlogn)