구간 분할 방식에 관한 DP

이런 문제를 따로 일컫는 명칭이 없는것 같아서, 이름을 적당히 붙여보려 했으나 쉽지 않다..
어떤 구간에 대한 값이 그 안에 포함된 더 짧은 구간에 대한 값들로 계산되는 형태이다.
- dp[i][j] = f_k(g(dp[i][k], dp[k][j], i, j, k))
이터레이션 할때는, 길이 1짜리 구간들에 대해서 먼저 계산하고, 그 다음 길이 2짜리 구간들에 대해서 계산하고,.. 하는 식으로 최종적으로 전체 구간에 대한 값을 구하게 된다.
- 2차원 테이블 관점에서는 가장 긴 대각선 위의 셀들을 먼저 채우고, 그 윗줄의 한칸 짧은 대각선위의 셀들을 채우고 하는 식..
n*(n-1)/2 개의 구간에 대해서 값을 계산해야 하고, 각각 구간에 대한 값을 구할때는 그 구간을 분할하는 O(n)개의 방법들에 대해서 계산해서 배교해야 하므로 전체 복잡도는 O(n^3)이 된다.

구현

구현할때는 구간을 dp 테이블과 어떻게 매핑시킬지에 대해 선택지가 있다. 구간 [x, y)에 대한 값을 (1) dp[x][y]에 저장할지, (2) dp[x][y-1]에 저장할지, (3)dp[x][y-x]에 저장할지의 선택지가 있다. [x,y) 라고 생각하면 (1)이 직관적이고, [x, y-1] 라고 생각하면 (2)가 직관적이기는 한데, (1)의 경우는 dp 테이블을 n*n이 아니라 n*(n+1)로 만들어야 하고, for 루프를 만들때 범위 설정이 조금 더 지저분하다. 그래서 (2)를 사용하기로 하자.
- (1)형태의 코드는 대충 이렇게 된다.
  - ```
  dp = [[0] * (N + 1) for _ in range(N + 1)]
  for l in range(2, N + 1):
      for i in range(N - l + 1):
          j = i + l
          for k in range(i, j):
              val = f(val, g(dp[i][k], dp[k][j], i, j, k))
          dp[i][j] = val
  return dp[0][N]
```
- (2)형태의 코드는 대충 이렇게 된다.
  - ```
  dp = [[0] * N for _ in range(N)]
  for l in range(1, N):
      for i in range(N - l):
          j = i + l
          for k in range(i, j):
              val = f(val, g(dp[i][k], dp[k + 1][j], i, j, k))
          dp[i][j] = val
  return dp[0][N - 1]
```

최적화

마이크로 최적화를 지양하기로 하긴 했지만, 이런 유형의 경우는 코드가 O(n^3)이다보니 3중 포문의 가장 안쪽 구문의 최적화정도가 전체 수행시간에 큰 영향을 미친다. 게다가, 안쪽 구문에서는 2차원 배열에서 원소를 찾는 파이썬에서(만) 비싼 연산을 두번이나 포함하게 되므로 최적화를 조금만 신경써보면 시간을 꽤 단축시킬수 있다. (뭐 그래봐야 다른 언어에 비해서 느린건 어쩔수 없다; 귀찮으면 그냥 PyPy 쓰자)
- 예를 들어, 행렬 곱셈 순서 문제의 경우, n<500 이고, O(n^3) 풀이를 정답으로 염두해서 만들어진 문제이지만 (O(nlogn)풀이법이 있기는 하다만..), Python3에서는 일반적인 구현 방식으로는 시간 초과를 피하기 힘들다. 직관적으로 작성한 다음의 코드로는 가뿐히 시간 초과가 난다.
  - ```
  for l in range(1, n):
      for i in range(n - l):
          j = i + d
          m = sizes[i][0] * sizes[j][1]
          dp[i][j] = min(dp[i][k] + dp[k + 1][j] + m * sizes[k][0] for k in range(i, j))
```
- 여기에 간단한 수준의 코드 최적화를 몇단계 더 시도해 보더라도 시간초과를 피하기는 쉽지 않다. cnt[i]를 미리 계산하고, cnt[i][k]를 인덱스 접근이 아니라 이터레이터를 통해서 접근하는 것은 Python에서의 최적화 요령이지만, cnt[k + 1][j]는 그 방법을 적용할수가 없다. 그래서 정말 억지스러운 수준의 최적화를 하는 방법은, dp 테이블에서 i≤j 인 i,j 에 대해서만 dp[i][j]에 값이 저장되는데, 이 값을 dp[j][i]에도 똑같이 저장하는 것이다. 그러면 cnt[k+1][j]대신 cnt[j][k+1]에서 똑같은 값을 가져올 수 있고 이터레이터 접근으로 처리할 수 있다.
- 그것을 활용하면 아래처럼 작성할 수 있다. 저 코드는 행렬 곱셈 순서를 유일하게 통과한 Python3 코드이다 (4000ms 이상이 걸리긴 한다..)
  - ```
  for l in range(1, n):
      for i in range(n - l):
          j = i + l
          tmp = sizes[i][0] * sizes[j][1]
          min_ij = min(dp_ik + dp_jk + tmp * sz_k[0]
                       for dp_ik, dp_jk, sz_k 
                       in zip(dp[i][i:j], dp[j][i + 1:j + 1], sizes[i + 1:j + 1]))
          dp[i][j] = dp[j][i] = min_ij
```

크누스 최적화

dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i][j] 형태의 점화식을 가지면서, C[a][c]+C[b][d]≤C[a][d]+C[b][c] 와 C[b][c]≤C[a][d] 를 만족할 때 사용 가능한 기법이다
O(n^3)의 시간복잡도를 O(n^2)으로 줄여줄 수 있다.
구사과 블로그, 전명우 블로그 참고
DP 최적화 테크닉 중에서 나름 알려진 편에 속하지만, 정작 사용할 경우가 별로 없다. BOJ에서 크누스 최적화가 태그로 붙은 문제는 불과 5개뿐인데, 그 중 2개는 최적 이진 검색 트리 문제라서 더 빠른 알고리즘을 사용할 수 있고, Painting 문제도 크누스 최적화와 관계 없는 방법으로 풀린다 (사실 이 문제에 크누스 최적화를 적용하려면 어떻게 해야 하는지도 모르겠다). 결국 크누스 최적화를 필수적으로 사용해야 풀 수 있는 문제는 Optimal Tournament과 웜뱃 두 문제 뿐이다. 너무 비실용적이다…

구현할 때에는, 구간의 값을 저장하는 dp테이블, 최적으로 구간을 분할하는 인덱스 k를 저장하는 opt테이블을 따로 만들어서 갱신해나가면 된다. 이런 형태가 된다

"""Knuth Optimization"""
dp = [[0] * N for _ in range(N + 1)]
opt = [[0] * N for _ in range(N)]
for i in range(N):
    opt[i][i] = i
for l in range(1, N):
    for i in range(N - l):
        j = i + l
        dp[i][j], opt[i][j] = min((dp[i][k] + dp[k + 1][j], k) 
                                  for k in range(opt[i][j - 1], opt[i + 1][j] + 1))
        dp[i][j] += C[i][j]
return dp[0][size - 1]

하지만, opt테이블의 경우, i-j가 l인 셀을 계산할 때에는, i-j가 l-1인 opt[i][j]의 값만 있으면 계산이 가능하다. 다시 말해서, opt2[l][i] = opt[i][i+l] 인 opt2로 바꿔서 쓴다면, opt2[l][…]를 계산하는 데는 opt2[l-1][…]만 있으면 되기 때문에, 슬라이딩 윈도우 방법으로 배열 두개만 갖고서 계산할 수 있다. 그리고 계산 순서를 생각해보면 아예 배열 하나만으로도 계산이 가능하다는 것을 알 수 있다. 그러면 코드는 이렇게 된다.
- ```
"""Knuth Optimization (Optimized)"""
dp = [[0] * size for _ in range(N + 1)]
opt = list(range(N))
for l in range(1, N):
    for i in range(N - l):
        j = i + l
        dp[i][j], opt[i] = min((dp[i][k] + dp[k + 1][j], k) 
                               for k in range(opt[i], opt[i + 1] + 1))
        dp[i][j] += C[i][j]
return dp[0][size - 1]
```

최적 이진 검색 트리

optimal binary search tree 참고
dp[i][j] = min(dp[i][k] + dp[k][j]) + sum(A[i], …, A[j]) 형태의 점화식으로 표현할 수 있다
sum(A[i], …, A[j]) 는 사각 부등식과 단조성을 만족하므로 크누스 최적화를 적용해서 O(n^2)으로 풀 수 있다
그러나, Garsia–Wachs algorithm을 사용하면 O(nlogn)에도 풀 수 있다.
- Garsia–Wachs algorithm의 동작 방식은 위키피디아를 참고하자.
- 이것을 O(n^2)에 구현하는 것은 그냥 리스트를 사용해서도 어렵지 않게 가능하다
  - x≤z 인 연속된 x,y,z들을 찾는 것은 그냥 앞에서부터 순회하면서 처리할 수 있다
  - 찾은 뒤에 x,y를 삭제하는 것은 그냥 O(n)의 delete 연산, x+y를 삽입할 위치를 찾는것도 O(n)의 선형 검색, 삽입을 하는 것도 O(n)의 insert 연산을 사용하면 된다.
  - 위키의 설명에서 좀 명확하지 못하게 쓰여 있던 부분은,
    - x+y를 삽입할 때, a[i]≥x+y 인 가장 큰 i를 찾고 나서 삽입을 하고 나면, …,a[i-1],a[i],x+y, … 이 될텐데, 이렇게 하고 나면 다시 a[i-1]≤x+y이 성립할 수가 있다. 그러면 다시 a[i-1]과 a[i]를 삭제하고 a[i-1]+a[i]를 그 앞에서 적합한 위치를 찾아서 삽입해야 한다. 재귀함수로 구현하는 것이 편하다
    - 또한 …,v,w,x,y,z,… 에서 x,y를 삭제하고 앞에다 x+y를 붙여서 …,x+y,…,v,w,z,..가 된 이후에 v≤z가 또 성립할 수 있다. 이 경우에는 또 v,w를 삭제하고 앞에 v+w를 삽입하는 것을 반복해줘야 한다.
  - 이렇게만 구현하더라도 DP에 크누스 최적화를 적용해서 구현한 것 보다는 같은 O(n^2)임에도 훨씬 빠르다.
- Garsia–Wachs algorithm 이 O(nlogn)에 동작하도록 구현하기 위해서는 위에서 O(n)으로 처리했던 작업들을 O(logn)에 처리할 수 있는 자료구조가 필요하다. 삽입할 위치를 찾는 작업의 경우는, 홀수번째 원소들에 대한 이분검색과 짝수번째 원소들에 대한 이분검색으로 나눠서 처리해야 하는데, 이것이 쉽게 안된다면 아예 홀수번째 원소들만 담는 컨테이너와 짝수번째 원소들만 담는 컨테이너 두개를 갖고 작업하도록 구현해야 한다. 이 경우에는 원소를 삽입하고 나면 그 위치 이후의 원소들은 홀짝이 바뀌기 때문에, 그 이후의 원소들을 다른쪽 컨테이너로 옮겨줘야 한다. 이렇게 하려면 삽입, 삭제, 이분검색 외에도 구간 스플릿, 구간 머지를 빠르게 지원하는 자료구조가 필요한데 여기에는 Splay Tree를 흔히 사용한다.

행렬 연쇄 곱셈

matrix chain multiplication 참고
dp[i][j] = min(dp[i][k] + dp[k][j]) + C[i]*C[j]*C[k] 형태의 점화식으로 표현할 수 있다
구간 분할 방식에 관한 DP의 대표적인 문제로 교과서에도 많이 등장한다. 보통 교과서에는 당연히 O(n^3) DP만을 가르친다.
하지만 이 문제는 Optimal polygon triangulation 문제로 바꿔서 생각해서 더 빠르게 풀수 있다
- Speed-up in Dynamic Programming 논문에는 O(n^2) 으로 푸는 방법이 소개되어있고,
- Hu and Shing의 알고리즘을 사용하면 O(nlogn)에 해결 가능하다
- 위키 페이지의 Talk 페이지에 설명된 Xiaodong Wang의 논문의 방법은 Hu and Shing의 알고리즘을 더 개선한 방법으로 O(nlogm)의 시간복잡도를 갖는다. (m은 인풋 시퀀스에서 local minimum의 갯수)

목차

구간 분할 방식에 관한 DP

구현

최적화

크누스 최적화

관련 문제

최적 이진 검색 트리

관련 문제

행렬 연쇄 곱셈

관련 문제