본문 바로가기

트리

[BOJ] 백준 22856번 트리 순회 (Java)
Dot Algo∙ DS/PS 2022. 3. 18. [BOJ] 백준 22856번 트리 순회 (Java) #22856 트리 순회 난이도 : 골드 4 유형 : 트리 순회 / DFS 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net ▸ 문제 노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다. 유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로..
[BOJ] 백준 3038번 완전 이진 트리 (Java)
Dot Algo∙ DS/PS 2022. 3. 5. [BOJ] 백준 3038번 완전 이진 트리 (Java) #3038 완전 이진 트리 난이도 : 플레 4 유형 : 트리 / 애드 혹 3038번: 완전 이진 트리 완전 이진 트리의 각 노드는 계측적인 구조로 이루어져 있다. 루트 노드의 레벨은 0이며, 레벨 1의 두 자식 노드를 가지고 있다. 또, 레벨 1의 자식 노드의 레벨은 2이다. 보통 레벨이 N인 완전 이 www.acmicpc.net ▸ 문제 완전 이진 트리의 각 노드는 계측적인 구조로 이루어져 있다. 루트 노드의 레벨은 0이며, 레벨 1의 두 자식 노드를 가지고 있다. 또, 레벨 1의 자식 노드의 레벨은 2이다. 보통 레벨이 N인 완전 이진 트리는 2N-1개의 노드를 가지고 있다. 레벨이 N-1이 아닌 모든 노드는 자식 노드를 두 개씩 가지고 있다. 1부터 2N-1까지 숫자를 레벨이 N인 완전 이진 트리의..
[BOJ] 백준 12888번 완전 이진 트리 도로 네트워크 (Java)
Dot Algo∙ DS/PS 2022. 3. 4. [BOJ] 백준 12888번 완전 이진 트리 도로 네트워크 (Java) #12888 완전 이진 트리 도로 네트워크 난이도 : 골드 4 유형 : dp / 트리 12888번: 완전 이진 트리 도로 네트워크 모든 도시를 방문한 차의 개수가 모두 1개가 되기 위해서, 수빈이가 차를 최소 몇 대를 보내야 하는지 출력한다. 정답은 항상 64비트 정수로 나타낼 수 있다. www.acmicpc.net ▸ 문제 BOJ 나라는 도시와 두 도시를 연결하는 도로로 이루어져 있다. 이 나라의 도로 네트워크는 완전 이진 트리의 형태를 가진다. 수빈이는 BOJ 나라의 도로 네트워크 트리의 높이 H를 알고 있다. 트리의 높이를 안다면, 도시의 개수와 도로의 개수도 구할 수 있다. 트리의 높이가 H인 경우에 도시의 개수는 2(H+1)-1개 이고, 도로의 개수는 2(H+1)-2개가 된다. 아래 그림은 H ..
[BOJ] 백준 19581번 두 번째 트리의 지름 (Java)
Dot Algo∙ DS/PS 2022. 2. 28. [BOJ] 백준 19581번 두 번째 트리의 지름 (Java) #19581 두 번째 트리의 지름 난이도 : 골드 1 유형 : 트리 / BFS 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net ▸ 문제 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리는 두 번째 트리의 지름을 구하려고 한다. 두 번째 트리의 지름은 무엇이냐? 바로 두 번째로 가장 먼 두 정점 간의 거리를 의미한다. (두 번째 트리의 지름은 트리의 지름과 같..
[BOJ] 백준 20530번 양분 (Java)
Dot Algo∙ DS/PS 2022. 2. 26. [BOJ] 백준 20530번 양분 (Java) #20530 양분 난이도 : 골드 2 유형 : 트리 / DFS 20530번: 양분 첫째 줄에 두 자연수 $N$, $Q$가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 $N$개이며 쿼리가 $Q$개 주어진다는 것을 의미한다. 둘째 줄부터 $N$개의 줄에는 $i$번 간선이 연결하는 두 정점 www.acmicpc.net ▸ 문제 나무 T는 양분을 먹고 자란다. 원래 나무는 정점 N개와 간선 N−1개로 구성되어야 하지만, 양분을 너무 많이 먹어버린 나머지 나무 T는 N개의 간선을 갖게 되었다. 더 이상 트리가 아니기 때문에 T는 꿈의 무대인 트리와 쿼리에 등장하지 못한다. 슬퍼하고 있는 T 위해 정휘는 새로운 문제를 만들어 주었다. N개의 정점과 N개의 간선으로 이루어진 연결 그래프 T가 주어진다. 정점은 ..
[BOJ] 백준 13325번 이진 트리 (Java)
Dot Algo∙ DS/PS 2022. 1. 21. [BOJ] 백준 13325번 이진 트리 (Java) #13325 이진 트리 난이도 : 골드 4 유형 : 트리 / DFS 13325번: 이진 트리 입력 데이터는 표준입력을 사용한다. 입력의 첫째 줄에는 포화이진트리의 높이를 나타내는 양의 정수 k(1 ≤ k ≤ 20)가 주어진다. 두 번째 줄에는 모든 에지들의 가중치가 주어진다. 에지들의 가 www.acmicpc.net ▸ 문제 각 에지에 양수인 가중치가 부여된 높이가 k인 포화이진트리가 주어져 있다. 높이 k인 포화이진트리는 2k개의 리프를 포함하여 (2k+1 − 1)개의 노드를 가진다. 루트에서 어떤 리프까지의 거리는 루트에서 그 리프까지의 경로상에 있는 모든 에지들의 가중치를 더한 값이다. 이 문제에서는, 어떤 에지들의 가중치를 증가시켜서 루트에서 모든 리프까지의 거리가 같도록 하고, 또한 에지 가중치..
[BOJ] 백준 14570번 나무 위의 구슬 (Java)
Dot Algo∙ DS/PS 2021. 12. 25. [BOJ] 백준 14570번 나무 위의 구슬 (Java) #14570 나무 위의 구슬 난이도 : 골드 2 유형 : 트리 / DFS 14570번: 나무 위의 구슬 이진 트리란, 위처럼 모든 노드의 자식의 수가 2개 이하인 트리이다. 각 노드에 쓰여 있는 수는 노드의 번호를 의미한다. 특히, 이 문제에서는 루트가 고정되어 있으며, 노드의 순서가 중요한(어 www.acmicpc.net ▸ 문제 이진 트리란, 위처럼 모든 노드의 자식의 수가 2개 이하인 트리이다. 각 노드에 쓰여 있는 수는 노드의 번호를 의미한다. 특히, 이 문제에서는 루트가 고정되어 있으며, 노드의 순서가 중요한(어떤 서브트리에서도 좌우를 변경할 수 없는) 이진 트리에 대해 다루기로 한다. 이진 트리의 루트에 구슬을 하나 올려놓으면 구슬은 아래와 같은 과정을 거쳐 떨어진다. 현재 구슬이 놓인 노드의..
[BOJ] 백준 7812번 중앙 트리 (Java)
Dot Algo∙ DS/PS 2021. 12. 24. [BOJ] 백준 7812번 중앙 트리 (Java) #7812 중앙 트리 난이도 : 플레 5 유형 : 트리 / DFS 7812번: 중앙 트리 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫 줄에는 트리의 정점의 수 n이 주어진다. (1 ≤ n ≤ 10,000) 각 정점은 0번부터 n-1번까지 번호가 붙여져 있다. 다음 n-1개 줄 www.acmicpc.net ▸ 문제 트리는 사이클을 갖지 않는 연결된 그래프이다. 중앙 정점은 모든 정점으로 이르는 비용의 합이 가장 작은 정점이다. 트리의 정점 개수가 작은 경우에는 모든 경우의 수를 다 계산해보는 프로그램을 이용해 쉽게 구할 수 있다. 위의 그림은 가중치가 있는 트리로, 정점의 개수는 5개이다. 이 트리의 중앙 정점은 B이다. B-A = 2, B-D = 7, B-C = 1, B-E ..

티스토리툴바

티스토리툴바