[알고리즘] Chap.5 Greedy algorithm

2006년 나온 알고리즘 책(S. Dasgupta et al.)을 공부하면서 개인적으로 정리한 노트입니다. 관련된 백준 문제를 풀어서 포스팅을 (언젠가) 올리면, 포스팅으로 대체할 생각입니다.

 

5.1 Minimum Spanning Tree(MST)

  - Spanning Tree, MST의 정의

    - Tree's property

      - n node with n-1 edge

      - Any connected, undirected |E| = |V|-1 graph => Tree!

      - Undirected graph with unique path between any pair of node => Tree!

  - MST 만드는 알고리즘

    - 1. Kruskal

      - Edge를 weight 따라 오름차순 정렬 후, 그리디하게 cycle을 만들지 않는 edge 추가

      - Disjoint set

        - 3 operations(makeset(x), find(x), union(x,y))

          - makeset(x): node x가 들어간 set 생성, O(1)

          - find: node x가 들어간 disjoint set의 root 반환, set height에 의존

          - union(x, y): x, y가 들어간 disjoint set 2개를 합침

            - 한 쪽의 root가 다른 한 쪽의 root를 가리키면 되므로 find 이후는 O(1)

            - Union by rank

              - 효율적인 연산 위해, height 큰 쪽이 root가 되도록 union

        - Path compression

          - find(x)에 들어가는 시간 줄이기 위해(height 감소)

          - find(x) 수행 시 x로부터 root까지 가는 길목에 있는 모든 node가 root를 가리키도록 변경

      - 시간복잡도: edge 정렬하는 데 걸리는 시간 O(ElogE) (+ union-find)

    - 2. Prim

      - Cut property

        - Part of MST S, 그 외의 vertex set V-S, S 내부의 edge set X

        - X와 {S와 V-S를 잇는 minimum weight edge}의 합집합 => MST를 구성하는 edge

        - S와 V-S를 잇는 minimum weight edge를 greedy하게 찾아나가자

      - Cut property 따라서 greedy하게 부분 MST와 최소 weight로 연결된 vertex 추가

      - 다익스트라와 비슷하지만, priority queue의 key로 들어가는 값이 다름

        - 다익스트라: 시작점으로부터 vertex까지의 거리

        - 프림: 부분 MST와 vertex를 잇는 edge의 weight

        - Unsorted array 사용할 때보다 prioirity queue 사용하면 시간복잡도 줄일 수 있음

      - 시간복잡도

        - 1. Unsorted array 사용 시 매 번 최소 weight vertex 찾는 시간 O(V^2)

        - 2. Priority queue 사용 시 O(VlogV + ElogV)

          - V번 Priority queue에서 뽑고 heap 재구성 시간 + E번 priority queue의 key update하고 heap 재구성 시간

    - 여담으로 Sollin 알고리즘도 있는데, 여기에는 언급되지 않음

 

5.2 Huffman Coding

  - 그냥 압축시키지 말고, 문서 내 단어의 빈도수를 이용해서 압축해보자!

    - 빈도수가 많은 문자는 적은 bit, 빈도수가 적은 문자는 많은 bit 사용 => 전체 문서를 표현하는데 필요한 공간 감소

  - Min heap 사용

  - 빈도수를 key로 해서 heap 만들고, 가장 작은 빈도수를 가진 두 노드를 child로 하는 node를 만들어 하나로 합침

    - Heap 내 key가 100 60 40 30 20이면, 30+20을 합치고 100 60 50(20+30) 40으로 재정렬

  - 빈도 수가 적은 문자는 많은 bit로, 빈도 수가 많은 문자는 적은 bit로 저장 가능 -> 기존 문서보다 압축됨!

 

5.3 Horn formula

  - 봐도봐도 이해가 잘 안 가네요....

 

5.4 Set cover

  - 어떤 집합에 대한 여러 부분 집합이 있을 때, 최소 갯수 집합으로 전체를 커버하는 경우를 찾자!

  - ex. 도시 10개, 각 도시에 소방서를 지을 때 커버할 수 있는 범위 제한, 각 소방서마다 들어가는 비용이 다름

  - 비용을 무시할 경우, greedy하게 찾으려면 가장 많은 범위를 커버할 수 있는 소방서부터 지어야 함

    - Optimal하지 않을 수 있음!

  - 비용을 고려하면 (비용/커버 가능 도시) 기준으로 greedy하게 찾을 수 있음

  - 비용 무시하는 경우 optimal이 k개 set이면, greedy한 경우는 klogn개 set으로 커버 보장

    - 증명!