알고리즘 기초 2
목차
1. 연결리스트(이전 글)
2.스택(이전 글)
3.큐(이전 글)
4.해시테이블(이전 글)
5. 트리
6. 힙
5-1. 트리
선형 구조: 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태의 자료구조. 큐(Queue), 스택(Stack)
비선형 구조: 데이터가 계층적 혹은 망으로 구성됨. 트리(Tree)
선형구조와 비선형구조의 차이점은 형태뿐만 아니라 용도에서도 차이점이 있음. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰짐.
Node: 트리에서 데이터를 저장하는 기본 요소 (A, B, C, D, ... , J)
Root Node: 트리 맨 위에 있는 노드 (A)
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 (level 0, level 1 ...)
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드(D는 H, I의 Parent Node)
Child Node: 어떤 노드의 하위 레벨에 연결된 노드(H, I는 D의 Child Node)
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드(H, I, J, F, G)
Sibling: 동일한 Parent Node를 가진 노드(F와 G, D와 E, B와 C, H와 I)
Depth: 트리에서 Node가 가질 수 있는 최대 Level(level 3)
5-2 이진트리: 각 노드가 자식을 최대 두 개만 가질 수 있는 트리( 0, 1, 2 개)
o Level 0 # -> 자식이 세 명이라고? 삼형제는 아니된다.
o o o Level 1
o o o Level 2 # 이진 트리(X)
o Level 0
o o Level 1
o o o Level 2 # 이진 트리(O)
5-3 완전 이진트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 함.
o Level 0
o o Level 1
o o Level 2 # -> 이진 트리 O 완전 이진 트리 X(맨 왼쪽이 비어있음)
o Level 0
o o Level 1
o o o Level 2 # -> 이진 트리 O 완전 이진 트리 O
완전 이진트리에 한 해 배열로 표현 가능함.(접근성이 용이함)
왼쪽부터 데이터가 쌓이는 속성을 이용해, 데이터를 순서대로 배열에 쌓으면서 표현
완전 이진트리 배열 구현
트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않음
그래서 None 값을 배열에 넣고 시작 [None]
8 Level 0 -> [None, 8] 첫번째 레벨의 8
6 3 Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3
4 2 5 Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 배열에 넣음
[None, 8, 6, 3, 4, 2, 5] 라는 배열에서 트리로 분석하는 방법
1. 현재 인덱스 * 2 -> 왼쪽 자식의 인덱스
2. 현재 인덱스 * 2 + 1 -> 오른쪽 자식의 인덱스
3. 현재 인덱스 // 2 -> 부모의 인덱스
예를 들어, 1번째 인덱스인 8을 부모로 보면: 왼쪽 자식은 6, 오른쪽 자식은 3
(자식 6): 1 * 2 = 2번째 인덱스-> (자식 6)
(자식 3): 1 * 2 + 1 = 3번째 인덱스-> (자식 3)
(부모 8): 3 // 2 = 1번째 인덱스-> (부모 8)
이를 다시 생각해보면
[None, 8, 6, 3, 4, 2, 5] 는
8 밑에 6, 3 이 있고, 6, 3 밑에 4, 2, 5가 있는 완전 이진 트리임을 알 수 있음.
트리의 높이(Height): 루트 노드부터 가장 아래 리프 노드까지의 길이
트리 높이
o Level 0 # 루트 노드
o o Level 1
o o o Level 2 # 가장 아래 리프 노드
이 트리의 높이? 2 - 0 = 2
각 Level이 꽉 찬 이진트리 높이
1 Level 0 -> 1개
2 3 Level 1 -> 2개
4 5 6 7 Level 2 -> 4개
8 9....... 14 15 Level 3 -> 8개
Level k -> 2^k 개
높이가 h 인데 모든 노드가 꽉 차 있는 완전 이진 트리라면 모든 노드의 개수는
1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h
= 2^(h+1) - 1
즉, 높이가 h 일 때 최대 노드의 개수는 2^(h+1) -1, 이 최대 노드의 개수를 N이라 할 때,
2^(h+1) -1 = N
→
h = log_2(N+1)-1
완전 이진 트리 노드의 개수가 N일 때 최대 높이는 log_2(N+1) - 1
따라서, 이진 트리의 높이의 최대는 O(log(N)) ▶ Big O표기에선 상수 무시.
*요약*
완전 이진 트리에서, 노드의 최대 개수가 N, 최대 높이를 h라 할 때
N = 2^(h+1) - 1
h = O(log(N))
6. 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
최대/최소의 값들이 필요한 연산이 있다면 힙을 사용.
힙 자료구조 예
8 Level 0
6 3 Level 1
2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X이므로, 힙X
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O
4 2 1 Level 2 # 모든 부모 노드의 값이 자식 노드보다 큼. 힙O
8 Level 0
6 (3) Level 1 # -> 이진 트리 O 완전 이진 트리 O
4 2 (5) Level 2 # 부모 노드의 값이 자식 노드보다 모두 큰 것은 아님. 힙X
최대 힙(Max Heap): 최댓값이 맨 위인 힙
최소 힙(Min Heap): 최솟값이 맨 위인 힙
- BST(이진탐색트리)와 다름. 좌, 우 자식의 위치(Siblings)가 대소관계를 반영하지 않음
- 마찬가지러 계산 편의를 위해 인덱스는 1부터 사용. (parent: x, left: 2x, right: 2x+1)
최대 힙 노드삽입 알고리즘:
1. 원소를 맨 마지막에 삽입
2. 그 자리의 부모 노드와 비교. 만약 더 크다면 자리를 바꿈
3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복아래와 같은 맥스 힙에서 9를 추가한다면,
8 Level 0
6 3 Level 1
4 2 1 Level 2
1. 맨 마지막에 원소를 삽입
8 Level 0
6 3 Level 1
4 2 1 9 Level 2
2-1. 부모 노드와 비교. 3보다 9가 큼으로, 둘의 자리 변경
8 Level 0
6 3 Level 1
4 2 1 9 Level 2
8 Level 0
6 9 Level 1
4 2 1 3 Level 2
2-2. 다시 부모 노드와 비교. 8보다 9가 더 큼으로, 둘의 자리 변경
8 Level 0
6 9 Level 1
4 2 1 3 Level 2
9 Level 0
6 8 Level 1
4 2 1 3 Level 2
3. 가장 위에 도달했으므로 멈춤.
9 Level 0
6 8 Level 1
4 2 1 3 Level 2
최대힙 노드삽입의 시간복잡도: 맨 밑부터 꼭대기까지 비교하면서 올리고 있음. 반복 최대 횟수는 최대 높이와 동일
O(log(N))
최대 힙 노드삽입코드
class BinaryMaxHeap:
def __init__(self):
# 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용하기에 0번째 인덱스에 None을 넣음
self.items = [None]
def insert(self, k):
#맨 마지막에 노드 추가
self.items.append(k)
#비교 함수
self._percolate_up()
def _percolate_up(self):
# percolate: 스며들다.
#cur 변수는 마지막에 새로 넣은 노드의 인덱스
cur = len(self.items) - 1
# left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
parent = cur // 2
# parent가 1일때 root Node
while parent > 0:
if self.items[cur] > self.items[parent]:
#두 변수의 값을 바꾸는 문장
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
cur = parent
parent = cur // 2
최대 힙 원소추출 알고리즘:
- 최댓값은 루트 노드 삭제(최댓값이 들어있으니까)를 통해 루트 노드의 원소를 추출할 수 있음.
- 스택과 같이 맨 위에 있는 원소만 제거 가능함(다른 위치의 노드를 삭제할 수는 없음).
- 맥스 힙에 원소를 추가했던 것과 마찬가지로 원소를 삭제할때도 힙의 규칙이 지켜져야 함.
1. 루트노드와 마지막 노드를 교환
2. 마지막 노드 원소 저장 및 제거
3. 교환된 루트노드의 크기를 자식들과 비교
4. 자식과 부모 교환. 힙 규칙이 적요 될때까지 3->4 반복이 맥스 힙에서 원소를 추출 (항상 맨 위의 루트 노드 제거)
8 Level 0
6 7 Level 1
2 5 4 3 Level 2
1. 루트 노드와 맨 끝에 있는 원소를 교체
8 Level 0
6 7 Level 1
2 5 4 3 Level 2
3 Level 0
7 6 Level 1
2 5 4 8 Level 2
2. 맨 뒤에 있는 원소를 삭제
이 값이 기존 맥스힙에 있던 가장 큰 값이므로 이 값을 마지막에 반환
3 Level 0
6 7 Level 1
2 5 4 X Level 2
3-1. 변경된 노드를 더 큰 자식 노드와 비교
우선 부모와 왼쪽 자식을 비교. 그리고 부모와 오른쪽 자식을 비교
그리고 부모보다 큰 자식 중, 더 큰 자식과 변경
왼쪽 자식인 6과 오른쪽 자식인 7 중에서 7이 더 크고, 부모인 3보다 크니까 7과 3의 자리를 변경
3 Level 0
6 7 Level 1
2 5 4 Level 2
7 Level 0
6 3 Level 1
2 5 4 Level 2
3-2. 다시 자식 노드와 비교
우선 부모와 왼쪽 자식을 비교(우측 자식 없으므로 생략)
왼쪽 자식인 4는 부모인 3보다 더 크니까 둘의 자리를 변경
7 Level 0
6 3 Level 1
2 5 4 Level 2
7 Level 0
6 4 Level 1
2 5 3 Level 2
4. 가장 아래 레벨에 도달했으므로 멈춤. 힙의 특성을 그대로 유지해 데이터를 삭제함.
7 Level 0
6 4 Level 1
2 5 3 Level 2
5. 제거한 원래 루트 노드, 8을 반환최대힙 원소추출의 시간복잡도: 루트 노드를 마지막 노드와 바꾸어 맨 밑부터 꼭대기까지 비교하면서 올리고 있음.
반복 최대 횟수는 최대 높이와 동일.
O(log(N))
최대 힙 노드의 원소 추출코드
class BinaryMaxHeap:
def __init__(self):
# 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
self.items = [None]
def insert(self, k):
self.items.append(k)
self._percolate_up()
def _percolate_up(self):
# percolate: 스며들다.
cur = len(self.items) - 1
# left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
parent = cur // 2
while parent > 0:
if self.items[cur] > self.items[parent]:
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
cur = parent
parent = cur // 2
#------------------------ 여기부터 --------------------------------
#값 추출하는 함수
def extract(self):
#힙에 아무것도 없다면 반환값 없음
if len(self.items) - 1 < 1:
return None
#root라는 빈 변수를 만들어 힙의 루트노드를 저장
root = self.items[1]
#힙의 마지막 노드를 루트노드에 저장
self.items[1] = self.items[-1]
#마지막거를 뽑음
self.items.pop()
#힙 정리 함수
self._percolate_down(1)
return root
def _percolate_down(self, cur):
#biggest는 현재 부모노드를 저장
biggest = cur
left = 2 * cur
right = 2 * cur + 1
#인덱스 접근이 배열의 크기를 넘어가면 안되기 때문에 앞에 제약을 검.
#왼쪽 자식노드가 부모노드보다 크면 biggest를 왼쪽 자식으로 바꿈
if left <= len(self.items) - 1 and self.items[left] > self.items[biggest]:
biggest = left
#오른쪽 자식노드가 부모노드보다 크면 biggest를 오른쪽 자식으로 바꿈
if right <= len(self.items) - 1 and self.items[right] > self.items[biggest]:
biggest = right
#왼쪽이나 오른쪽 자식 노드로 바뀐거면, 위의 문장을 다시 실행해야함. 안바뀐거면 힙 정리가 끝난 상태여서 건들지 않아도 됨.
if biggest != cur:
self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
self._percolate_down(biggest)----------------------------------------------------------
나만의 필수암기노트
파이썬 pprint: json파일이나 디렉토리를 접근할때 이쁘게 출력함.
'알고리즘' 카테고리의 다른 글
| 알고리즘 2 (BFS, 백 트래킹, 이진탐색) (1) | 2024.06.17 |
|---|---|
| 알고리즘 1 (그래프, DFS) (0) | 2024.06.14 |
| DFS 문제(섬의 개수 구하기) (2) | 2024.06.14 |
| 자료구조 종류1 (연결리스트, 스택, 큐, 해시테이블) (0) | 2024.06.12 |
| O(n)에서 O(n^2)인 약수의 개수 구하기 예 (0) | 2024.06.12 |