[알고리즘] Chap.6 Dynamic Programming

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

 

6.1 Shortest path in dags, revisited

  - Chap.4에서 본 문제가 사실 DP의 관점으로 볼 수 있음

  - DP의 조건

    - Overlapping subproblem: 큰 문제가 여러 부분문제로 분할되고, 겹침

    - Optimal substructure: Optimal한 문제 결과가 부분문제의 optimal로부터 설계될 수 있는가

  - Memoization: 같은 부분문제를 여러 번 풀 필요가 없으니까, 풀고 어디에다 저장해두고, 필요할 때 쓰자!

 

6.2 Longest increasing subsequence

  - 수열이 주어졌을 때, 증가하는 가장 긴 부분 수열을 찾는 문제

  - 이거도 dag에서의 가장 긴 path 개념으로 생각할 수 있음

    - 근데 수열이 주어졌을 때 dag 만드는데 걸리는 시간...?

  - O(N^2)로 가능하지만, Binary search 이용해서 O(nlogn)에 해결 가능

    - 백준 11053번

 

6.3 Edit distance

  - 단어 A를 B로 바꿀 때, 최소 횟수의 연산을 통해 바꾸는 문제

    - 가능한 연산은 삭제(a -> -), 추가(- -> a), 수정(a -> b) 3종류

  - 예를 들어, 문자 A: abcdef를 문자 B: bzdefg로 바꿀 때 a 삭제, c->z 수정, g 추가로 가능(연산 3회)

    - 이 때 abc -> bz로 바꾸는 문제의 optimal solution은 abc -> b, ab->bz, ab->b 3가지 부분문제로부터 구할 수 있음

      - abc -> b 문제: 연산 2회(a 삭제, c 삭제)

        - 여기서 abc -> bz로 넘어가려면, z 추가 연산 1회 필요

      - ab -> bz 문제: 연산 2회(a 삭제, z 추가)

        - 여기서 abc -> bz로 넘어가려면, c 삭제 연산 1회 필요

      - ab -> b 문제: 연산 1회(a 삭제)

        - 여기서 abc -> bz로 넘어가려면, c->z 연산 1회 필요

          - 만약, 문제가 abc -> bc인 경우, 추가되는 문제인 A[2]와 B[1]이 같으므로 추가 연산 필요 없음

    - 결국 2+1, 2+1, 1+1 비교해서 minimum 값음 1+1 선택, 그래서 abc -> bz로 바꾸는 데 optimal soultion 2회

  - 백준 15483번

 

6.4 Knapsack

  - 제가 올린 게시글입니다.

  - 백준 12865번

 

6.5 Chain matrix multiplication

  - 제가 올린 게시글입니다.

  - 백준 11049번

 

6.6 Shortest path

  - Greedy를 다룬 5장에서 다익스트라, 벨만-포드를 봄

    - 모든 정점-모든 정점 간 최단 거리를 한 번에 구할 수는 없을까?

      - 플로이드-와샬 알고리즘!

  - Optimal substructure : 특정 경로 내 무수히 많은 정점 있을 때, 중간중간 정점이 각각 최단 거리임이 확인된다면?

    - 최단 거리들을 모두 이은 전체 경로 또한 최단 보장!

    - 1~2~3~4라는 경로가 있을 때, 1~2, 2~3, 3~4가 각각 최단 거리면 1~2~3~4 또한 optimal

  - Graph의 adjacency matrix가 초기 상태

    - 중간에 거쳐가는 노드(intermediate node)가 없다고 할 때, 이동 가능한 최단 거리를 나타냄

    - 이제, intermediate node를 1개씩 늘려가면서 최단 거리를 찾자

      - 2에서 3으로 가는 방법이 2->3, 2->1->3 두 가지가 있을 때, 초기 상태에서는 2->3만 허용

      - 1이 intermediate로 허용되면 2->3, 2->1->3을 비교해서 optimal한 경우 저장

      - 이렇게 모든 노드를 순차적으로 intermediate node로 허용

    - 만약 최단 경로까지 구하려면 matrix 하나 더 만들어서, A->B로 가는 최단 경로에서 B 직전에 방문하게 되는 노드를 [A,B]에 저장

  - 백준 11404번

 

6.7 Independent sets in Trees

  - Tree 내 노드 갯수가 최대인 독립집합을 구해보자

    - 독립집합의 정의: 집합 내 모든 node 간 edge가 없으면 그 집합은 독립집합

    - Graph 내에서 찾는 건 힘든데, tree에서 찾는 건 linear time에 가능

  - 현재 노드 A가 독립집합에 포함되면, A의 child는 독립집합 포함 불가

    - 이 경우 A의 grandchild부터 독립집합 포함 가능

  - 현재 노드 A를 독립집합에 포함시키지 않으면, A의 child의 독립집합 그대로 사용 가능

  - 이 두 가지 경우를 비교해서 더 큰 독립집합이 되는 쪽을 골라나가자!

  - 백준 2213번(책에서는 최대 노드 갯수, 문제에서는 최대 weight 합)