[BOJ] 5639 이진 검색 트리_binary search
Date:
이진 검색 트리
문제
전위 순회(루트-왼쪽-오른쪽)로 배열된 이진 트리를 후위 순회(왼쪽-오른쪽-루틑)로 변경하는 프로그램 작성
이진 트리 조건
- 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
- 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
- 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.
제약 사항
- node 수 : 10,000개 이하
- note의 key값 : 10**6 이하
해결 방법
graph를 그린 후 재귀함수를 통해 원하는 원소부터 접근할 수 있도록 조건을 걸어 준다.
이 문제는 두 가지 해결법으로 풀어보려고 한다. (풀고나서 다른 사람이 푼 코드를 보니, 너무 간결하게 되어있어 그 부분도 남겨보고자 한다.)
💨 재귀 함수를 컨트롤할 조건 정리하기
1차 풀이(효율성 🐢)
🌱idea
- Binary Tree에서 왼쪽과 오른쪽 구분을 위해 for문을 돌려 b0 보다 큰 수를 찾음
- 해당 index를 div_p(divid_point) 변수에 넣음
- 왼쪽 Tree와 오른쪽 트리에서 1번과 동일 연산을 반복
- 트리의 마지막이 되면 st>=end조건에 의해 재귀 함수를 마무리함
—
2차 풀이(효율성 🐇) - 정답자 풀이 참조하여 수정
🌱idea
- 함수 처음에 i=0으로 초기화(의미 : 트리 가장 밑부터 순서를 매긴다는 뜻)
- 현재값(b[st])과 다음값(b[st+1]을 비교, 다음값이 작으면 왼쪽 트리로 빠짐
- 이전 값(root)의 왼쪽 자식 수를 i로 지정
- 현재 값과 다음 값을 비교, 다음 값이 크면, 이전 root값과 다음 값(b[st+i+1])을 비교하여, 트리의 위치를 정함
1차 풀이
```python import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def bitree(st,end): if st >= end: return div_p=end for i in range(st+1,end): if b[st] < b[i]: div_p=i break
bitree(st+1,div_p)
bitree(div_p,end)
print(b[st])
b=[] while True: try : b+=[int(input())] except : break
bitree(0,len(b))
result :
> ## 2차 풀이
---
```python
import sys
input = sys.stdin.read
sys.setrecursionlimit(10**6)
def bitree(st,root):
i=0 #0으로 초기화 해주면, 맨 아래 노드부터 i값이 증가하기 시작함.
now=b[st]
if st+1>=len(b): return 0
if now>b[st+1]:
i += bitree(st+1,now) # 멈추는 역할
if root>b[st+i+1] :
i += bitree(st+i+1,root) # 위로 올라가는 역할
print(b[st])
return i+1
b=list(map(int,input().split()))
b+=[10**6+1] #st+1 = len(b)까지 돌리기 때문에, 마지막 항목 비교가 안되어, 입력수보다 큰 수를 추가
bitree(0,10**6+1)
result :
마무리
아직 재귀 함수를 다루는 게 익숙하지 않아, 오늘 마음잡고 한 번 털어보았다. 재귀 함수가 어떻게 동작하는지, 문제를 풀면서 생각해 내는 것도 익숙하지 않고, 설명하는 건 더 어려운 것 같다. 당분간은 재귀함수 문제를 풀면서 감을 익혀야 겠다.
💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡
댓글