제가 재학 중인 대학교에서 열린 파이썬 알고리즘 코딩캠프(25.02.03 ~ 25.02.14) 수업을 듣고 정리한 글입니다.
목차 :
- 트리, 이진 트리
- 이진 트리의 순회
- 힙, 우선순위 큐
트리, 이진 트리
트리는 ‘사이클이 없는 무방향 그래프’를 의미하며, 계층형 자료구조를 가짐.
이진 트리 : 노드의 차수가 최대 2인 트리
트리 및 이진 트리에 대한 자세한 건 자료구조 때 공부했던 거 참고.
트리는 다양한 표현 방식이 있으나, 이진 트리의 경우는 차수 최대 제한이 있으니,
각 노드에 대해 left, right 두 가지를 가지고 표현하는 게 가장 효율적.
백준 등에서 트리에 대한 입력은 보통 아래처럼 들어옴.
0번은 보통 안 씀.
L R이 둘다 -1면 리프 노드 ← 문풀에 많이 쓰는 정보.
1번부터 13번까지 총 13개의 정점이 존재하는 트리에 대한 입력이 아래와 같이 주어진다고 가정한다.
첫 줄에는 정점의 개수 n이 주어지고, 그 다음 줄에는 부모-자식 연결 간선이 일렬로 주어진다.
예를 들어, `1 2 1 3` 이라면 `1-2, 1-3` 두 개의 간선이 주어진다는 의미이다. (앞이 부모, 뒤가 자식)
13
1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13이때, 인접리스트를 응용한 방식으로 이진 트리를 아래와 같이 나타낼 수 있다.
각 부모 노드는 자식 노드의 정보를 크기가 2인 배열에 저장한다. `([왼쪽 자식 노드, 오른쪽 자식 노드])`
처음에는 모두 -1로 초기화 한다. -1은 왼쪽 혹은 오른쪽에 자식 노드가 존재하지 않음을 의미한다.
이후 간선 정보에 따라 왼쪽, 오른쪽 자식 노드를 채워간다.
# 1. 이진 트리
'''
13
1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13
'''
n = int(input())
nodes = list(map(int, input().split()))
# 1. 트리를 초기화하기
# 정점번호가 1부터 시작할 거니까, n + 1개
tree = [[-1, -1] for _ in range(n + 1)]
# 간선의 정보를 채움
for i in range(0, len(nodes), 2):
parent = nodes[i]
child = nodes[i + 1]
if tree[parent][0] == -1: # [-1, -1] 리스트 하나의 첫번째 놈
tree[parent][0] = child
continue
tree[parent][1] = child
for line in tree:
print(line)
'''
[-1, -1]
[2, 3]
[4, -1]
[5, 6]
[7, -1]
[8, 9]
[10, 11]
[12, -1]
[-1, -1]
[-1, -1]
[-1, -1]
[13, -1]
[-1, -1]
[-1, -1]
'''이진 트리의 순회
이진 트리의 순회 - 전위, 중위, 후위 순회
여기서 말하는 전 중 후는, 부모 노드가 앞에 오냐 중간에 오냐 나중에 오냐를 말하는 거임.
여기서 L → R 순서는 바뀌지 않음. 그냥 C(center)의 위치 차이.
전위순회는 굳이 말하면, CLR이 아닌 CLtRt임. (left subtree, right subtree)
# 2. 전위 순회
'''
13
1 2 1 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 11 13
'''
n = int(input())
nodes = list(map(int, input().split()))
# 1. 트리를 초기화하기
# 정점번호가 1부터 시작할 거니까, n + 1개
tree = [[-1, -1] for _ in range(n + 1)]
# 간선의 정보를 채움
for i in range(0, len(nodes), 2):
parent = nodes[i]
child = nodes[i + 1]
if tree[parent][0] == -1: # [-1, -1] 리스트 하나의 첫번째 놈
tree[parent][0] = child
continue
tree[parent][1] = child
# 1. 전위 순회
def preorder(node):
# 1. 종료 조건
# 없는 가상의 노드에 들어오면, 일단 들어오고 그 담에 끝냄
if node == -1:
return
# 2. 점화식(재귀식)
print(node, end = ' ')
preorder(tree[node][0])
preorder(tree[node][1])
# preorder(1)
# 1 2 4 7 12 3 5 8 9 6 10 11 13
# 2. 중위 순회
def inorder(node):
# 1. 종료 조건
# 없는 가상의 노드에 들어오면, 일단 들어오고 그 담에 끝냄
if node == -1:
return
# 2. 점화식(재귀식)
inorder(tree[node][0])
print(node, end = ' ')
inorder(tree[node][1])
# inorder(1)
# 12 7 4 2 1 8 5 9 3 10 6 13 11
# 3. 후위 순회
def postorder(node):
# 1. 종료 조건
# 없는 가상의 노드에 들어오면, 일단 들어오고 그 담에 끝냄
if node == -1:
return
# 2. 점화식(재귀식)
postorder(tree[node][0])
postorder(tree[node][1])
print(node, end = ' ')
# postorder(1)
# 12 7 4 2 8 9 5 10 13 11 6 3 1힙, 우선순위 큐
여기서 힙의 구현에 대해선 설명하지 않을거임. 구현은 자료구조 시간 때 배운 C언어 구현 참고.
완전이진트리 : 왼쪽부터 차례로 빈 곳 없이 채워진 이진 트리.
힙은 우선순위 큐를 구현하는 데 쓰임.
자바는 우선순위 큐 클래스가 따로 있는데, 파이썬은 우선순위 큐를 힙으로 구현해야 됨. 근데, 힙을 또 완전 이진트리로 구현함.
리스트 → (로 구현한) 힙 → (로 구현한) 우선순위 큐
힙: 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리의 일종.
최소 힙: 크기가 작은 원소를 우선적으로 뽑는 힙. (항상 부모 노드의 값이 자식 노드의 값보다 큰 완전 이진 트리.)
최대 힙: 크기가 큰 원소를 우선적으로 뽑는 힙 (항상 부모 노드의 값이 자식 노드의 값보다 작은 완전 이진 트리.)
(형제 노드들끼리의 순서는 중요하지 x)
그래서 이 우선순위 큐를 어떻게 구현하나?
그냥 queue로 구현할 수도 있을거임.
하지만 이 경우, 파이썬은 list 또는 deque니까,
여기서 최소랑 최대 찾으려면 반복문 돌아야 함. O(n). 또 제거 후 옮겨주기도 필요함. O(n). 이 땐 삽입은 그냥 push하면 되니 O(1)이겠지만.
아님 애초에 정렬된 상태를 유지할거라 해도, 처음 정렬하는 데에도 O(nlogn)은 최소한 소요되고, 새 요소를 어느 위치에 넣어줘야 할 지 리스트 다 조회하는데 O(n)임. 이 땐 제거는 그냥 popleft하면 되니 O(1)이겠지만.
결국, 작은 거랑 큰거 찾을 때마다(아님 넣을 때마다) O(n)을 써야 하는 게 좀 불편한거임.
근데 힙을 써서 구현하면, 더 빠르게 작은 거랑 큰 거 찾을 수 있지 않을까 하는 거.
이제, 힙을 사용해 우선순위 큐를 구현할 거임.
파이썬에선 힙을 구현할 때 list를 사용함.
삽입과 삭제가 힙(또는 이를 통해 구현한 우선순위 큐) ADT의 대표적 연산들.
삽입
- 가장 마지막 노드 위치에 삽입
- (최소 힙 기준) 부모 < 자식이 될 때까지 올라가면서 swap
힙의 삽입 시간복잡도는 O(log(n)).
왜냐하면, 완전 이진 트리의 height는 점근적으로 log_2(n) 이기 때문. 최악의 경우 루트 노드까지 높이만큼 올라감.
삭제
- (루트 노드를 제거)
- 가장 마지막 노드를 루트로 이동
- (최소 힙 기준) 부모 < 자식이 될 때까지 더 작은 노드 쪽으로 내려가면서 swap
힙의 삭제 시간복잡도는 O(log(n))
왜냐하면, 최악의 경우 높이만큼 내려감.
결론) 힙(또는 이를 통해 구현한 우선순위 큐)의 삽입 삭제 연산 시간복잡도는 O(log(n))을 보장함.
근데, 아까 리스트 또는 덱을 통해 구현한 우선순위 큐는 삽입 삭제 연산 시간복잡도가 O(n)이었잖음?
이 이유때문에 힙을 쓰는 것이다.
강노에 있는 힙을 직접 우리가 구현할 일이 거의 없다고 보면 됨. 99.9%.
순열, 조합에서 직접 조건에 따라 구현했던 그 일이 사실상 없음.
따라서, 그냥 힙큐 모듈을 사용하면 됨.
하지만 그 원리는 당연히 알고 있어야지.(이미 학교에서 배웠기도 하고)
# heapq 모듈
from heapq import heappop, heappush
heap = []
# 삽입
heappush(heap, 5)
heappush(heap, 3)
heappush(heap, 1)
heappush(heap, 0)
heappush(heap, -9)
# heappush(리스트, 숫자) -> 이 리스트에 숫자를 넣겠다.
# 우리는 일반 리스트를 힙처럼 사용할 것임.
# list.append처럼 메서드 형식으로 사용한 것과 차이가 있다.
print(heap) # [-9, 0, 3, 5, 1]
# 보면 알겠지만, heap이 내부적으로 정렬되어있진 않음.
# 그냥 루트 노드가 젤 작은 놈인거임.
# 조회
print(heap[0])
# 삭제
print(heappop(heap))
print(heappop(heap))
print(heappop(heap))
print(heappop(heap))
print(heappop(heap))
# -9
# 0
# 1
# 3
# 5
# 그래서 힙 정렬이란 것도 있는데, 힙에 다 넣고 빼는 거임. 2 * log(n) = O(log(n))
heappush(heap, (1, 3))
heappush(heap, (2, 3))
heappush(heap, (1, 2))
print(heappop(heap)) # (1, 2)
# 컨테이너 자료형이 저기 들어가면,
# 앞부분의 원소부터 순서대로 정렬!!
# 엄청 중요함 이거.근데, 파이썬의 heapq는 기본적으로 최소 힙임.
그럼, 최대 힙은 어떻게 구현할까? → 과제에 백준 문제가 있으니, 그걸 참고.
과제 및 풀이 정리
- 트리 전위, 중위, 후위 순회
- 우선순위 큐
- 최대 힙
- 절댓값 힙
- 트리 순회
- 더 맵게
- 부동산 다툼
- 게으름뱅이
- 트리
'Algorithms & Languages > 25-1 파이썬 알고리즘 코딩캠프' 카테고리의 다른 글
| [알고리즘 코딩캠프 9일차] 다익스트라 알고리즘 (0) | 2025.02.28 |
|---|---|
| [알고리즘 코딩캠프 8일차] 유니온 파인드, 최소 신장 트리(MST), 크루스칼 알고리즘 (0) | 2025.02.27 |
| [알고리즘 코딩캠프 6일차] 순열, 조합, 중복순열, 중복조합, 백트래킹 (0) | 2025.02.23 |
| [알고리즘 코딩캠프 5일차] 그래프 탐색 알고리즘: DFS, BFS (0) | 2025.02.18 |
| [알고리즘 코딩캠프 4일차] 스택, 큐, 덱, 그래프 - 인접 행렬, 인접 리스트 (0) | 2025.02.07 |
