[코드트리 챌린지] 7주차

---

실력진단 결과

코드트리 7주차 실력진단 결과

---

오늘의 학습

Tree DP

각 정점에 값이 적혀있는 트리 정보가 아래와 같이 주어졌을 때, 각각의 노드마다 자신을 포함하여 자손 노드들에 적혀있는 수들의 합을 구해보려고 합니다.

위 그림에서 예를 들어 6번 노드의 경우 자신을 포함한 자손 노드 번호가 6, 2, 3, 5 이므로 각 노드에 적혀있는 수들의 합인 2 + 3 + 3 + 4 = 12가 나와야 합니다. 즉, 우리가 얻고 싶은 결과는 아래와 같습니다.

이를 각 노드를 정한 뒤 해당 노드에서 자식 노드로 움직이는 것을 재귀적으로 반복하는 탐색을 진행하는 완전탐색 방법을 통해 구현한다면, 각 노드를 정하는데 O(N), 각 노드마다 최대 확인해야 하는 노드 수가 O(N)이 되어 총 O(N^2)의 시간복잡도를 갖게 됩니다.

이는 DP를 활용하여 O(N)의 시간복잡도로 만들 수 있습니다. 아직 동적계획법에 대해 잘 모르신다면 DP 유형을 공부하시고 나서 다시 이 설명을 읽는 것을 추천드립니다.

DP[i] : i번 노드를 루트로 하는 서브 트리에 있는 노드에 적힌 수들의 합으로 정의했을 때, 각 DP값은 문제에서 원하는 그 값이 됩니다. i번 노드의 자식 번호를 c 1​ ,c 2​ ,...,c k​ 라 했을 때, 다음 점화식을 만족하게 됩니다. 정의상 모든 자식의 DP값에 현재 노드에 적혀있는 수인 A[i]를 더하면 서브 트리에 있는 노드에 적힌 모든 수의 합이 구해지기 때문입니다.

DP[i] = DP[c1​]+DP[c2] + ... +DP[ck] + A[i]

DP는 큰 문제를 풀기 위해 이미 풀려있는 작은 문제의 답을 이용하는 방식이기에, DP[i]값을 구하기 위해서는 미리 자식들에 해당하는 DP값이 구해져 있어야만 합니다.

이는 DFS를 통한 트리 탐색과 함께 쉽게 구현이 가능합니다. 트리에서의 DFS는 깊이우선탐색 특성상 모든 자손을 방문한 이후에 다시 현재 노드의 위치로 되돌아오게 됩니다. 이를 이용하면 됩니다. 아래와 같이 현재 노드 x를 기준으로 먼저 DFS 탐색을 전부 진행한 뒤, 퇴각하기 직전에 DP 값을 갱신해주는 식으로 값을 계산해주면 됩니다.

 

 

이 과정을 코드와 함께 보면 다음과 같습니다.