4장 Greedy Algorithm

chap4 Greedy algorithm design pattern

=과거 미래에 상관없이 현재 순간에 최선을 고르는 방식. = local optimal 해결책임 , global optimal solution이 아닐 수 있음.

greedy 알고리즘의 반복순서

1. selection step = solution set에 들어갈 현재의 최선을 선택함
2. feasibility check = 타당한지 확인함(가능한지)
3. solution checking step = 새로운 solution set이 문제를 만족하는 해답인지 확인.
   • global optimal solution을 얻기 위해 local optimal을 선택하는 과정

Minimum spanning Tree 문제 = 최소 비용 신장트리

1. Select an edge
2. Cycle 없는지 check
3. 다 연결하고 문제 없는 spanning tree인지 확인.(만든 tree의 node수가 전체 node수와 같으면 종료)

• MST문제는 Prim와 Kruskal 알고리즘 2가지 방식이 있음.

Prim’s greedy MST

1. vertex(시작지점)을 골라주고,
2. 가장 가까운 vertex 선택
3. cycle이 아니면 통과하고 vertex를 리스트에 포함시킴. + adjacency matrix 값 변경
4. 2~3 반복하다가 vertex 개수 확인 후 같으면 종료

• adjacency matrix를 만들어 관리.
• time complextiy = N^2 ,basic op = comparison

Kruskal ‘s greedy MST = edge가중치를 정렬하여 가장 작은 값 포함시키기

1. edge weight가 가장 작은 edge 선택
2. 선택한 edge가 cycle 생성하는지 체크
3. 완성되면 반복 종료

• basic op = comparison = mergesort를 사용하여 edge를 정렬(mlogm)하는 과정
• worst case인 경우 n^2 logn 까지 나오기도 함.
• best case 는 nlogn까지도 나옴.
• average case = mlogm 인데, n-1≤ m ≤n(n-1)/2임 m = number of edges n = number of vertices , 즉 그래프 형태에 따라 complexity가 달라짐 edge가 많을 수록 더 느려진다는 문제점

Dijkstra 알고리즘 shortest path, single → many destination

• DP의 floyd 알고리즘을 사용하면 many → many가 n^3에 걸쳐 가능했다.(graph방식)
• 그래서 greedy 방식인 Dijkstra 알고리즘을 사용하겠다.(spanning tree방식)

1. select new vertex
2. vertex를 완료 리스트에 포함
3. vertex개수 비교로 반복종료

• adjacency matrix사용
• basic OP = comparison T(n) = n^2 = code word 를 binary code로 효율좋게 정리하는 방식

Huffman Code Tree

fixed

• length binary code 방식은 문자 개수만큼 비트를 할당해주는 비효율적인 방식으로 character하나당 log_2(n) 만큼의 bit가 필요함
• 비효율적이라 아래방식 사용함.

variable

• length binary code는 빈도수를 확인해 문자마다 구분 가능한 가장 효율적인 bit를 부여함. = optimal binary code problem

1. n개의 값들을(character들을) 빈도수에 따라 정렬한 후(min heap 구현) 가장 작은 값 2개를 merge한다.
2. single tree 가 될때까지 반복한다.

• 유용성 계산은 bit 수 *확률을 모두 더하면 된다.
• fixed -그 값/ fixed *100 을 하면 reduction of bit의 퍼센트를 얻을 수 있음 = ex) Huffman’s encoding은 25% less memory than its fixed-length code 라고 답을 적음

0-1 knapsack problem을 통한 greedy, DP 비교

1. Trial and Error solution 모든 경우를 다 해보면 2^n complexity 필요
2. greedy algorithm solution
   • price/weight 값으로 정렬한 후 .가장 적당한거 선택.
   • 그냥 price 높은 순서대로 weight가 넘치지 않게 선택.

• 하는 두가지 greedy 풀이 경우가 있는데 상황에 따라 optimal 값이 다르더라 = greedy 방식으로 풀 수 없는 문제이다.

3. DP solution
   • DP 표를 만든다.
   

• 그러면 optimal 값을 얻어낼 수는 있지만, n*n!이라는 time complexity를 가진다. 이를 줄이기 위해서 modified 방식이 있는데, 모든 entry를 구할 필요는 없다는 생각에서 나옴. 위 표는 꽉차있지만 오른쪽 아래로 가는 대각선으로 선을 긋고 선이 지나는 중간 부분을 제외한 아래 부분은 필요없지 않냐는 생각
• =2^n의 time complexity의 worst case 결과를 가지더라.

• 그래서 나온게
• Memory Function = hybrid of Divde and conquer and DP

= 둘의 장점을 함쳐서 오직 필요한 sub problem만 계산하도록 해보자

• DP는 unnecessary sub problem을 계산하지 않도록 주의해야한다.는 개념.