본문 바로가기

트리

[백준 1991] 트리 순회(JAVA)

CodingTEST 2024. 1. 16. [백준 1991] 트리 순회(JAVA) 백준 1991번 문제 - 트리 순회 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 문제 분석 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램 만들기 전위 순회: (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회 : (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회 : (왼쪽 자식) (오른쪽 자식) (루트) 해결 포인트 재귀 함수 사용 트리 노드 클래스 구현..

[백준 17073] 나무 위의 빗물 (JAVA)

CodingTEST 2023. 10. 18. [백준 17073] 나무 위의 빗물 (JAVA) 백준 17073번 문제 - 나무 위의 빗물 17073번: 나무 위의 빗물 첫째 줄에 트리의 노드의 수 N과 1번 노드에 고인 물의 양을 의미하는 정수 W가 주어진다. (2 ≤ N ≤ 500,000, 1 ≤ W ≤ 109) 다음 N-1줄에 걸쳐, 트리에 존재하는 간선의 정보가 U V의 형태로 주어진다 www.acmicpc.net 문제 분석 더 이상 물이 움직이지 않을 때 : 마지막 리프로 모든 물이 다 내려갔을 때 이 때 물이 존재하는 리프들이 물들의 평균을 구해 출력해라 해결 키 포인트 마지막 리프 개수 구하는 법 처음에는 BFS와 같이 큐를 제작하고 visited를 체크하면서 관련된 간선이 모두 visited된 상태일 경우 마지막 리프로 처리하는 방법 시도 → 실패 (이렇게 하면 문제가 생기는 듯) 관..

[백준 3584] 가장 가까운 공통 조상 (JAVA)

CodingTEST 2023. 10. 11. [백준 3584] 가장 가까운 공통 조상 (JAVA) 백준 3584번 문제 - 가장 가까운 공통 조상 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 분석 루트가 있는 트리가 주어졌을 때, 가장 가까운 공통 조상을 출력해라 해결 키 포인트 문제를 보고 depth를 통일시키고 부모를 확인할 때, 부모가 동일하면 출력하면 되겠구나 쉽게 생각했다. 고민은 "depth를 어떻게 확인하냐" 뿐 입력을 받고 맵에 해당 값이 존재하면 해당 depth +1, 존재하지 않으면 0으로 (최상위부모)로 설정하고 자식 노드에게..

[백준 5639] 이진 검색 트리 (JAVA)

CodingTEST 2023. 10. 11. [백준 5639] 이진 검색 트리 (JAVA) 백준 5639번 문제 - 이진 검색 트리 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 분석 이진 검색 트리가 전위 순회 (루트 - 왼쪽 - 오른쪽) 했을 때 결과를 입력 해당 이진 검색 트리를 후위 순회 (왼쪽 - 오른쪽 - 루트) 했을 때 결과를 출력 해결 키 포인트 전위 순회 입력을 통해 이진 검색 트리를 생성 처음에 이전 루트를 기억해 해당 루트와 비교하여 트리를 생성하는 방법 사용 1. 이전 루트 > 해당 루트 : 해당 루트를 이전 루트의 left로 설정 2. 이전 루트 < 해당 ..

[백준 14675] 단절점과 단절선 (JAVA)

CodingTEST 2023. 9. 19. [백준 14675] 단절점과 단절선 (JAVA) 백준 14675번 문제 - 단절점과 단절선 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net 문제 분석 트리에서 해당 점이 단절점인지, 해당 선이 단절선인지 유무를 출력한다. 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우 해결 키 포인트 각 정점에 연결된 정점 정보를 ArrayList로 제작한다. 질문에 대한 답을..

이전 1 다음

티스토리툴바