1135번 - 뉴스 전하기
댓글 감사드립니다.
저도 말씀하신 바와 같이 문제를 정의하고 풀었습니다.
위와 같이 정의하였을 때 dp(x)는 x의 직속 상관에 의해 단 한 번만 계산되는 것 같은데요, 혹시 부분 문제가 중복되는 경우가 없어도 DP라고 부를 수 있는지 궁금합니다.
부분 문제가 동형으로 표현되는건 DP의 특징보다는 오히려 분할 정복의 특징에 가깝지 않나요?
dp라는 것 자체가 엄밀한 알고리즘이 아니라 패러다임이긴 하지만, 보통 dp라고 하면 중복되는 부분 문제를 한 번만 계산하고 그걸 여러 곳에서 활용해서 계산의 횟수를 줄이는 것에 초점을 맞춘다고 생각합니다.
이 문제에서는 dp(x)가 한 번만 계산이 되고, 그 계산 과정에서 1~k까지의 dp(y_i) 값을 전부 호출하니 dp의 중복되는 부분 문제를 한 번만 해결하기가 잘 먹힌다고 보입니다.
수정: 생각해보니 RGB 거리같은 예외가 있네요.
DP를 정의함에 있어서 부분 문제끼리의 겹침을 반드시 요구한다면 "트리 DP"라는 표현을 어떻게 받아들일지 고민이 필요할 것 같습니다. 트리의 정의상 서브트리들은 교집합이 없고, 많은 경우에 각 노드의 상태값은 부모 노드에서만 사용되니까요. 아마도 그냥 DFS나 위상 정렬의 일종으로 불러야 하겠죠. 그것도 일리 있는 견해라고 생각합니다.
그런데 저는 DP 문제를 풀면서 어떻게 하면 부분 문제들이 서로 겹칠까를 의식해본 적이 한 번도 없습니다. 어떻게 상태를 정의해야 모든 가능성을 "빈틈" 없이 커버하면서 상태 개수와 상태 전이 횟수가(=공간/시간 복잡도) 제한 내에 들어올지에만 집중하는 편이고, 보통 그걸로 충분해요. 그래서 DP 중에는 트리 DP가 상태 정의가 정직해서 제일 쉽게 느꼈는데, solved.ac 기준으로는 실버~골드 DP 중 상위권(골드2~1)에 있는 걸 보면 제가 특이한 케이스일지도 모르겠습니다. 아무튼 DP가 naive에 비해 계산을 줄이기 위함임은 틀림없으니, 그 감소가 어떤 원리에서 오는지는 각자 본인에게 자연스럽게 와닿는 설명을 탐구해도 좋을 듯합니다.
분할 정복을 언급해 주셨는데 저는 사실 분할 정복도 DP의 일종으로 봅니다. 문제 풀다 보면 하는 관찰도 비슷하고 비슷한 스텝들을 밟게 되더라고요. 방문하는 상태들이 sparse하고 부분 문제들을 잘 합치는 데에 방점이 찍힌 탑다운 DP의 한 유형 정도로 생각하고 있습니다.
댓글을 작성하려면 로그인해야 합니다.
leomessi 1년 전
저는 일반적인 트리 순회로 풀었는데 혹시 DP를 적용한다면 어떤 식으로 풀게 되는건가요?