DP개념정리

문제의 크기

DP(정확히는 recurrence겠지만)를 이야기할때, 큰 문제를 작은 부분문제들로 분할하여 풀고 합친다는 개념이 나온다. 관련 문제들을 풀다보면 어느정도 느낌은 알겠지만, 도대체 문제들의 크고 작음이란 무엇이란 말인가? 1차원 DP면 f(n)의 n값이 크기일까? 그것도 점화식에 따라 다를 것이다. 일단 넘어가서 2차원, n차원 DP의 순서라는것은 각 인자의 사전순 순서가 맞는지도 의문이다. 점화식의 인자의 순서를 바꿔도 위상순서는 같지 않은가?

내가 찾은 답은 다음과 같다. 점화식의 의존성그래프의 Partial Ordering이 문제들의 순서가 된다!

TopDown과 BottomUp에 대하여

DP를 푸는데 있어 크게 2가지로 분류하는데, 하나는 TD(TopDown)방식이고, 나머지 하나는 BU(BottomUp)방식이다. 이 두가지에 대해 명확한 설명이 되어있는 글을 본적이 없기 때문에, 이번기회에 다루어보려 한다.

  1. Top Down
  2. TopDown은 제일 큰 문제에서 시작하여, 현재의 문제를 풀기 위해 필요한 더 작은 문제들을 찾아 내려간 후, 맨 아래서 다시 올라오면서 계산한다. (아래로 내려가는 부분이 Topological Sorting, 다시 위로 올라오는 부분이 실제 계산이다.) 물론 Partial Ordering이기 때문에 '제일 큰 문제'나 '제일 작은 문제'같은건 잘 정의되지 않는다. 그 대신 자신보다 더 큰 문제가 없는 극대점, 자신보다 더 작은 문제가 없는 극소점은 정의할 수 있다. (여러개 존재할 수 있으며, 유일하면 최대/최소가 된다.) 극대점들(=시작할 지점)은 우리가 최종적으로 구해야 하는 값들이고, 극소점은 더이상 분해할 수 없으며 빠르게 계산가능한 base case가 된다.

  3. Bottom Up
  4. BottomUp은 제일 작은문제(엄밀하게는, 극소점)들에서 시작하여 그냥 위로 올라오며 계산하는 방법이다.

NOTE: TD와 BU는 문제를 계산하는 순서에 따라 구분되는것이 아니다. 어떤 방식이던 계산은 극소점부터 진행해서 극대점으로 마무리 되어야 한다. 이때, 극소점과 극대점은 유일하지 않기 때문에 가능한 계산순서는 다양하다. 그렇다면 둘은 어떠한 차이점이 있는가?

재귀로 구현하면 TD, 반복문으로 구현하면 BU라는 말도 들리는데, 주로 그렇게 구현하는건 맞지만 엄밀하게는 둘을 구분할 기준이 될 수 없다. 재귀를 스택+반복문으로, 반복문을 재귀로 상호변환이 가능하기 때문이다.

처음 시작을 극대점으로 해서 TS(Topological Sorting, 재귀함수로 점화식을 구현하면 된다)을 통해 계산순서를 자동적으로 결정한 다음, 그 순서대로 거꾸로 올라가며 계산하는것이 TD

TS없이, 처음부터 극소점에서 시작하여 계산하는 것이 BU

즉, TS의 유무가 TD와 BU의 차이를 만든다고 할 수 있다.

TS는 있으면 뭐가 좋은가? BU에는 TS과정이 없기 때문에, 프로그래머가 직접 계산순서를 잘 지정해서 topological order를 지켜서 계산하도록 짜야한다. 그래서 코딩할때 TD보다 신경쓸게 많다는 단점이 있다. 그렇지만 TS과정이 없기 때문에, TD와는 달리 재귀로 구현할 필요가 없어서 오버헤드가 적다는 장점도 존재한다. 또한, 의존성그래프의 정점(=상태개수)이 v, 간선이 e개일 경우 TS의 시간복잡도는 O(v+e)가 되는데, Dense Graph일 경우 O(v^2)이 되는걸 (적어도 나는) 피할 수가 없다. BU의 경우 TS가 없기 때문에, 의존하는 작은문제들 값으로 현재문제의 값을 빠르게 구할 방법 (ex:연속된 작은문제들의 합을 Segment Tree, Prefix Sum, Sliding Window등으로 빠르게 구하기)이 존재한다면 O(v^2)보다 낮은 복잡도로 문제를 해결할 수 있다. 공간복잡도도 마찬가지로 더 줄일 수 있다.

TD는 코딩이 편하지만 재귀 오버헤드가 좀 있고, 어떤 경우에는 시간복잡도 면에서도 불리할 수 있다. BU는 코딩할때 조심해줄 부분이 많지만, 오버헤드가 작고 (TS가 없음으로 인해)시간복잡도적인 측면에서도 유리할 수 있다. 이정도로 정리할 수 있을듯

DP접근법 체크리스트

  1. 시간복잡도는 잠시 잊어버리고, 굉장히 나이브한 완전탐색 점화식을 짠다.(문제의 재귀적 분해)(사실 이거부터도 모호하고 어렵다)
  2. 이제 완전탐색 점화식에서 필요없는 인자(다른매개변수들로부터 추출이 가능하다던가, 그리디한 어떤 성질에 의해 안보고도 다음인자값을 계산할수 있다던가)를 가능한 많이 제거한다.
  3. 인자를 다른방식으로 표현(값 대신 인덱스를 저장한다던가)할수 있는지, 그렇다면 어떤게 더 효율적인지 판단하고 적용한다. "BOJ2618 경찰차" 문제가 이런 느낌. 결과값이 bool인 dp는 결과값에 인자정보를 대신 추가해서 최적화할 여지가 있다. (BOJ1114 실행빠른코드들, 노란책 이상한 냅색dp도 비슷했던듯, KOI2019검은돌 dp도 구사과블로그에서 이런최적화를 했으니 읽어보자 보통 인자에 단조성?연속성?이 있어서 최대최소만 알아도 될때 가능한건가? 나중에 formal하게 정리해보자. 점화식을 한번 비틀기(15773은 [x,n)풍선남았고 현재 y고도일때 터트리기최대개수z를 묻는데, f(x,y)=z로 두면 최적화가 거의 힘들고, [0,x]풍선으로 z개터트릴때 최소고도y로 약간 비틀어서 f(x,z)=y로 정의하면 점화식이 더 예쁘게 나와서 풀 수 있다. 점화식 결과값 정의는 상당히 중요한거같다))
  4. 바텀업으로 짤때 시간복잡도를 개선(위상순서대로 계산값을 전이시킬때 효율적이라거나)할 수 있는지 생각해보기.
  5. 대충만 적었던 점화식을 기저조건을 포함해서 꼼꼼하게 적고, 답은 어떤형태인지(ans=dp[n], ans=dp[0]+...+dp[n] 등)도 적는다.
  6. 알려진 dp최적화를 적용할수 있는 형태인가?(인자 하나만 자유도를 줄때 값이 볼록->slope trick, 이전인덱스들의 일차함수형태 min->cht, Monge(submodular)Cost->Div&ConqDP 등)
  7. 시간복잡도가 충분히 작아졌다면 코딩. 아니면 다시 2번으로 돌아가서 반복

2,3,6은 상태표현의 최적화 4,6은 상태전이의 최적화라고 부르는듯

home