알고리즘/백준

5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net ✅ 문제 설명 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하는 문제입니다. 이진 검색 트리? - 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. - 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. - 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. ✅ 접근 방식 처음 접근한 방법 전위순회 결과를 이용해서 트리를 만들고, 이를 후위순회하려했습니다. 그렇..

9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net ✅ 문제 설명 문제를 읽어보면 깊이가 K인 완전 이진 트리가 주어지고, 상근이는 중위순회 방식(왼쪽-> 루트 -> 오른쪽 순)으로 트리를 순회합니다. 이런 환경에서 상근이가 방문한 빌딩 번호가 순서대로 주어질 때, 완전 이진트리를 역으로 유추해 각 레벨에 있는 빌딩의 번호를 출력하는 문제입니다. ✅ 접근 방식 완전 이진 트리라는 점, 상근이가 중위순회를 한다는 것, 그리고 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 ..

1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net ✅ 문제 설명 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 문제입니다. (이진 트리: 각 노드가 최대 2개의 자식노드를 가지는 트리) 전위순회, 중위순회, 후위순회? 전위순회 = (루트) (왼쪽 자식) (오른쪽 자식) 중위순회 = (왼쪽 자식) (루트) (오른쪽 자식) 후위순회 = (왼쪽 자식) (오른쪽 자식) (루..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ✅ 문제 설명 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 문제다. 입력 => 첫째줄에 노드의 수 N이 주어지고, 둘째 줄부터 트리 상에서 연결된 두 정점이 주어진다. ex) 아래 그림에서 왼쪽과 같은 입력으로 트리를 그려보면 그림의 오른쪽과 같은 트리를 얻을 수 있다. ✅ 접근 방식 트리의 특징 상, 루트노드에서부터 탐색을 수행하면 부모노드를 거치지 않고선 자식노드에게 갈 수 없다. 루트노드에서 dfs나 bfs로 트리를 탐색하면서 "새롭게 탐색된 노드의 부모노드 = 현재 노드"로 저장해 준다. ✅ 코드 # 트..