leomessi   1년 전

저는 일반적인 트리 순회로 풀었는데 혹시 DP를 적용한다면 어떤 식으로 풀게 되는건가요?

zenith82114   1년 전

$x$의 서브트리에서 $x$만 뉴스를 아는 시점부터 모두가 뉴스를 알기까지 걸리는 최소 시간을 $\mathsf{dp}(x)$라 두면, $x$의 직속 부하 $y_1, \cdots, y_k$에 대하여 $$\mathsf{dp}(x) = \max_{1 \le i \le k}\ \left( i + \mathsf{dp}(y_i) \right)$$입니다. 단, $\mathsf{dp}(y_1) \ge \cdots \ge \mathsf{dp}(y_k)$입니다.

leomessi   1년 전

@zenith82114

댓글 감사드립니다.

저도 말씀하신 바와 같이 문제를 정의하고 풀었습니다.

위와 같이 정의하였을 때 dp(x)는 x의 직속 상관에 의해 단 한 번만 계산되는 것 같은데요, 혹시 부분 문제가 중복되는 경우가 없어도 DP라고 부를 수 있는지 궁금합니다. 

zenith82114   1년 전

네. DP의 본질은 한 문제가 동형의 부분 문제들로 표현되는 구조 자체이며, 부분 문제 간 중복은 중요한 요소가 아닙니다. 트리에서의 DP가 중복이 없는 대표적인 경우이며, 부분 문제 중복을 해결하기 위해 쓰는 메모이제이션도 DP에서만 쓰이는 것이 아닙니다.

azruine   1년 전

부분 문제가 동형으로 표현되는건 DP의 특징보다는 오히려 분할 정복의 특징에 가깝지 않나요? 

dp라는 것 자체가 엄밀한 알고리즘이 아니라 패러다임이긴 하지만, 보통 dp라고 하면 중복되는 부분 문제를 한 번만 계산하고 그걸 여러 곳에서 활용해서 계산의 횟수를 줄이는 것에 초점을 맞춘다고 생각합니다.

이 문제에서는 dp(x)가 한 번만 계산이 되고, 그 계산 과정에서 1~k까지의 dp(y_i) 값을 전부 호출하니 dp의 중복되는 부분 문제를 한 번만 해결하기가 잘 먹힌다고 보입니다.

수정: 생각해보니 RGB 거리같은 예외가 있네요.

leomessi   1년 전

제가 DP에 대해 오해하고 있었네요. 알려주셔서 감사합니다.

zenith82114   1년 전

@azruine

DP를 정의함에 있어서 부분 문제끼리의 겹침을 반드시 요구한다면 "트리 DP"라는 표현을 어떻게 받아들일지 고민이 필요할 것 같습니다. 트리의 정의상 서브트리들은 교집합이 없고, 많은 경우에 각 노드의 상태값은 부모 노드에서만 사용되니까요. 아마도 그냥 DFS나 위상 정렬의 일종으로 불러야 하겠죠. 그것도 일리 있는 견해라고 생각합니다.

그런데 저는 DP 문제를 풀면서 어떻게 하면 부분 문제들이 서로 겹칠까를 의식해본 적이 한 번도 없습니다. 어떻게 상태를 정의해야 모든 가능성을 "빈틈" 없이 커버하면서 상태 개수와 상태 전이 횟수가(=공간/시간 복잡도) 제한 내에 들어올지에만 집중하는 편이고, 보통 그걸로 충분해요. 그래서 DP 중에는 트리 DP가 상태 정의가 정직해서 제일 쉽게 느꼈는데, solved.ac 기준으로는 실버~골드 DP 중 상위권(골드2~1)에 있는 걸 보면 제가 특이한 케이스일지도 모르겠습니다. 아무튼 DP가 naive에 비해 계산을 줄이기 위함임은 틀림없으니, 그 감소가 어떤 원리에서 오는지는 각자 본인에게 자연스럽게 와닿는 설명을 탐구해도 좋을 듯합니다.

분할 정복을 언급해 주셨는데 저는 사실 분할 정복도 DP의 일종으로 봅니다. 문제 풀다 보면 하는 관찰도 비슷하고 비슷한 스텝들을 밟게 되더라고요. 방문하는 상태들이 sparse하고 부분 문제들을 잘 합치는 데에 방점이 찍힌 탑다운 DP의 한 유형 정도로 생각하고 있습니다.

댓글을 작성하려면 로그인해야 합니다.