이 블로그의 "트리에 관하여" 시리즈의 첫 번째 카테고리, ❮Tree DP❯에서 다루는 첫 번째 주제이다. 이 테크닉은 다른 이름으로도 알려져 있다. KOI에 출제된 어떤 유명한 문제의 이름을 딴 것인데, 스포일러가 될 수 있으므로 연습 문제 목차에서 후술 하겠다. Square-order tree DP? 사실 이건 그 자체로 뭔가 해야 하는 테크닉은 아니다. 트리 DP 점화식이 2차원으로 나오고, 전이 과정을 합쳐서 대충 보기에는 $O(n^3)$의 시간 복잡도를 가져야 할 것으로 보이는 후술 할 조건을 만족하는 알고리즘이 사실 $O(n^2)$이라는 더 좋은 시간 복잡도를 갖는다는 사실을 이용하는 테크닉이다. 만족해야 하는 조건은 구한 점화식 $\text{dp}(x,y)$에 대해, $x$가 각 노드를 뜻하..

문제 링크 재밌는 트리 DP 문제였다. 편의상 각 사원 $i$의 실력을 $V_i$, 부모를 $P_i$라고 하자. Subtask: $V_i > 0$ (17점) 더보기 그냥 최대한 많이 포함하면 이득이다. 그런데, 한 팀의 팀장을 전체 트리의 루트로 잡아버리면 다른 팀이 만들어질 수 없다. 또한, 루트의 $k$대 독자 후손 노드도 잡아버리면 다른 팀이 만들어질 수 없다. 따라서 1번 노드에서부터 DFS를 돌리다가 처음으로 자식 노드가 2개 이상이 된다면 가장 큰 2개만 골라주면 된다. 필자의 코드이다. Subtask: $N\le 5\ 000,\ P_i=i-1$ (12점) 더보기 직선형 그래프에서 문제를 풀면 된다. Kadane 알고리즘과 꽤 비슷하다. 각 노드 $i$마다 $\sum_{i\le k\le j}V..

밥 먹기 문제 링크 7577번: 탐사의 마이너 버전이라고 할 수 있다. 필자는 '탐사'를 자력으로 못 풀었지만, 어쨌든 '탐사'에 사용되는 방법을 배워서 이 문제를 수월하게 풀 수 있었다. 어쩌면 '밥 먹기'를 푼 뒤 '탐사'를 시도하면 풀 수 있을 것 같기도 하다. 풀이 더보기 상당히 어려운 문제이고, 아이디어성 문제이다. 문제에서 요구하는 것을 간단하게 바꾸면 '연립 부등식의 해를 결정해라' 정도의 얘기가 된다. 완전한 결정을 의미하는 것은 아니지만 아무튼. 신기하게도 떨어지는 거리의 범위가 큰 것이 문제의 힌트가 된다. '탐사'의 경우는 범위가 적어서 오히려 접근이 어려웠다. 따라서 DP의 가능성은 적다. $1\cdots N$을 쭉 나열하고 범위를 표시하면서 파악하면 감을 잡기 쉽다. $D_1$을 ..

트리의 지름을 구하는 방법은 다음의 몇 가지가 있다. 동적 계획법을 이용하는 방법 트리 순회를 2번 이용하는 방법 동적 계획법을 통해 지름을 구하는 과정은 상당히 직관적이고 쉽다. 하지만 구현이 조금 힘들 수 있다. 그래서 대부분의 사람들은 이보다 단순한 트리 순회 알고리즘을 이용한다. 그런데 이것은 생각보다 이해하기가 어렵다. 게다가 가중치 트리에 대해서도 이 방법이 통하는데 이것까지 아울러서 이해하려면 상당히 힘들다. 그래서 나는 이를 이해하기 위해 트리를 독특한 방식으로 재배치하였다. 동그랗게 생겼으면서 색이 칠해진 것들이 트리의 노드이고, 실선들이 엣지이다. 하얀색 동그라미는 열린 구간임을 나타내는 표시이다. (물론 트리의 지름이 유일하지 않은 경우 하얀색 동그라미 자리에 지름의 한 끝점이 위치할..