트리 (15) 썸네일형 리스트형 [백준 / BOJ] 20924 트리의 기둥과 가지 문제 출처 : https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에 세 개의 정수 $a$, $b$, $d$($1 \le a, b \le N$, $ a \ne b$)가 주어진다. 이는 $a$번 www.acmicpc.net N개의 노드와 N-1개의 간선으로 이루어진 트리가 있다. 이 트리의 루트를 타고 이동하다가, 처음으로 2개 이상의 노드가 연결된 노드가 발견될 경우, 이를 기가 노드라고 하며, 이전 경로를 기둥경로 라고 한다. 기가 노드에서시작해서 기둥 경로를 제외하고, 리프노드까지의 .. [백준 / BOJ] 15591 MooTube (Silver) 문제 출처 : https://www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 농부 존은 MooTube라는 동영상 공유 서비스를 만들었다. MooTube의 동영상들은 트리구조로 연결되어있고, 동영상 Vi를 볼때, Vi와 연결된 모든 동영상들중에 유사도가 Ki이상인 동영상들을 추천해준다. 이때, 동영상 Vi와 다른 동영상 Vj의 유사도는 Vi와 Vj 를 연결하는 경로의 최소 유사도이다. 소가 Vi동영상을 시청하.. [백준 / BOJ] 1135 뉴스 전하기 문제 출처 : https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 민식이는 회사의 매니저이다. 민식이는 회사의 뉴스를 모든 직원들에게 전하려고한다. 회사의 모든 직원들은 정확히 한명의 선임이 있으며, 자신은 자신의 선임이 아니다. 모든 직원들은 모두 민식이의 간접,직접적인 부하이다. 모든 사람은 자신의 직속부하에게만 뉴스를 전달할수있고, 이때, 1분의 시간이 걸린다. 모든 직원이 뉴스를 전달받는 최소시간을 구하는 문제다. 풀이 그리디로 풀은 문제다. 직.. [백준 / BOJ] 1967 트리의 지름 문제 출처 : www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 가중치를 가진 트리가 주어진다. 이때, 트리의 지름을 구하는 문제이다. 트리의 지름은 트리의 모든 경로들중 가장 긴 경로를 말한다. (가장 긴 경로를 지름으로 하는 원을 그리면, 모든 노드들을 해당 경로안에 집어넣을수있다.) 풀이 전형적인 트리의 지름을 구하는 문제다. BFS,DFS,다익스트라 등으로 풀수있는데, 최단시간으로 답을 구하는 방법은 다익스트라라고 생각해서 다익스트라.. [백준 / BOJ] 1991 트리 순회 문제 출처 : www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 트리가 주어졌을때, 해당 트리를 전위순회, 중위순회, 후위순회한 결과를 출력하는 문제다. 풀이 트리 탐방자체는 어렵지않았는데, 입력을 트리구조로만드는게 난해한 문제였다. (순회 문제를 푼게 아니라 트리구조를 만드는 문제를 푼느낌...) 기본적인 트리구조(idx*2, idx*2+1)에 익숙해져서인지 처음엔 그런방향으로 구현하는걸 생각했었다. 입력이 위에서부터 너비우선탐색으로 입력되는것 같아서 .. [백준 / BOJ] 19581 두 번째 트리의 지름 문제 출처 : www.acmicpc.net/problem/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 트리가 주어졌을때 두번째로 긴 트리의 지름을 구하는 문제다. 풀이 트리의 지름을 구하는 임의의 지점에서 가장 먼지점 A를 찾고, A에서 가장 먼 지점 B를 찾으면 된다. 이걸 좀더 응용하면 되는데, 1. 임의의 지점 O 에서 가장 먼지점 A를 찾고, A에서 두번째로 먼 지점 B를 찾는다. 2. 임의의 지점 O 에서 두번째로 먼지점 C를 찾고, C에서 가장 먼 지점 D를 찾는다. 두 값.. [백준 / BOJ] 13325 이진트리 문제 출처 : www.acmicpc.net/problem/13325 13325번: 이진 트리 문제 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거�� www.acmicpc.net 1~K높이의 이진트리가 주어졌을때, 한 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 각 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 모두 같게하면서 에지의 가중치합을 최소로 만드는 문제다. 풀이 (백준에서 1초에 반복문이 1억번 돈다고 들은것같다..) 최악의 경우인 1^1 + 1^2 + 1 ^ 3 + ... .. 이전 1 2 다음
