링크: https://www.acmicpc.net/problem/15480문제문제 설명은 간단하다.루트를 r로 하는 트리에서 u와 v의 최소공통조상(LCA)를 출력하는 문제이다. LCA(r, u), LCA(r, v), LCA(u, v) 세 개 중에서 깊이가 더 깊은 노드를 출력하면 된다.증명은 사실 안 했는데, 케이스 몇 개를 두고 해보니까 계속 답이었다..혹시나 싶어서 제출해봤더니 정답코드

제목 그대로, 트리의 노드 순서를 다시 정리하여 구간으로 표현하는 것이다. 그림으로 보면, 트리의 구조와 왼쪽과 같았다면, 각 트리의 번호를 오른쪽처럼 변경하는 것이다. 순서는 전위순회(pre-order)로 탐색하면서 번호를 붙이면 된다. 이게 왜 필요할까? 제목에서 이미 말한거지만, 구간으로 표현하는 것이 더 용이할 때 사용한다. 특히 트리를 세그먼트 트리나 펜윅 트리 등의 구간합/부분합으로 변형하여 문제 해결이 필요한 경우이다. 노드의 번호를 위처럼 정리하면, 각 노드가 포괄하는 노드는 항상 확실하다. "자신의 번호 + 그 노드의 서브 트리(들)의 크기"가 포함할 수 있는 자식의 마지막 번호와 같다. 그럼 트리를 일렬로 펴서 다룰 수 있다. 코드 관련 문제 (+스포일러)BOJ 2820 - 자동차 공장..

링크: https://www.acmicpc.net/problem/16964풀이문제의 가장 큰 힌트는 입력된 그래프의 모양이 트리라는 점이다. 즉, 사이클이 없다. 올바른 DFS 방문 순서가 되기 위해서는 자식이 부모보다 먼저 나오는 경우가 있어서는 안된다.이 특징을 살리면, 어떤 순서 \(i\)번째에 등장하는 노드 \(x\)의 깊이는 어떤 순서 \(i\)+\(x\)의 서브트리의 크기까지는 전부 그 노드의 자식이라는 점이다. 위 그림처럼 입력이 주어졌다고 해보자.여러 DFS 방문 순서가 가능하겠지만, 그 중 하나인 [1, 3, 5, 8, 6, 4, 7, 9, 2]의 순서를 예로 들자면 어떤 \(i\)번째 순서에 있는 노드 \(x\)는 자신의 서브트리의 크기만큼 다음 순서가 자신의 형제 노드이다.2번째 순서..

링크: https://www.acmicpc.net/problem/1613이전 풀이: http://joonas-yoon.blogspot.com/2016/04/1613.html문제알고 있는 사건의 전후 관계를 방향성이 있는 간선으로 보면, 서로 다른 두 사건을 유추한다는 것은 어떤 방향으로건 일단 연결이 되어있는가를 물어보는 것이다. 방향 그래프에서 정점 a에서 b로 갈 수 있는 경로가 있는 지 물어보는 문제이다. a에서 b로 가는 경로가 있으면 앞에 있는 사건이 먼저 일어난 것이므로 -1b에서 a로 가는 경로가 있다면 1, 경로가 없다면 0을 출력하면 된다. 문제는 이러한 물음이 한두번이 아니라 s번(최대 50,000번) 물어보기 때문에, 경로를 빠르게 찾을 수 있어야한다. n이 400으로 작으므로 플로이..

링크: https://www.acmicpc.net/problem/3075 문제p개의 은하가 있을 때, n명과 교통비의 합이 최소가 되는 어떤 하나의 은하(미팅 장소)를 찾는 문제이다. 조심할 것조건이 특별히 안 적혀있어서 조심해야 할 게 많은 문제였다. 주의해야 할 조건으로는1. 하나의 은하에 여러 사람이 있을 수 있고2. 은하와 은하 사이에는 여러 개의 길이 존재할 수 있다(doju님의 데이터 추가 글) 나는 외딴 섬에 대한 케이스를 처리 못해서 틀렸었다. 풀이미팅 장소가 될 은하를 하나 잡고, 그 은하로부터 나머지 사람들과의 거리의 합을 구한다. 이 때, 거리의 합이 최소가 되는 은하가 정답이다. 은하의 개수 \(p \lt 100\) 로 작은 크기이기 때문에, 플로이드-와샬 알고리즘으로 구현하면 간단..