PS와 개발을 공부하자

http://boj.kr/14657 문제에서 주어진 세개의 조건을 통해 N개의 문제들은 트리를 이루고 있다는 것을 알 수가 있다. 그럼 가장 많은 문제를 풀기 위해서는 트리에서의 가장 긴 단순 경로를 찾으면 되며, 트리에서의 가장 긴 단순 경로는 바로 트리의 지름이 되기 때문에 트리의 모든 지름 중에 경로상에 포함된 에지들의 가중치합이 최소가 되는 지름을 찾는 문제로 볼 수가 있게된다. 트리의 모든 지름을 체크하기 위해 우선 트리의 중심을 찾고 그..

https://community.topcoder.com/stat?c=problem_statement&pm=11308 풀이를 떠올린 속도는 나쁘지는 않았는데 cache 의 초기값을 -inf 로 안주고 0으로 줬다가 디버깅하느라 시간이 좀 걸렸다.트리의 간선의 수 N이 정해지면 모든 노드들의 degree 의 합도 2N 으로정해지기 때문에 노드 수와 degree의 합이 N+1과 2N이 되게 하는 모든 degree의 조합의 최대 점수를 dp로 계산하..

LCA(A, C) = C, LCA(B, C) = LCA(A, B) or LCA(B, C) = C, LCA(A, C) = LCA(A, B)가 참이면 존재하는거임

이 문제는 흔히 가로외 세로의 길이가 같은 격자판에서 각 칸이검은색 또는 흰색으로 이루어져 있을때 자식이 4개이거나 0개인트리로 격자를 표현하는 '쿼드 트리' 라는 개념의 변형 문제이다.격자가 주어졌을때 이 격자를 가장작은 정사각형모양으로 키우고새로생긴 격자를 흰색으로 채운 뒤쿼드트리의 노드의 개수를 구하는 것이 첫번째 요구되어지는 것이고그다음엔 압축된 쿼드트리의 노드 수를 구해야 하는데압축을 하는 방법은 공통된 서브 트리들을 딱 하나만남겨서 공유하..

이 문제는 M개의 트리가 주어지고 각각의 트리에 대해 하나의 엣지를 선택하여오른쪽 트리에게 주었을때(마지막 트리는 맨 처음 트리에게 준다.) 각 M개의 트리가 여전히 모두 트리가 되도록 간선을 선택하는모든 경우의 수를 계산하는 문제이다. 우선 이 문제는 dp 로  풀 수가있다. 그래서 내가 처음 생각해낸 풀이는dp[i][u][v] : i-1번째 트리에서 엣지 u-v 를 선택했고 i번째 트리부터 엣지들을 잘 선택했을때 M개의..

http://codeforces.com/contest/681/problem/D간단하게 문제를 설명하자면, N개의 사람이있고 M개의 연결관계가 주어진다그리고 하나의 컴포넌트는 트리구조를 이룬다. (여러개의 컴포넌트로 이루어질 수도 있음)N명의 사람들 각각은 선물을 주고 싶은 사람이 한사람 씩 있는데 이 한 사람은 무조건 자기 자신이거나 자신의 조상이어야 한다. 또, 우리는 어떤 list를 작성해야하는데각 N명의 사람들은 list의 맨왼쪽에 있..

사실 원래의 풀이와 아주 큰 차이는 없다. 두번의 dfs를 돌리는 것까지는 똑같지만 변수가 하나 줄었고, 점화식이 좀 더 단순해 졌다.우선 size(i) 는 i를 루트로 갖는 서브트리의 총 노드수라고 보면노드 i 부터 자손들까지의 거리의 총합 S(i)는,노드 i의 자식이 c1, c2, c3..... cn 이고, ck 와 연결된 간선의 가중치는 wk 일때size(c1)*w1 + size(c2)*w2 +....+size(cn)*wn +S(c1) + S(..

우선 이 문제를 풀기 위해서 한가지 선행 지식이 필요하다. N개의 노드를 가진 트리에서 모든 정점 쌍의 거리의 합을 O(N)에 구할 수가 있는데 size(i) = i번 노드를 루트로 갖는 서브트리의 노드의 수. 로 정의하여 재귀적으로 모든 노드에 대해 구하면서 각 간선을 지나는 경로의 수를 dfs로 구하는것이다. 이 전, 전 포스트에 설명이 되어있다.하지만 이 문제는 점프 거리 k 라는 입력이 주어져서 한번에 k개의 간선을 뛰어넘을 수가 있..

이 문제는 N개의 노드를 가지고 간선에 가중치가 있는 트리에서 중앙 정점이라는 것을 찾아서 이 중앙 정점에서 다른 정점까지의 모든 거리의 합을 구하는 문제이다.중앙 정점의 정의는 어떤 한 점에서 다른 모든 정점까지의 거리의 합이 최소가 되는 점이다. 처음에 트리의 중심과 헷갈려서 트리의 중심으로 풀 뻔 했는데 잘 생각해 보면 트리의 중심은 어떤 한 점에서 다른 모든 정점까지의 거리의 최대값이 최소가 되는 점이기 때문에 확실히 다른 개념이다.그렇다면 ..

naive 하게 모든 노드쌍간의 거리의 총합을 구한다고 하면 총 N개의 노드에 대해 DFS 혹은 BFS를 돌려서 O(N^2) 에 구하는 것이지만 N이 좀더 커지만 사용할 수가 없다.이 때 발상을 조금 전환해서 모든 가능한 경로상에 각각의 간선이 총 몇번이나 포함되는지를 세어주면 이 것의 총합이 우리가 구하고자 하는 답이 될 것이다.그렇다면 트리에서 루트 노드를 제외한 다른 모든 노드들은 하나의 부모가 있으므로 부모와 연결된 간선을 하나씩 가질 것이므..