본문 바로가기
알고리즘/백준

[BAEKJOON]5639 이진 검색 트리

by 응애~ 개발자 2025. 4. 29.
728x90
반응형

문제 요약

  • 알고리즘 분류: 트리, 트리 탐색
  • 난이도: Gold4
  • 문제내용:
    • 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
      • 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
      • 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
      • 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
    • 위 트리에서 전위 순회 한것을 후위 순회한 결과를 출력하여라
  • 사이트: https://www.acmicpc.net/problem/5639

문제풀이

   이번에는 문제 유형은 트리 탐색에 관련 문제이다. 트리에 관한 자세한 내용은 여기에서 보면된다.

문제 접근방법

이 문제의 핵심은 전위 순회 결과만 가지고 후위 순회 결과를 어떻게 구하느냐는 것입니다. 아래 와 같이 처음부터 집어 넣는 식으로 만들면 시간 초과로 나올 것입니다.

import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

def post_order(node):
    if tree[node][0]:
        post_order(tree[node][0])
    if tree[node][1]:
        post_order(tree[node][1])
    print(node)


root = int(input())
tree = {root: [0, 0]}

while True:
    try:
        node = root
        N = int(input())
        tree[N] = [0, 0]
        while node != 0:
            if N < node:
                after_node = tree[node][0]
                index = 0
            else:
                after_node = tree[node][1]
                index = 1
            if after_node == 0:
                tree[node][index] = N
                break

            node = after_node

    except:
        break
        
post_order(root)

 그래서  전위 순회 특성을 이용해서  후위 순위를 출력 하는 식으로 구현 해야지 시간 초과 이슈가 안 일어 날 것입니다.

 전위 순회의 특성상 가장 먼저 나오는 값이 루트 노드입니다. 이진 검색 트리의 특성을 활용하면, 루트 노드보다 큰 첫 번째 값이 나오는 위치부터는 오른쪽 서브트리가 시작됩니다. 이를 이용해 트리를 아래와 같은 구조로 탐색 할수 있습니다.

 

 

알고리즘 단계:

  1. 전위 순회 결과의 첫 번째 값은 현재 서브트리의 루트입니다.
  2. 루트보다 큰 첫 번째 값을 찾습니다. 이 값부터 오른쪽 서브트리가 시작됩니다.
  3. 루트 다음부터 오른쪽 서브트리 시작 전까지가 왼쪽 서브트리입니다.
  4. 왼쪽 서브트리와 오른쪽 서브트리에 대해 재귀적으로 같은 과정을 수행합니다.
  5. 후위 순회 순서(왼쪽-오른쪽-루트)로 값을 출력합니다.

마무리

이 문제는 이진 검색 트리의 특성과 트리 순회 방법에 대한 이해를 필요로 합니다. 재귀적으로 문제를 해결하는 방식으로, 전위 순회 결과만으로 원래 트리 구조를 유추하고 후위 순회 결과를 생성할 수 있습니다.

핵심 통찰은 이진 검색 트리에서 루트보다 큰 값이 처음 나타나는 위치가 오른쪽 서브트리의 시작이라는 점입니다. 이를 활용하여 트리를 분할 정복 방식으로 처리하면 효율적으로 문제를 해결할 수 있습니다.

이 문제를 통해 트리 자료구조와 재귀 알고리즘에 대한 이해를 깊게 할 수 있습니다.

Code

Python

import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

"""
전위 순회 결과로부터 후위 순회 결과를 생성하는 함수
root: 현재 서브트리의 루트 노드 인덱스
end: 현재 서브트리의 마지막 노드 인덱스
"""
def post_order(root, end):

    # 기저 조건: 유효하지 않은 범위면 종료
    if root > end:
        return

    start = root + 1  # 루트 다음 노드(왼쪽 서브트리의 시작)
    node = nodes[root]  # 현재 서브트리의 루트 값

    # 오른쪽 서브트리의 시작점(mid)을 찾음
    # 루트 값보다 큰 첫 번째 노드가 오른쪽 서브트리의 시작
    for index in range(start, end + 1):
        if node < nodes[index]:
            mid = index
            break
    else:
        # 모든 값이 루트보다 작거나 같으면 오른쪽 서브트리는 없음
        mid = end + 1

    # 왼쪽 서브트리 후위 순회 (start부터 mid-1까지)
    post_order(start, mid - 1)

    # 오른쪽 서브트리 후위 순회 (mid부터 end까지)
    post_order(mid, end)

    # 현재 노드 출력 (후위 순회에서는 루트가 마지막에 방문됨)
    print(node)


# 노드 값을 저장할 리스트
nodes = []

# EOF(파일 끝)까지 입력 받기
while True:
    try:
        N = int(input())
        nodes.append(N)
    except:
        # 입력이 더 이상 없거나 오류 발생시 입력 종료
        break

# 전체 트리에 대해 후위 순회 수행 (0부터 마지막 인덱스까지)
post_order(0, len(nodes) - 1)

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {

	static List<Integer> nodes; // 노드 값을 저장할 리스트

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
		nodes = new ArrayList<>();
		nodes.add(Integer.valueOf(br.readLine()));
		String line;
		while ((line = br.readLine()) != null && !line.isEmpty()) {
			nodes.add(Integer.valueOf(line));
		}
		
		// 전체 트리에 대해 후위 순회 수행 (0부터 마지막 인덱스까지)
		postOrder(0, nodes.size() - 1);

	}

	/*
	 * 전위 순회 결과로부터 후위 순회 결과를 생성하는 함수
	 * root: 현재 서브트리의 루트 노드 인덱스
	 * end: 현재 서브트리의 마지막 노드 인덱스
	 */
	static void postOrder(int root, int end){

		// 기저 조건: 유효하지 않은 범위면 종료
		if(root > end){
			return;
		}

		int start = root + 1; // 루트 다음 노드(왼쪽 서브트리의 시작)
		int node = nodes.get(root); // 현재 서브트리의 루트 값
		int mid = start;

		// 오른쪽 서브트리의 시작점(mid)을 찾음
		// 루트 값보다 큰 첫 번째 노드가 오른쪽 서브트리의 시작
		while(mid <= end){
			if(node < nodes.get(mid)){
				break;
			}
			mid++;
		}

		// 왼쪽 서브트리 후위 순회 (start부터 mid-1까지)
		postOrder(start, mid - 1);
		// 오른쪽 서브트리 후위 순회 (mid부터 end까지)
		postOrder(mid, end);
		// 현재 노드 출력 (후위 순회에서는 루트가 마지막에 방문됨)
		System.out.println(node);
	}

}

Javascript

var input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

/*
 * 전위 순회 결과로부터 후위 순회 결과를 생성하는 함수
 * root: 현재 서브트리의 루트 노드 인덱스
 * end: 현재 서브트리의 마지막 노드 인덱스
 */
function postOrder(root, end){
    // 기저 조건: 유효하지 않은 범위면 종료
    if(root > end){
        return;
    }

    const start = root + 1; // 루트 다음 노드(왼쪽 서브트리의 시작)
    const node = nodes[root]; // 현재 서브트리의 루트 값
    let mid = start;

    // 오른쪽 서브트리의 시작점(mid)을 찾음
    // 루트 값보다 큰 첫 번째 노드가 오른쪽 서브트리의 시작
    while(mid <= end){
        if(node < nodes[mid]){
            break;
        }
        mid++;
    }

    // 왼쪽 서브트리 후위 순회 (start부터 mid-1까지)
    postOrder(start, mid - 1);
    // 오른쪽 서브트리 후위 순회 (mid부터 end까지)
    postOrder(mid, end);
    // 현재 노드 출력 (후위 순회에서는 루트가 마지막에 방문됨)
    console.log(node);

}


let nodes = [parseInt(input[0])]

for (let i = 1; i < input.length; i++) {
    nodes.push(parseInt(input[i]));
}

// 전체 트리에 대해 후위 순회 수행 (0부터 마지막 인덱스까지)
postOrder(0, nodes.length - 1);
728x90
반응형

'알고리즘 > 백준' 카테고리의 다른 글

[BAEKJOON]7785 회사에 있는 사람  (0) 2025.05.12
[BAEKJOON]13241 최소공배수  (0) 2025.05.08
[BAEKJOON]11005 진법 변환 2  (0) 2025.04.29
[BAEKJOON]2745 진법 변환  (0) 2025.04.24
[BAEKJOON]25206 너의 평점은  (0) 2025.04.24

관련글

티스토리툴바