DAC(분할 정복)과 비교해보는 DP(동적 계획)

DAC는 작은 문제로 쪼갰을 때 그것들이 서로 관계가 없을 때 쉽게 쓸 수 있다.

위상적으로(그래프) 접근하자면, 작은 문제라는 점들 사이에 연결 관계가 없고, 작은 문제와 큰 문제 사이의 연결 관계(규칙)가 한눈에 보일 때 쓸 수 있다.

2630 색종이 만들기(https://www.acmicpc.net/problem/2630)를 예로 들자면

전체 색종이를 넷으로 잘랐을 때, 1사분면이 덩어리든 섞였든 2사분면의 결과와는 전혀 상관이 없다.

그리고 큰 문제가 안풀릴때 작은 문제 넷으로 나눈다는 명확한 규칙이 보인다.

이렇게 문제를 서로 독립적인 부분 문제들로 쉽게 분리가 가능할 때 DAC를 사용한다.

 

반면 DP는 작은 문제로 쪼갰을 때에도 그것들이 서로 관계가 있을 때 쓴다.

위상적으로 접근하자면, 작은 문제라는 점들 사이에 외방향 연결 관계가 있을 때 쓸 수 있다.

(이는 A를 안다면 B를 알 수 있게 되고, B를 안다면 C를 알 수 있게 되는 그런 상황을 말한다.)

그리고 그 '관계'는 보통 애매해서, 그 규칙성(점화식)을 명확히 찾는데에서부터 풀이가 시작된다.

규칙성을 발견하고, 자명하게 해를 구할 수 있는(= degree가 0인) 한두개의 부분문제의 답부터 구한 뒤

그와 연결된 다른 부분문제의 답을 구하는 방식으로 전체 문제를 해결한다.

 

DAC와 DP는 서로 다른 배타적인 개념이라기보다는, 같은 일을 하는데 포커스를 어디에 두냐의 차이인 것 같다.

작은 문제로부터 큰 문제로 넘어가는 관계가 단순명확해서 각각의 작은 문제를 해결하고 합치는 함수의 구현에 포커스를 맞춘다면 DAC의 관점에서 봐야 할 것이다.

반대로 작은 문제로부터 큰 문제로 넘어가는 관계가 모호해서 그것을 확실히 결정하는 (= 점화식을 구하는) 것에 포커스를 맞춰야 한다면 DP의 관점에서 본다고 할 수 있다.

DAC는 말 그대로 "분할 정복"이라는 거대한 개념이기 때문에, DP도 일종의 DAC라고 볼 수도 있다.

 

3주차까지 다 배우고 나니까 DP가 그래프와 위상정렬까지 배운 다음에야 커리큘럼에 들어가는 이유를 알 것 같다.

주먹구구식으로 점화식 구해서 풀면 다변수 점화식은 못풀었을 것 같다.

DFS BFS가 어떻게 돌아가는지도 알고 2차원 행렬 그래프도 좀 다루고 한 경험 덕에 이제 dp의 메모 테이블이 2차원 3차원이 돼도 머리가 버티는게 아닐까