동적 계획법 (Dynamic Programming)

기본 개념은 wikipedia 참고
정확히는 최적 부분 구조(Optimal Substructure)를 지닌 중복된 하위 문제들(Overlapping Subproblems)을 분할 정복으로 풀이하는 문제해결 패러다임이다.
대충 답에 대한 공식을 점화식으로 표현해서 그걸 갖고 계산하면 DP라고 생각해도 별 문제 없고, 어떤 문제가 DP로 풀어야 하는 문제라는 것을 알게 되면 점화식을 세워보려고 시도하면 된다. 키워드는 '점화식'이다.

정리중

DP는 워낙 끝이 없이 방대한 분야라서.. 관련된 수많은 내용들을 정리하는 것부터가 난관이다. 아래에 있는 내용들은 n년전에 위키를 처음 쓰기 시작했을 무렵에 적어두었던 내용들이고, 이후에 수많은 지식과 깨달음을 얻었지만 어떻게 정리해야할지가 막막해서 DP 항목은 거의 업데이트를 못하고 있었다.
아직도 제대로 적어서 정리하기에는 시간도 없고 엄두가 안나지만, 나중에 시간이 난다면 적고 싶은 내용들을 대충 제목이라도 달아놓자..
DP의 개념
- DP로 풀수 있는 문제들?
  - 최적 부분 구조니 뭐니 하는 말들은 너무 직관적이지 않다. DP를 적용할수 있는 조건중 하나는, 답을 단계적인 계산과정으로 구해야 되는 문제라고 생각해보자.
  - DP는 기본적으로 상태공간의 모든 상태에 대해서 계산을 하는 '완전탐색'에 가까운 방법이다. 탐색해야 할 상태 공간을 줄여나가는 '이분 탐색'이나, 아예 특정한 조건을 만족하는 상태를 찾는 '그리디' 와는 다르게, 모든 상태에 대해서 값을 구한다. 다만 중복된 계산을 피함으로써 계산을 효율적으로 하는것 뿐이다.
  - DP를 통해서 푸는 문제의 거의 대부분은 최댓값 문제 또는 갯수 문제이다.
    - 최댓값 문제는 어떤 상태 x에 대해 값을 계산할수 있을때, 그 함수를 f(x)라고 하면, max(f(x))를 구하는 문제이다
      - 여기서 확장되는 문제는 최댓값을 갖는 x를 찾는 것으로, 흔히 DP 역추적 문제라고 불린다. 최댓값을 구하는 점화식을 세우는데에 성공했다면 보통은 기계적으로 적용할수 있다.
    - 갯수 문제는, 조건을 만족하는 상태의 개수를 구하는 문제이다. 어떤 상태 x를 참,거짓으로 구분할수 있는 조건이 있을때, 그 함수를 p(x)라고 하면, size({x|p(x)==True}) 를 구하는 문제.
      - 여기서 확장되는 문제는 k번째로 큰 x를 찾는 것이다. 이것도 부분 상태들의 갯수를 다 구했다면, 보통은 기계적으로 적용할 수 있다.
      - 확률을 구하는 문제도, 만족하는 개수를 전체 개수로 나누는 것이기 때문에 그냥 개수를 세는 문제와 별 차이 없다. 기댓값의 선형성을 이용해서 기댓값을 구하는 문제도 마찬가지.
  - 최댓값 문제와 개수 문제는 나이브하게 풀때는 비슷하게 풀리지만, DP를 최적화하는 각종 트릭들을 적용하려고 보면 적용되는 대상이 다르다
    - Monotone deque, 세그먼트 트리 등을 이용해서 최댓값을 빠르게 구하는 최적화는 최댓값 DP에서 사용된다
    - CHT, DnC Opt, slope trick 등등도 마찬가지로 최댓값 DP에 사용된다.
    - 점화식을 행렬곱으로 변환해서 계산하거나 보스턴-모리 알고리즘으로 빠르게 푸는 것은 선형 점화식일때에 사용되고, 이는 개수 DP일때 가능하다
    - 몇개의 샘플로부터 DP점화식을 찾아내는 벌캠프-매시 알고리즘도 선형 점화식을 찾아주는 것이니까 개수를 찾는 문제에서 사용된다
상태 정의에 따른 분류
- 어떻게 점화식이 성립할수 있도록 상태를 정의할것이냐가 문제마다 너무 달라서 끝이 없는 창의력이 필요한 부분이지.. 상태를 정의해서 점화식을 찾으면, 계산하는 방법은 비교적 카테고리들로 나눠볼수 있다.
- 자연수
  - DP테이블은 1차원 배열
  - DP[i]를 가능한 트랜지션은 거의 한정적이다.
    - 모든 이전항들로부터 계산하거나
      - 온갖 최적화
    - 이전 k개 항으로부터 계산하거나.
      - 토글링
- 자연수의 페어
  - DP테이블은 2차원 배열
  - 의미는 정말 다양하지만, 표현 자체는 2차원 배열로 되고 트랜지션도 비교적 정형화되어있다
- 자연수의 k-튜플
- 1차원 구간
  - 구간을 분할하는 방법에 대한 DP.
- 트리
  - 트리DP.
  - 거의 대부분의 경우는, 자식 노드들의 값들로부터 부모노드의 값을 계산하는 형태이다.
- DAG
  - 트리DP의 일반화 느낌이지만 조금 더 복잡한 경우도 있다.
  - 자식 노드들의 값들로부터 부모노드의 값을 계산하는 형태 외에도, 모든 자손들로부터 부모노트의 값을 계산해야 하는 경우
    - 트리에서는 자손들이 겹치지 않으니까 그냥 부모노드에 누적시켜서 처리할수 있었는데, 일반 DAG에서는 그건 안된다.
    - 예를 들면, chain(totally ordered subset)의 개수를 세는 문제가 있다.
    - transitive closure 를 만들어서, 거기에서 자식로부터 부모값을 구하면 된다.
- 집합
  - 보통 비트마스크를 이용해서 표현된다
  - 집합에 원소를 하나씩 추가해나가면서 업데이트 하는 문제. 즉, DP(S)를 DP(S-{xi})들로부터 구하는 문제들
  - 집합의 원소들과, 마지막으로 추가한 원소까지 같이 포함해서 상태를 정의하는 형태
    - 가능한 순열들중에서 최적값을 구할때 주로 사용된다. 대표적으로 외판원문제
  - 집합의 값이, 모든 부분집합들로부터 계산되는 형태 - SOS DP 방법으로 최적화
- 이전 k항의 상태값들
  - 실제 현재 항의 계산에는 이전 k번째 항만으로 계산이 가능하지만, 이후 항들에 대해서 값을 계속 계산하기 위해서는 이전 k개 항의 값들을 모두 들고서 거기에 따라 각각 값을 갖고있어야 한다
  - bit scrolling DP, connection profile DP
  - 비트마스크를 사용하거나, 상태공간을 압축해서 표현하거나..

1차원 DP

상태 공간이 n 이하의 자연수인 문제. 그래서 문제는 그냥 n번째의 값을 구하는 것이 된다.
이 경우는 유형이 다양하지는 않다. 잘 정리해보면 대부분의 문제는, 매번 한가지의 액션을 선택하고, 그렇게 순서대로 n번의 액션을 선택했을때 만들수 있는 결과값의 최댓값, 또는 액션을 선택하는 방법의 수가 된다.
당연히 항상 모든 액션을 선택할수 있으면 문제가 너무 쉬워지고, 보통은 현재 선택할수 있는 액션이 이전에 선택한 액션에 따라서 제한을 받게 된다.
보통은 그래서 dp[i][x] 에는 i번째에 x번 액션을 선택했을때 i번째까지 얻은 최대 점수, 또는 i번까지 액션을 취해고 i번째에 x번 액션을 선택

이하는 예전에 적었던 글들로 리뉴얼이 필요하다

상향식과 하향식

상향식 - bottom-up - Tabulation
하향식 - top-down - Memoization
기본적으로는 상향식이 빠르고 코드도 심플하니, 디폴트로는 상향식을 쓰는걸로 하자.
하향식을 쓰는게 나을때
- 점화식의 인덱스가 자연수들로 평범하게 떨어지지 않아서 어디서부터 시작해야 할지 고민하기 복잡할때.
  - 집합이나 트리에 대한 DP등..
- 본 문제를 푸는 데에 부분문제중 일부만이 필요할 때. 상향식은 모든 부분문제에 대한 테이블을 전부 채워가면서 올라가는데, 사실 모든 테이블을 전부 채우지 않고도 문제가 풀릴수 있는 경우
- top down으로 푼 문제들
  - 1521.. 리프 스테이트에서부터 상위 스테이트들로 순서대로 이터레이션 시키는것이 어렵다.

종류

결국 DP는 큰 범위에 대한 값을, 작은범위에 대해서 계산했던 값들을 이용해서 빠르게 계산할수 있으면 적용 가능하다. 큰 범위와 작은 범위에 해당될수 있는 것들은 다양한데, 대표적인 것들을 이런것들이다.
[1차원 DP] - N에 대한 값을 1 ~ N-1 까지의 값들로부터 계산할 수 있는 경우
- N-1, N-2, .., N-i 까지의 값들로만 계산할 수 있는 경우
[2차원 DP] N,M에 대한 값을 1 ~ N-1, 1 ~ M-1 까지의 값들로 부터 계산할 수 있는 경우
[비트마스킹을 이용한 DP] 집합에 대한 값을, 부분집합에 대한 값들로부터 계산할 수 있는 경우
[트리에서의 DP] 트리에 대한 값을, 서브트리에 대한 값들로부터 계산할 수 있는 경우
[위상정렬을 이용한 DP] DAG에서 현재 노드에 대한 값을, predecessor 노드들에 대한 값들로부터 계산할 수 있는 경우
[구간 분할에 대한 DP] 구간에 대한 값을, 부분구간에 대한 값들로부터 계산할 수 있는 경우

1차원 DP

인접 k항에 대한 점화식

A(n) = f(A(n-1), A(n-2), …, A(n-k)) 인 경우
기본적으로 시간복잡도는 O(kn)이 된다. (k개의 인자로부터 f값을 계산하는게 O(k)라고 가정)
그리고, 슬라이딩 윈도우라 불리는 방법으로 공간복잡도를 O(k)에 처리할수 있다. 최근 k항의 dp값만 유지하고 나머지는 버려도 된다.
- 하향식에서는 이 기법이 불가능하다
변수명을 통일하자.
- k=1일 때에는, dp_cur과 dp_prev를 사용한다. A(n) = f(A(n-1)) 이면 dp_cur = func(dp_prev) 이렇게 업데이트하자
- k=2일 때에는, dp_cur과 dp_prev, dp_pprev를 사용한다. A(n) = f(A(n-1)) 이면 dp_cur = func(dp_prev, dp_pprev) 이렇게 업데이트하자
- k>=3 이상일때는 그냥 deque를 쓰자.
그래서 코드는 보통 이렇게 된다
- [To be filled]

인접 k항의 선형함수

f가 선형 함수, 즉 점화식이 dp[n] = c[1]*dp[n-1] + c[2]*dp[n-2] + … + c[k]*dp[n-k] 형태일경우, 선형 동차 점화식이라고 한다. 이 경우에는 DP로 푸는 대신, 행렬의 거듭제곱 형태로 변환하여 더 빠르게 계산 가능하다
- 최근 k개 항으로부터 계산된다면 표현된다면, 행렬 거듭제곱으로 O(k^3*logn)에 풀수 있다. k가 큰 경우에는 키타마사법과 FFT를 버무려서 O(klogk*logn)까지 줄일수 있다
보통 최댓값이나 최솟값을 찾는 문제라면, f에 min이나 max가 들어가므로 해당이 안되지만, 모든 경우의 수를 찾는 문제라면 f가 선형 함수가 되어서 이 방식을 적용할 수 있는 경우가 많다.
- 대표적으로 피보나치 함수도 이 방법으로 구할수있다.
자세한것은 선형 점화식 참고

인접 k항의 최솟값에 의존하는 점화식

f가 인접 k항의 최솟값을 받는 함수인 경우에는, 인접 k항의 최솟값을 빠르게 구해서 전체 시간 복잡도를 줄일수 있다.
Monotone deque 테크닉을 이용하면 인접 k항의 최솟값(또는 최댓값)을 O(k)가 아닌, amortized O(1)에 구할수 있다. 최솟값을 구한 뒤에 상수시간 처리만 필요하다면, 결국 하나의 dp값을 O(1)에 구할수 있으므로, 전체 계산은 O(n)에 할수 있다.
백준에서는 '덱을 이용한 다이나믹 프로그래밍' 이라고 태그되어있다
자세한 것은 Monotone deque 참고

2차원 DP

2개의 변수에 대한 식으로 표현되는 경우. 이 경우의 구현은 2차원 배열을 채워나가는 식으로 계산하게 된다.

행 순서대로 채우는 DP

흔한 경우.
어떤 행에 대한 값이 이전 행에 대한 값들로 계산되는 형태
- dp[i][j] = f(g(dp[0][0]), …, g(dp[0][N]), g(dp[1][0]), …, g(dp[1][N]), …, g(dp[i-1][0]), …, g(dp[i-1][N]))

대충 이렇게 된다.

dp = [[0] * M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            dp[i][j] = some_func(dp[:i], dp[i][:j])
    
    print(dp[N - 1][M - 1])

인접 k개 행에 대한 점화식

인접 k항에 대한 점화식의 2차원 형태
i번째 행에 대한 값이 i-1, i-2, …, i-k 행만 갖고 계산 가능한 상황. 이때는 N*M의 테이블을 만들 필요 없이, K*M의 테이블만으로 충분하다
대부분은 k=1인 경우인데, 이때는 그냥 1차원 배열만으로 된다.

k=1 일때, 코드는 대충 이렇게 된다.

dp_cur = [0] * M
    for _ in range(N):
        dp_cur, dp_prev = [0] * M, dp_cur
        for i in range(M):
            for j in range(N):
                val = update(val, func(dp_prev[j]))
            dp_cur[i] = val
    
    print(dp_cur[M - 1])

테이블이 sparse한 경우

몇개의 셀에만 값이 채워져있고 나머지는 0으로 채워져 있는 상태에서, 값이 채워진 칸의 주변에서만 업데이트가 일어나는 형태.
이때는 테이블을 다 만들고 모든 셀을 iterate하는 것보다 그냥 map을 이용해서 값이 채워진 셀만 유지하는 것이 속도면에서 효율적인 경우가 있다
대표적인 예로는 0-1 knapsack 문제가 있다.
- 이 문제의 BOJ 버전인 평범한 배낭에서 좀더 구체적인 예시가 설명되어있다

대충 코드는 이런 식이다

dp_cur = {0: 0}
    for i in range(N):
        dp_cur, dp_prev = dp_cur.copy(), dp_cur
        for prev_i, prev_v in dp_prev.items():
            cur_i, cur_v = func(prev_i, prev_v)
            dp_cur[cur_i] = cur_v
    
    print(dp_cur[M-1])

구간 분할 방식에 관한 DP

2개의 변수가 어떤 구간의 시작 인덱스와 끝 인덱스인 경우. 어떤 구간에 대한 값이 그 안에 포함된 더 짧은 구간에 대한 값들로 계산되는 형태. 말하자면 점화식이 다음처럼 생긴 형태.
- dp[i][j] = f_k(g(dp[i][k], dp[k][j], i, k, j))
구간 분할 방식에 관한 DP 참고

집합에 대한 DP

어떤 집합 S에 대한 함수값이, 그 부분집합들의 값에 대한 식으로 계산되는 경우들이다.
전체집합의 부분집합들을 표현하는 것을 비트마스킹으로 처리하는 것은 유명한 테크닉이다. 집합을 정수형으로 표현하는 것도 가능하고, 집합과 그 부분집합간의 관계가 키값의 대소관계로 유지되는 것도 상향식 재귀를 가능하게 해준다. 하지만, 그냥 집합의 튜플 자체를 key로 잡고 재귀로 표현하는 것이 가독성에서는 오히려 나은 점도 있다보니, 아직은 그때그때 내키는대로 쓰는 중.. 어느쪽을 확정적으로 사용할지는 아직 고민중.

퍼뮤테이션에 대한 DP

n개의 원소를 배열하는 순서에 따라 값이 결정되는 함수의 최대값을 구하는 형태.
그냥 전부 다 해보려면 n!가지의 배열법을 다 해봐야 하지만, 남은 원소에 대한 함수값이 앞선 배치 순서에 영향을 받지 않는다면, dp[S] = max(f(x) + dp[S - x]) 와 같이 쓸 수 있고, 이것은 S의 모든 부분집합 2^|S|개에 대한 테이블을 만들고, 각각을 O(|S|)에 채우면 되므로 O(|S| * 2^|S|)로 풀수 있다.

SOS DP

링크 참고
이름이 거창한데, 그냥 Sum over Subsets의 약자로.. f[S] = sum(g[S - x] for x in S) 와 같은 형태로 된 f를 모든 집합에 대해서 구하는 방법이다
- 예를 들면 f[{x,y,z}] = g[{y,z}] + g[{x,y}] + g[{y,z}] 같은 형태..
비트마스크로 바꿔서 생각해보면, N 이하 모든 자연수 i에 대해서, i & x = i 인 모든 x의 함수값의 합을 구하는 것과도 동일하다
DP를 이용해서, {전체 원소의 갯수} * {집합의 갯수} 만큼의 테이블을 이용해서 O(NlogN)에 풀 수 있다 (N은 집합의 갯수). 그리고 이터레이션 순서를 잘 조절하면 공간복잡도 O(N)에 굉장히 깔끔한 코드로 정리할 수 있다. (코드는 깔끔하지만 파이썬에서의 실행속도는 매우 느리다)

for i in range(n.bit_length() + 1):
    for num in range(n + 1):
        if num & (1 << i):
            dp[num] += dp[num ^ (1 << i)]

최적화 테크닉

[To be filled]

목차

동적 계획법 (Dynamic Programming)

정리중

1차원 DP

상향식과 하향식

종류

1차원 DP

인접 k항에 대한 점화식

인접 k항의 선형함수

인접 k항의 최솟값에 의존하는 점화식

2차원 DP

행 순서대로 채우는 DP

인접 k개 행에 대한 점화식

테이블이 sparse한 경우

구간 분할 방식에 관한 DP

집합에 대한 DP

퍼뮤테이션에 대한 DP

SOS DP

관련 문제

최적화 테크닉