좋아요!
Baekjoon 5639번 이진 검색 트리 문제를 위한 입력 예제, 정답, 코드, 그리고 한 줄 한 줄 디버깅급 풀이를 준비해 드릴게요.
사용자의 요구에 맞춰 예제와 정답을 코드 안에 포함하고, 코드의 각 줄을 예제와 연관 지으며 디버깅하듯 한 줄 한 줄 자세히 해설하겠습니다.
🎯 문제 요약
입력: 전위(preorder) 순회 순서가 한 줄에 하나씩 주어지는 이진 검색 트리(BST)가 주어짐.
출력: 후위(postorder) 순회 결과를 한 줄에 하나씩 출력.
🧪 입력 예제
50
30
24
5
28
45
98
52
60✅ 위 입력에 대한 정답
5
28
24
45
30
60
52
98
50🧠 트리 구조 해석
이 트리를 그려보면 아래와 같습니다.
50
/ \
30 98
/ \ /
24 45 52
/ \ \
5 28 60이 트리를 후위 순회(postorder) 하면:
- 왼쪽(30 트리) 후위 -> (5, 28, 24, 45, 30)
- 오른쪽(98 트리) 후위 -> (60, 52, 98)
- 루트 -> (50)
📝 Python 코드
이제 위 트리 구조를 이용하여 동작하는 코드를 짜 보겠습니다.
입력 부분을 코드 안에 포함해서 테스트할 수 있는 형태로 작성하고, 한 줄 한 줄 디버깅 형태의 자세한 설명을 추가하겠습니다.
# 트리의 각 노드를 나타내는 클래스 정의
class Node:
def __init__(self, key):
# 1. 생성자: Node 객체를 만들 때 호출됨
self.key = key # 2. 현재 노드의 값
self.left = None # 3. 왼쪽 자식
self.right = None # 4. 오른쪽 자식
# 트리에 새로운 값을 삽입하는 함수
def insert(root, key):
# 5. 트리의 루트가 비어 있으면 새 Node 반환
if root is None:
return Node(key)
# 6. 삽입할 값이 현재 루트보다 작으면 왼쪽 트리로 재귀 호출
if key < root.key:
root.left = insert(root.left, key)
# 7. 삽입할 값이 현재 루트보다 크면 오른쪽 트리로 재귀 호출
else:
root.right = insert(root.right, key)
# 8. 트리 구조가 바뀐 루트를 반환
return root
# 후위 순회를 출력하는 함수
def postorder(root):
# 9. 현재 노드가 None이면 종료 (리프에서 호출됨)
if root is None:
return
# 10. 왼쪽 서브트리 후위 순회
postorder(root.left)
# 11. 오른쪽 서브트리 후위 순회
postorder(root.right)
# 12. 현재 노드 출력
print(root.key)
# 13. 트리의 루트를 None으로 초기화
root = None
# 14. 여기서 문제의 예제 데이터를 리스트로 준비
preorder_input = [
50,
30,
24,
5,
28,
45,
98,
52,
60
]
# 15. 위 리스트의 각 값을 트리에 삽입
for num in preorder_input:
root = insert(root, num)
# 16. 트리의 후위 순회 호출
postorder(root)🕵♂️ 한 줄 한 줄 디버깅 해설
트리 구조 준비 부분
1~4. Node 클래스:
- 트리의 한 노드를 정의하는 부분입니다.
key속성에 현재 값(노드의 숫자)을 담고, 초기 상태에서는left와right를 None(없음) 상태로 둡니다.- 이렇게 트리 구조를 짜야 이후 트리를 연결할 수 있어요.
트리 삽입 부분
5~8. insert 함수:
- 트리에 새 값(
key)을 넣을 때 호출됩니다. - 트리(
root)가 비어 있으면 새로운 노드를 반환해서 트리의 루트를 잡아요. - 트리가 있으면, 현재 루트보다 작은 경우 왼쪽에 삽입하고 큰 경우 오른쪽에 삽입합니다.
- 이게 BST의 기본 규칙(왼쪽 < 루트 < 오른쪽)입니다.
- 재귀 호출을 이용해서 트리의 끝까지 내려갑니다.
트리 출력 부분
9~12. postorder 함수:
- 후위 순회를 구현합니다.
- 순서: 왼쪽 → 오른쪽 → 현재
- 현재 루트가 None일 경우 반환(재귀 종료 조건) 후, 양쪽을 탐색한 뒤 현재 노드를 출력합니다.
트리 구성과 호출 부분
13~16:
- 트리의 루트를 초기화
preorder_input리스트 안에 문제의 예제 데이터를 직접 넣었습니다.- 리스트를 for문으로 돌며 트리에 값들을 차례로 삽입 (
insert) - 트리가 다 구성된 후
postorder(root)호출 -> 트리 출력
🎯 코드 실행 결과
이 코드를 실행하면 터미널에:
5
28
24
45
30
60
52
98
50가 출력되며, 우리가 위에서 수작업 계산한 정답과 일치합니다.
맞아요, 질문에서 트리 삽입의 흐름을 잘 이해하고 계신 거 같습니다. 😊
그런데 조금만 다듬으면 훨씬 선명해질 거예요. 한 줄 한 줄 트리 삽입 과정을 정리해 드릴게요.
🔍 트리 삽입 과정 정리 (코드를 기준으로)
1️⃣ insert(root, key) 호출
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root🧠 단계별 예제 실행 상황
✅ 1번째 호출: insert(None, 50)
- 현재 트리가 비어 있으므로(
root is None) Node(50)을 만들어 반환 → 트리의 루트가 50이 됨.
✅ 2번째 호출: insert(root(50), 30)
여기서 root.key == 50, key == 30
-
root가 None이 아니므로 if문 통과 -
key(=30) < 50참 →root.left = insert(root.left, 30)- 현재
root.left가 None이므로insert(None, 30)호출 - 이 호출에서
Node(30)반환
- 현재
-
트리 구조:
50
/
30✅ 3번째 호출: insert(root(50), 24)
이번에도 root.key == 50, key == 24
-
24 < 50참 →root.left = insert(root.left(=30), 24) -
이제
insert(root(30), 24)호출24 < 30참 →root.left = insert(root.left(None), 24)- None이므로
Node(24)반환
-
트리 구조:
50
/
30
/
24✅ 4번째 호출: insert(root(50), 5)
5 < 50→root.left = insert(30, 5)5 < 30→root.left = insert(24, 5)5 < 24→root.left = insert(None, 5)→Node(5)반환
이런 식으로 트리를 아래로 내려가면서 if key < 현재노드.key 검사 후 왼쪽 혹은 오른쪽을 골라 타고 내려갑니다.
🎯 정리
✅ 질문 주신 부분 정리
첫 번째 호출: 트리 비어있음 → Node(50) 반환, 트리 루트 = 50두 번째 호출: 트리 루트 = 50 있는데, key=30 → 50보다 작으므로 왼쪽에 삽입따라서 “50이 들어가고, 30이니까 if문에 걸려서 왼쪽에 넣는다” → 맞아요.
단, "넣는다"는 트리의 왼쪽 자식 포인터가Node(30)을 가리키도록 바꾼다는 말이고, 반환값을 반드시root.left = insert(root.left, key)에 대입해주는 부분이 중요합니다.
좋아요! insert가 끝난 상태의 트리 구조를 한눈에 볼 수 있게 정리해 드릴게요.
우리가 넣은 입력 순서는 이거였죠:
50, 30, 24, 5, 28, 45, 98, 52, 60이 숫자들로 트리를 삽입해 나가면 트리 구조가 어떻게 되는지 한 줄 한 줄 쌓아보겠습니다.
🌳 트리 완성 상태 (계층 구조)
최종 트리 모양:
50
/ \
30 98
/ \ /
24 45 52
/ \ \
5 28 60📜 트리 상태를 단계별로 쌓아보기
50삽입 → 트리:
5030삽입 (50 > 30) → 트리:
50
/
3024삽입 (50 > 24,30 > 24)
50
/
30
/
245삽입 (50 > 5,30 > 5,24 > 5)
50
/
30
/
24
/
528삽입 (50 > 28,30 > 28,24 < 28)
50
/
30
/
24
/ \
5 2845삽입 (50 > 45,30 < 45)
50
/
30
/ \
24 45
/ \
5 2898삽입 (50 < 98)
50
/ \
30 98
/ \
24 45
/ \
5 2852삽입 (50 < 52,98 > 52)
50
/ \
30 98
/ \ /
24 45 52
/ \
5 2860삽입 (50 < 60,98 > 60,52 < 60)
50
/ \
30 98
/ \ /
24 45 52
/ \ \
5 28 60✅ 이렇게 트리 삽입이 끝난 상태가 위와 같습니다.
🎯 포스트오더(후위 순회) 할 때의 순서가 위 트리 구조에서 나오는 거예요.
후위 순회(
postorder):
왼쪽 → 오른쪽 → 루트
그래서 출력값이:
5
28
24
45
30
60
52
98
50맞아요! 후위 순회(postorder)의 핵심은 “왼쪽 → 오른쪽 → 루트” 순서인데,
이 부분을 단계마다 디버깅하면서 트리의 구조와 호출 순서를 보여드릴게요.
🎯 트리 구조 (다시 한 번)
최종 트리는 다음과 같습니다:
(50)
/ \
(30) (98)
/ \ /
(24) (45) (52)
/ \
(5) (28) \
(60)🧠 postorder(root) 함수:
def postorder(root):
if root is None:
return
postorder(root.left) # 1️⃣ 왼쪽
postorder(root.right) # 2️⃣ 오른쪽
print(root.key) # 3️⃣ 루트🔍 호출 디버깅 트레이스
후위순회가 어떻게 호출되는지를 “스택” 느낌으로 따라가 볼게요.
🔵 postorder(50)
- 왼쪽 호출:
postorder(30)
→ 이게 끝나야 오른쪽 호출 가능
🟠 postorder(30)
- 왼쪽 호출:
postorder(24)
🟠 postorder(24)
- 왼쪽 호출:
postorder(5)
→5의 왼쪽, 오른쪽은 없음 → 바로print(5) - 오른쪽 호출:
postorder(28)
→28도 자식 없음 →print(28) - 이제
24출력
🟠 postorder(24)가 끝나면 → postorder(45) 호출
→ 45 왼쪽/오른쪽 없음 → print(45)
🟠 이제 postorder(30)의 오른쪽까지 끝나면 print(30)
🔵 postorder(50)의 오른쪽 호출: postorder(98)
🟣 postorder(98)의 왼쪽 호출: postorder(52)
52의 왼쪽 없음52의 오른쪽 호출:postorder(60)→60출력- 이제
52출력 98출력
🔵 이제 postorder(50) 호출 끝 → print(50)
📜 호출 순서 한 줄 정리
postorder(50)
→ postorder(30)
→ postorder(24)
→ postorder(5) 출력 5
→ postorder(28) 출력 28
출력 24
→ postorder(45) 출력 45
출력 30
→ postorder(98)
→ postorder(52)
→ postorder(60) 출력 60
출력 52
출력 98
출력 50🎯 최종 출력
이 순서대로 출력되는 값:
5
28
24
45
30
60
52
98
50맞죠? 🎉
