알고리즘 문제 풀이/알고리즘 이론 공부

4장 Greedy Algorithm

잘잔디 2023. 7. 30. 16:23

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 방식으로 풀 수 없는 문제이다.
  1. DP solution
    • DP 표를 만든다.
    image
  • 그러면 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을 계산하지 않도록 주의해야한다.는 개념.