백준 골드 트리 순회 정복하기: 재귀 최적화와 시간 초과 탈출 비법

알고리즘 공부를 하다 보면 '트리'라는 벽을 만나게 됩니다. 실버급 문제는 단순한 재귀로도 술술 풀리지만, 골드 등급으로 올라가는 순간 상황이 달라지죠. 분명 로직은 맞는데 왜 자꾸 '시간 초과'나 '런타임 에러(StackOverflow)'가 뜨는 걸까요?
 
저도 처음엔 머리를 쥐어짜며 고민했습니다. 특히 데이터가 10만 개쯤 들어오는 2263번 같은 문제를 풀 때는 기존 방식이 통하지 않더군요. 오늘은 제가 수많은 '틀렸습니다'를 겪으며 정리한 골드급 트리 순회 구현 전략과 자바(Java) 최적화 팁을 아낌없이 공유해 드립니다.
 

[핵심 요약 박스]

* 위치 사전(Index Map): 중위 순회 값의 위치를 배열에 미리 저장해 O(1)로 탐색하기
* 분할 정복 범위 최적화: 인덱스 계산 실수 하나가 시간 초과를 부릅니다.
* Fast I/O & StringBuilder: 10만 개 이상의 출력은 무조건 StringBuilder가 답입니다.
* 비재귀(Iterative) 고려: 스택 오버플로우가 걱정된다면 스택 자료구조를 직접 쓰세요.
 

목차

* 트리 순회의 기본기와 골드급의 차이
* 트리의 순회에서 가장 많이 틀리는 이유 TOP 3
* 2263번 완전 정복: 위치 사전의 마법
* 5639번 & 1967번: 유형별 접근법 정리
* 자바 개발자를 위한 성능 최적화 실전 팁

트리 순회, 기본만 알면 골드에서 막힙니다

전위(Pre), 중위(In), 후위(Post) 순회의 개념은 다들 아실 겁니다. 하지만 골드 문제는 단순히 순회하는 게 아니라, "순회 결과 두 개를 줄 테니 나머지 하나를 복구해봐"라는 식으로 나옵니다. 마치 흩어진 퍼즐 조각을 맞추는 것과 같죠.
 
가장 기초적인 1991번 문제는 노드 개수가 적어 배열로 간단히 구현되지만, 2263번처럼 N이 10만 개라면 이야기가 다릅니다. 이때는 노드를 하나하나 찾으러 다니는 행위 자체가 사치입니다. 솔직히 말씀드리면, 탐색 시간을 줄이지 못하면 절대 통과할 수 없습니다.

사람들이 가장 많이 궁금해하는 질문

Q1. 자바에서 10만 개 노드 재귀 돌리면 무조건 터지나요?

보통 백준의 자바 스택 메모리는 1MB 내외로 제한적인 경우가 많습니다. 편향 트리(Skewed Tree)처럼 한쪽으로만 길게 늘어진 구조라면 10만 번의 재귀는 StackOverflow를 일으키기 딱 좋습니다. 개인적으로 이 부분이 가장 번거로운 지점인데, 문제를 풀 때 최대한 꼬리 재귀 형태로 짜거나, 정 불안하면 직접 Stack 클래스를 활용한 반복문 형태로 바꾸는 연습이 필요합니다.

Q2. 왜 제 코드는 Python보다 느린 것 같죠?

자바는 객체 생성 비용이 큽니다. 매번 new String()을 하거나 Scanner를 쓰면 입출력에서만 수백 ms를 잡아먹습니다. 또한, 파이썬의 dict는 편리하지만 속도가 느릴 때가 있는데, 자바는 단순 int[] 배열을 인덱스 사전으로 쓰면 압도적인 속도를 낼 수 있습니다.

2263번: 중위+후위로 전위 구하기 (핵심 전략)

이 문제의 핵심은 '후위 순회의 맨 끝이 루트 노드'라는 점과 '중위 순회에서 루트를 기준으로 좌우가 나뉜다'는 성질을 이용하는 것입니다.
 

재귀 함수를 호출할 때마다 중위 순회 배열에서 루트 노드의 인덱스를 찾아야 합니다. 이걸 for문으로 매번 찾으면 $O(N^2)$이 되어버리죠. 10만 개의 제곱은 100억입니다. 당연히 시간 초과죠. 여기서 모르면 손해 보는 팁이 바로 '위치 사전'입니다.

// 입력 단계에서 미리 위치를 저장해둡니다.
for(int i = 0; i < N; i++) {
    inOrder[i] = Integer.parseInt(st.nextToken());
    pos[inOrder[i]] = i; // 값 자체가 인덱스가 되는 마법
}

 
이렇게 하면 어떤 값이 중위 순회에서 몇 번째 인덱스에 있는지 0.00001초 만에 알 수 있습니다. 이후에는 재귀적으로 범위를 좁혀가며 루트를 먼저 출력(전위 순회)하면 끝납니다.
 
사실 여기서부터가 진짜 핵심입니다. 아래 표를 통해 주요 골드 트리 문제들의 특징을 비교해 보세요.

문제 번호	문제 이름	난이도	핵심 알고리즘	최적화 포인트
2263	트리의 순회	골드 1	분할 정복	위치 사전(Array) 사용
5639	이진 검색 트리	골드 4	BST 성질	스택 또는 재귀 범위 제한
1967	트리의 지름	골드 4	DFS / BFS	2번의 탐색으로 지름 찾기
11438	LCA 2	플래티넘 5	희소 배열	2^k 부모 전처리

 
표를 보면 아시겠지만, 단순 순회를 넘어 트리 고유의 성질(BST, 지름, 공통 조상)을 얼마나 잘 활용하느냐가 골드 등급의 관건입니다.

성능을 2배로 높이는 자바 구현 팁

코드를 다 짰는데 '시간 초과'가 난다면 로직보다는 입출력의 문제일 확률이 90%입니다. 마치 대형마트 오픈런을 하는데 자동문이 아니라 수동문을 하나씩 열고 들어가는 것과 같죠.

• Scanner는 버리세요: BufferedReader와 StringTokenizer 조합은 선택이 아닌 필수입니다.
• System.out.print는 금지: 10만 번의 출력을 따로 호출하면 입출력 버퍼링 때문에 엄청나게 느려집니다. StringBuilder에 담아서 마지막에 한 번만 출력하세요.
• 배열 크기 주의: 노드 번호가 1번부터 시작하면 new int[N + 1]로 선언해 인덱스 헷갈림을 방지하는 게 정신 건강에 이롭습니다.

나에게 맞는 최적의 선택지

트리 문제를 풀 때 본인의 상황에 맞춰 전략을 선택해 보세요.

• 재귀가 너무 어렵다면?: 5639번 같은 문제를 스택(Stack) 자료구조만 사용해서 풀어보세요. 재귀의 원리를 시각적으로 이해하는 데 큰 도움이 됩니다.
• 실행 속도가 중요하다면?: 무조건 자바나 C++을 추천합니다. 특히 대규모 트리 구조에서는 파이썬의 재귀 깊이 제한이 발목을 잡는 경우가 많습니다.
• 구현력을 키우고 싶다면?: 1167번이나 1967번 같은 '트리의 지름' 문제를 추천합니다. 트리를 그래프처럼 다루는 감각을 익힐 수 있습니다.

결국 트리 순회의 핵심은 "어떻게 하면 불필요한 탐색을 줄이고, 컴퓨터가 편하게 일하도록 범위를 쪼개줄 것인가"에 달려 있습니다. 여러분은 어떤 방식의 순회를 가장 선호하시나요?
 

함께 읽으면 좋은 글

Codewars 6kyu 알고리즘 정복: 나만의 JS 유틸리티 라이브러리 제작 가이드