from collections import deque
class TreeNode:
def __init__(self, key):
self.key = key # 노드의 값
self.left = None # 왼쪽 자식 노드를 가리킴
self.right = None # 오른쪽 자식 노드를 가리킴
class BinaryTree:
def __init__(self):
self.root = None # 트리의 루트 노드
# 새로운 노드를 삽입하는 함수 (레벨 순서 삽입)
def insert(self, key):
new_node = TreeNode(key)
if self.root is None:
self.root = new_node
return
# 레벨 순서로 트리를 탐색하기 위해 큐를 사용
queue = deque([self.root])
while queue:
node = queue.popleft()
# 왼쪽 자식이 비어있으면 삽입
if node.left is None:
node.left = new_node
break
else:
queue.append(node.left)
# 오른쪽 자식이 비어있으면 삽입
if node.right is None:
node.right = new_node
break
else:
queue.append(node.right)
def inorder_traversal(self):
# 중위 순회를 통해 트리의 노드들을 출력하는 함수
return self._inorder_traversal(self.root, [])
def _inorder_traversal(self, node, result):
if node:
self._inorder_traversal(node.left, result)
result.append(node.key)
self._inorder_traversal(node.right, result)
return result
# 예제 사용법
if __name__ == "__main__":
tree = BinaryTree()
tree.insert(50)
print("Inorder Traversal:", tree.inorder_traversal())
tree.insert(30)
print("Inorder Traversal:", tree.inorder_traversal())
tree.insert(20)
print("Inorder Traversal:", tree.inorder_traversal())
tree.insert(40)
print("Inorder Traversal:", tree.inorder_traversal())
tree.insert(70)
print("Inorder Traversal:", tree.inorder_traversal())
tree.insert(60)
print("Inorder Traversal:", tree.inorder_traversal())
tree.insert(80)
print("Inorder Traversal:", tree.inorder_traversal())
✅ 인접 리스트를 이용한 이진 트리 표현
def dfs(node):
if node == -1:
return
preorder.append(node)
dfs(graph[node][0])
inorder.append(node)
dfs(graph[node][1])
postorder.append(node)
N = int(input())
E = N - 1
arr = list(map(int, input().split()))
graph = [[] for _ in range(N + 1)]
# append 를 통해 갈 수 있는 경로를 추가하기
for i in range(E):
p, c = arr[i * 2], arr[i * 2 + 1]
graph[p].append(c)
# 없는 경우 -1로 데이터를 저장하기 위한 코드("좌우 경로가 있는가 ?")
# 탐색 시 index 오류를 방지하기 위해 없는 경로를 -1로 저장하였습니다.
for i in range(N + 1):
while len(graph[i]) < 2:
graph[i].append(-1)
preorder = []
inorder = []
postorder = []
dfs(1)
print(*inorder)
print(*preorder)
print(*postorder)
완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해 만든 자료구조
힙에서는 루트 노드의 원소만을 삭제할 수 있다.
루트 노드의 원소를 삭제하여 반환(return)한다.
힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.→ 최대 힙 / 최소 힙
Python의 공식 Library에 내장되어 있다.
배열을 통해 트리 형태를 쉽게 구현할 수 있다.
부모나 자식 노드를 O(1) 연산으로 쉽게 찾을 수 있음
n 위치에 있는 노드의 자식은 2n과 2n+1에 위치함
완전 이진 트리의 특성에 의해 추가/삭제 위치는 자료의 시작과 끝 인덱스로 쉽게 판단할 수 있음
# 입력 값 예시
'''
7
20 15 19 4 13 11 17
7
20 15 19 4 13 11 23
'''
from heapq import heappush, heappop
N = int(input()) # 필요한 노드 수
arr = list(map(int, input().split()))
heap = [] # 최대힙을 구현하기 위한 리스트
# 최소힙 ( 기본 )
for num in arr:
heappush(heap, num)
print([x for x in heap]) # 힙의 내부 상태를 출력 (음수로 저장된 상태)
while heap:
print(heappop(heap), end=' ')
print('\n------------------------------------')
# 최대힙
# 삽입 시 음수로 곱하여 저장 (제일 큰 수가 제일 작아짐)
# 삭제 후 음수값을 곱하여 출력 (다시 원래 수로 복구하여 출력)
for num in arr:
heappush(heap, -num)
print([-x for x in heap]) # 힙의 내부 상태를 출력 (음수로 저장된 상태)
while heap:
print(-heappop(heap), end=' ')
✅ 최대 힙 (max heap)
키(key) 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
(부모 노드의 키 값) > (자식 노드의 키 값)
루트 노드: 키 값이 가장 큰 노드
# 입력 값 예시
'''
7
20 15 19 4 13 11 17
7
20 15 19 4 13 11 23
'''
# 최대힙
def enq(n):
global last
last += 1 # 마지막 노드 추가(완전이진트리 유지)
h[last] = n # 마지막 노드에 데이터 삽입
c = last # 부모>자식 비교를 위해
p = c//2 # 부모번호 계산
while p >= 1 and h[p] < h[c]: # 부모가 있는데, 더 작으면
h[p], h[c] = h[c], h[p] # 교환
c = p
p = c//2
def deq():
global last
tmp = h[1] # 루트의 키값 보관
h[1] = h[last]
last -= 1
p = 1 # 새로 옮긴 루트
c = p*2
while c <= last: # 자식이 있으면
if c+1 <= last and h[c] < h[c+1]: # 오른쪽자식이 있고 더 크면
c += 1
if h[p] < h[c]:
h[p], h[c] = h[c], h[p]
p = c
c = p*2
else:
break
return tmp
N = int(input()) # 필요한 노드 수
arr = list(map(int, input().split()))
h = [0]*(N+1) # 최대힙
last = 0 # 힙의 마지막 노드 번호
for num in arr:
enq(num)
print(h)
while last > 0:
print(deq(), end=' ')
✅ 최소 힙 (min heap)
키(key) 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
(부모 노드의 키 값) < (자식 노드의 키 값)
루트 노드: 키 값이 가장 작은 노드
# 입력 값 예시
'''
7
20 15 19 4 13 11 17
7
20 15 19 4 13 11 23
'''
# 최소힙
def enq(n):
global last
last += 1 # 마지막 노드 추가(완전이진트리 유지)
h[last] = n # 마지막 노드에 데이터 삽입
c = last # 부모>자식 비교를 위해
p = c//2 # 부모번호 계산
while p >= 1 and h[p] > h[c]: # 부모가 있는데, 더 크면
h[p], h[c] = h[c], h[p] # 교환
c = p
p = c//2
def deq():
global last
tmp = h[1] # 루트의 키값 보관
h[1] = h[last]
last -= 1
p = 1 # 새로 옮긴 루트
c = p*2
while c <= last: # 자식이 있으면
if c+1 <= last and h[c] > h[c+1]: # 오른쪽자식이 있고 더 작으면
c += 1
if h[p] > h[c]:
h[p], h[c] = h[c], h[p]
p = c
c = p*2
else:
break
return tmp
N = int(input()) # 필요한 노드 수
arr = list(map(int, input().split()))
h = [0]*(N+1) # 최대힙
last = 0 # 힙의 마지막 노드 번호
for num in arr:
enq(num)
print(h)
while last > 0:
print(deq(), end=' ')
✅ 힙 연산 - 삽입(insertion)
시간복잡도 → O(log N)
✅ 힙 연산 - 삭제(delete)
시간복잡도 → O(log N)
✅ 힙의 활용
대표적으로 특별한 큐(e.g. 우선순위 큐) 구현과 정렬에 활용됨
우선순위 큐 구현 장점
노드 하나의 추가/삭제가 시간 복잡도 O(logN)이며, 최대값/최소값을 O(1)에 구할 수 있음
완전 정렬보다 관리 비용이 적게 듦
힙 정렬은 힙 자료구조를 이용하여 이진 탐색과 유사한 방법으로 수행
배열에 저장된 자료를 정렬하기에 유용하다.
힙 정렬의 시간복잡도 삽입/삭제 연산은 각각 O(logN)이므로, N개의 노드를 삽입 연산하고 삭제 연산하는 경우, 전체 정렬의 시간복잡도는 O(NlogN)이다.
1. [이진 트리 - 순회] 아래 트리(Tree)에서의 전위 순회, 중위 순회, 후위 순회에 대해 설명하시오.
"""
전위 순회: A - B - D - H - I - E - J - C - F - K - G - L - M
중위 순회: H - D - I - B - J - E - A - F - K - C - L - G - M
후위 순회: H - I - D - J - E - B - K - F - L - M - G - C - A
"""
2. [수식 트리] 아래 수식 이진 트리(Expression Binary Tree)의 전위 순회, 중위 순회, 후위 순회에 대해 설명하시오.
"""
전위순회 (식의 전위 표기법): + * * / A B C D E
중위순회 (식의 중위 표기법): A / B * C * D + E
후위순회 (식의 후위 표기법): A B / C * D * E +
"""
3. [이진 트리] 아래 이진 트리 표현에 대해 전위 순회하여 정점의 번호를 출력하시오.
첫 줄에는 트리 정점의 총 수(v)가 주어지고, 다음 줄부터 V - 1 개 간선이 나열된다.
간선은 그것을 이루는 두 정점으로 표기되며 항상 부모, 자식 순서로 표현된다.
간선은 부모 정점 번호가 작은 것부터 나열되고, 부모 정점이 동일하다면 자식 정점 번호가 작은 것부터 나열된다.
# 연습문제 3번 답안 코드(left, right를 쓰는 버전)
# 단, 입력이 반드시 각 노드당 최대 2번씩만 들어온다고 가정한 코드
# 전위 순회
def preorder(node):
if node == 0:
return
# 내 차례
print(node, end = ' ')
# 왼쪽 자식 차례
preorder(left[node])
# 오른쪽 자식 차례
preorder(right[node])
# 중위 순회
def inorder(node):
if node == 0:
return
# 왼쪽 자식 차례
inorder(left[node])
# 내 차례
print(node, end=' ')
# 오른쪽 자식 차례
inorder(right[node])
# 후위 순회
def postorder(node):
if node == 0:
return
# 왼쪽 자식 차례
postorder(left[node])
# 오른쪽 자식 차례
postorder(right[node])
# 내 차례
print(node, end = ' ')
N = int(input())
E = N - 1
arr = list(map(int, input().split()))
# 왼쪽 자식 번호를 저장할 리스트
left = [0] * (N + 1)
# 오른쪽 자식 번호를 저장할 리스트
right = [0] * (N + 1)
# 자식을 인덱스로 하여 부모 저장
par = [0] * (N + 1)
for i in range(E):
parent, child = arr[i*2], arr[i*2+1]
# 왼쪽 자식이 없다면, 왼쪽에 삽입함
if left[parent] == 0:
left[parent] = child
# 왼쪽 자식은 있지만, 오른쪽 자식이 없다면 오른쪽에 삽입함
else:
right[parent] = child
par[child] = parent
c = N
while par[c] != 0: # 부모가 있으면
c = par[c] # 부모를 새로운 자식으로 두고
# 더이상 부모가 없다면, root
root = c
# 전위 순회
preorder(root)
print()
# 중위 순회
inorder(root)
print()
# 후위 순회
postorder(root)
4. 자료구조에서 트리와 그래프의 차이는?
출처: https://bigsong.tistory.com/33
그래프(graph) 노드와 노드 간을 연결하는 간선으로 구성된 자료구조로, 연결된 노드의 관계를 표현할 수 있다.
순환/비순환 구조를 이룸
무방향/방향/양방향 그래프가 가능하며, 따라서 2개 이상의 경로가 가능함
루트(root) 노드의 개념이 없어서 부모 - 자식 관계의 개념이 없음
트리(tree) 그래프와 마찬가지로 노드 간의 연결을 간선으로 구성한 자료구조이다.
두 개의 노드 사이에 반드시 1개의 경로만을 가짐 (Only 방향 그래프)
"최소 연결 트리"라고 부르기도 함
부모 - 자식 관계가 성립하므로 "계층형 모델"이라고도 함
레벨이 존재함 (최상위 노드 : root)
완전이진트리의 경우 노드가 N개일 때, 간선은 N-1개이며 각 레벨(k)에 존재하는 노드는 2^k개이다.
비순환 구조 이므로 사이클이 존재하지 않음
트리의 순회에는 3가지(전위순회 / 중위순회 / 후위순회)가 존재한다.
5. [힙(heap)] 아래의 트리가 힙(heap)이 아닌 이유를 설명하시오.
▷ 트리1은 완전 이진 트리 형태가 아니므로 힙(heap)이 될 수 없고,
트리2는 루트 노드인 8의 값이 왼쪽 서브트리의 값들보다 작기 때문에 힙(heap)이 될 수 없다.
6. [힙(heap)] N개의 데이터를 힙(heap)으로 만든다면 시간 복잡도는 어떻게 될까?
