트리 (5) 썸네일형 리스트형 [Python] 15681번 트리와 쿼리 https://www.acmicpc.net/problem/15681 24/03/29 트리 DP를 연습할 수 있는 아주 좋은 문제다. 이전에 해결했던 문제를 복습하는 겸, 글로 작성해본다. 문제 접근 방식: 나이브하게 각 쿼리마다 위의 값을 일일히 구해서 내보내려고 한다면, 최악의 경우 $\mathcal{O}(QN)$이 소요된다. 각 쿼리마다 DFS를 한 번 진행할 것이고, 트리에서의 DFS는 $\mathcal{O}(N)$의 시간 복잡도가 소요되기 때문이다. 따라서, 한 번의 DFS를 진행하여, 그 결과를 저장해야한다. 즉, DP를 진행하는데, DFS를 진행하며 DP를 진행하면 된다. 탑다운 DP의 구현 방식과 비슷한데, 트리 DP는 서브 트리 별로 문제를 분할하는 것이 핵심이다. DP 점화식을 다음.. [Python] 26260번 이가 빠진 이진 트리 https://www.acmicpc.net/problem/26260 26260번: 이가 빠진 이진 트리 김소마는 최근에 포화 이진 트리에 대해 배웠다. 포화 이진 트리란, 이진 트리에서 리프 노드를 제외한 모든 노드가 두 자식 노드를 가지며, 모든 리프 노드가 채워진 것을 말한다. 아래의 그림 www.acmicpc.net 24/02/16 업다운 랜디를 하다가 만난 문제로, 처음 보고 뇌 정지가 와서 잘 해결하지 못했던 문제다. 이후 다시 풀게 되었고, 생각보다 간단한 해결 방법이 있어 글을 쓴다. 문제 접근 방식: 문제의 요구 조건은, 포화 이진 트리이면서 이진 검색 트리인 트리가 주어졌을 때, 특정 부분을 제거하고 다시 새롭게 썼을 때 바뀌는 트리의 후위 순회 결과를 출력하는 것이다. 처음에 보고 정석.. [Python] 8286번 Road Network 2 https://www.acmicpc.net/problem/8286 8286번: Road Network 2 If no road network plan satisfying the conditions from the input exists, the first and only line of output should contain a single word BRAK - i.e., none in Polish. In the opposite case each of the lines in the output should contain a description of one bi www.acmicpc.net 23/09/23 차수열(Degree Sequence)의 개념을 익힐 수 있는 문제다. 여담으로 대회 개최를 준비하던 중.. [Python] 24230번 트리 색칠하기 https://www.acmicpc.net/problem/24230 24230번: 트리 색칠하기 정점이 $N$개인 트리가 있다. 정점에는 1부터 $N$까지 번호가 붙어있다. 트리의 루트는 항상 1번 정점이며 맨 처음에는 모든 정점이 하얀색으로 칠해져 있는 상태이다. 하나의 정점에 색칠하면 해 www.acmicpc.net 23/05/29 골드 5 짜리 문제 치고는 아이디어가 매우 좋았던 문제이다. 문제 접근 방식: 문제 정보를 보면, 트리가 주어져 있는데 각 노드별로 색깔 정보가 주어진다고 했다. 한 노드를 색칠하면, 그 노드를 포함한 서브트리는 모두 같은 색으로 색칠된다고 한다. 이때, 모든 정점을 원하는 색으로 칠하고자 할 때 구하는 최소 색칠 횟수를 구하는 것이 우리의 목적이다. 맨 처음 떠올렸던 방.. [Python] 18126번 너구리 구구 https://www.acmicpc.net/problem/18126 18126번: 너구리 구구 텔레토비 동산에 사는 너구리 구구는 입구, 거실, 주방, 안방, 공부방, 운동실, 음악실, 음식 창고 등 N개의 방을 가지고 있다. 입구를 포함한 모든 방은 1부터 N까지의 번호가 있고, 입구는 1번이 www.acmicpc.net 22/09/19 그룹원들과 푼 그룹 주간 문제로 이 문제를 선택해서 풀었다. 오랜만에 DFS문제, 그것도 일반적인 matrix모양으로 간선이 주어지는 것이 아닌 실제 간선 모양으로 주어지는 그래프라서 조금 헷갈리긴 했지만 더듬더듬 기억을 되살려 가며 주석을 달아가며 작성했던 문제이다. 문제 접근 방식: 처음에는 이 문제를 재귀 오류로 틀렸었다. (재귀 제한 코드를 실수로 적지 못했다... 이전 1 다음
