오늘부터 본격적으로 알고리즘 문제를 풀었다.
1번 1991 트리 순회
https://www.acmicpc.net/problem/1991
파이썬에서 이진 탐색 트리를 만들기 위해 Node와 트리 클래스를 만들어서 설계한다. 동료(룸메이트)분께서 알려주셨다. 딕셔너리와 재귀를 통해 루트, 왼쪽, 오른쪽 노드로 나누어서 프린트한다.
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8) # 재귀함수 리미트하여 메모리 초과 방지
n = int(input())
# 딕셔너리로 트리 구현
tree = {}
for i in range(n):
root, left, right = map(str, input().split()) # 루트, 왼쪽자식, 오른쪽 자식
tree[root] = left, right # {'A': ('B', 'C')}
# 즉, 입력받은 left, right를 root A의 자식 B,C로 저장한다
print(tree)
def preorder(v): # 전위순회
if v != ".": # 루트 노트가 .이 아니면 (자식이 있다면)
print(v, end="") # 루트를 우선적으로 출력
preorder(tree[v][0]) # 재귀적으로 왼쪽 노드 탐색
preorder(tree[v][1]) # 재귀적으로 오른쪽 노드 탐색
def inorder(v): # 중위순회
if v != ".": # .이 아니면
inorder(tree[v][0]) # 재귀적으로 왼쪽 노드 탐색
print(v, end="") # 루트 출력
inorder(tree[v][1]) # 재귀적으로 오른쪽 노드 탐색
def postorder(v): # 후위순회
if v != ".": # .이 아니면
postorder(tree[v][0]) # 재귀적으로 왼쪽 노드 탐색
postorder(tree[v][1]) # 재귀적으로 오른쪽 노드 탐색
print(v, end="") # 루트 출력
#루트노드이므로 'A'로 고정
preorder('A')
print()
inorder('A')
print()
postorder('A')어떻게 그전으로 돌아가서 다른 브런치를 찾을까? 재귀함수가 자동으로 스택을 사용하기 때문에 가능하다고한다. 재귀를 호출하면 시스템 스택에 쌓이고 재귀가 끝나면 이전 상태로 복귀한다. 그러므로 한쪽 브런치가 완료되면 초기로 돌아가 다음 브런치를 찾는다.
2번 5639 이진 검색 트리
https://www.acmicpc.net/problem/5639
이진 트리의 이론은 모든 왼쪽 자식들 <= 부모노드 < 모든 오른쪽 자식들 의 규칙을 치켜야한다. 입력은 전위 순회이고 출력은 후위 순회이다. 인덱스만 가지고 트리를 구현한다. 직접 트리를 구현하면 오류가 나온다.(시간이 오래걸려서) 그래서 딕셔너리를 통해서 구현한다. 정산적인 출력을 위해 EOF 처리를 해주는데 팀원분들을 통해 좋은 정보를 알았다.
# import sys
# sys.setrecursionlimit(10**6)
# input = sys.stdin.readline
# NUM = []
# while True: # N을 받아서 입력 횟수를 받지 않기 때문에 공백이 입력되면 종료시키는 EOF처리를 해준다.
# try:
# NUM.append(int(input()))
# except:
# break
# def post_order(left, right): # 입력단 전위 순회 구현
# if left > right: # 직전값과 현재값 비교해서 직전값이 크면 종료
# return
# mid = right + 1 # mid는 오른쪽 서브트리의 시작 인덱스를 저장할 변수
# for i in range(left+1, right+1): # 현재 서브트리의 범위 내에서 탐색
# if NUM[left] < NUM[i]: # 현재 루트보다 큰 값이 나오면 오른쪽 서브트리 시작점
# mid = i
# break # 찾으면 바로 루프 종료
# # 재귀적으로 왼쪽 오른쪽 서브트리 탐색
# post_order(left+1, mid-1) # 왼쪽 서브트리 탐색 (NUM[left]보다 작은 값들)
# post_order(mid, right) # 오른쪽 서브트리 탐색 (NUM[left]보다 큰 값들)
# # 루트 출력
# print(NUM[left]) # 현재 서브트리의 루트 노드 출력
# # 후위 순회
# post_order(0, len(NUM)-1)
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
class Node: # 노드 설정
def __init__(self, data) -> None:
self.data = data
self.left = None
self.right = None
nodes = []
while True: # 노드 입력 처리
try:
nodes.append(Node(int(input())))
except:
break
class Tree:
def __init__(self) -> None:
self.root = None
def insert(self, node): # 노드 추가
if self.root is None: # 아무것도 없으면 입력
self.root = node
else: # 자식 노드가 있으면 검사
root = self.root
while True:
# 작으면 left
if node.data < root.data: # 추가할 노드가 이미 있는 루트보다 작으면
if root.left is None:
root.left = node
break
else:
root = root.left
# 크면 right (같은 경우는 없음)
else:
if root.right is None:
root.right = node
break
else:
root = root.right
# 후위 순회 진행
def postorder(node):
if node is None:
return
postorder(node.left)
postorder(node.right)
print(node.data)
# 노드 입력
tree = Tree()
for node in nodes:
tree.insert(node)
postorder(tree.root) 해당 방식에 대해서 여러 방법을 살펴보았다. 딕셔너리, 리스트로 구현하는 방식이 있지만 원리적으로 left, right로 노드를 추가해서 구현해 보고 싶었다. 거의 토요일 하루종일 했지만 100퍼센트 이해하지 못했다. 내일 다시한번 보겠다.
21:00 ~
다음 문제가 최소신장트리를 알아야하기 때문에, 위상정렬과 최소신장트리 개념을 다시 공부하고 돌아오겠다. 이번엔 코드 공부와 병행하겠다.
코가 너무 나와서 훌쩍거려서 머리가 어지럽다. 공부에 지장이 갈 정도라… 내일 약국 갔다와야겠다.
전화를 1시간 하게되어서 집중 못하는 김에 벨로그 내용을 티스토리로 복사했다.
이제 위상정렬과 최소신장 트리 개념을 정복해보겠다.(코드까지)
이날 이야기 꽃이 피어서 위상정렬만 하고 돌아갔다. 위상정렬은 전 포스트를 참고하면된다.
