[CS] 자료구조 - 스택, 큐, 트리, 힙

1. 스택

- 후입선출: 마지막에 넣은 데이터가 가장 먼저 나옴

- 활용: 재귀 호출, 괄호 짝 맞추기, DFS 등

- 주요 연산

# 가장 흔한 방법
stack = []
stack.append(10)
top = stack.pop()

2. 큐

- 선입선출: 먼저 들어간 데이터가 먼저 나옴

- 활용: BFS, 캐시, 작업 예약 처리에 사용

- collections.deque: 가장 빠르고 많이 쓰임

- queue.Queue: 스레드 안전(멀티스레스 환경용)

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
x = queue.popleft()

print(queue) # [2]

 

3. 트리

- 계층적 자료 구조. 노드와 간선으로 구성된 비순환 그래프

- 이진트리: 자식이 최대 2개

- 이진탐색트리: 왼쪽 < 부모 < 오른쪽

1) 전위순회: 루트 → 왼 → 오

2) 중위순회: 왼 → 루트 → 오

3) 후위순회: 왼 → 오 → 루트

4) 레벨 순회: BFS

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def preorder(node):
    if node:
        print(node.value, end=' ')
        preorder(node.left)
        preorder(node.right)

def inorder(node):
    if node:
        inorder(node.left)
        print(node.value, end=' ')
        inorder(node.right)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.value, end=' ')
        
# 트리 구조
#       1
#      / \
#     2   3
#    / \
#   4   5

tree = Node(1,
            Node(2, Node(4), Node(5)),
            Node(3))

print("Preorder:")
preorder(tree)     # 1 2 4 5 3

print("\nInorder:")
inorder(tree)      # 4 2 5 1 3

print("\nPostorder:")
postorder(tree)    # 4 5 2 3 1

4. 힙

1) 최소 힙 : 부모 <= 자식 → 루트가 최솟값

2) 최대 힙: 부모 >= 자식  → 루트가 최댓값

- 부모 노드의 index가 n일때, 왼쪽 자식의 인덱스는 2n, 오른쪽자식의 인덱스는 2n+1

- 모든 정수를 힙에 입력하는 연산: O(n log n)

- 힙에서 모든 정수를 출력하는 연산: O(n log n)

- 시간복잡도: 삽입, 삭제 O(log n) : 완전 이진트리의 높이는 log2(n)이기 때문

* heapq.heappush()는 새로운 원소를 리스트 맨 끝에 추가(O(1)), 그다음 부모 노드와 비교하면서 위로 올라감 => 최대 트리의 높이 만큼 이동 => O(log n)

** 완전이진트리 : 모든 레벨이 왼쪽부터 차족차족 채워진 트리

*** 트리의 높이: 루트에서 가장 아래 노드까지의 거리(레벨 수)

**** 레벨(깊이): 루트로부터의 거리, 루트는 0부터 시작

        A         → level 0 / depth 0 / height 2
      /   \         레벨 0 (2^0 = 최대 1개 노드)
     B     C      → level 1 / depth 1 / height 1, 0
    / \             레벨 1 (2^1 = 최대 2개 노드)
   D   E          → level 2 / depth 2 / height 0
                    레벨 2 (2^2 = 최대 4개 노드 가능)
                    
                    => 총 레벨2 => 총 2^2+1 -1 =7개 노드 가능

- 높이가 h인 완전 이진 트리의 최대 노드 수 : 2^h+1 -1

- 최솟값/최댓값 확인: O(1)

- 리스트 → 힙으로 변환: O(n)

* heapq는 완전 이진트리기반 최소 힙 구조(루트에 최소값 보장)

** 리프 노드는 자식이 없기 때문에 힙 조건을 따질 필요 없어 밑에서 부터 위로 수정(위에서부터하면 밑에 계속 수정해야함, 비효율적)

import heapq

nums =  [33, 48, 6, 16, 8]
heapq.heapify(nums) # 최소힙

#        33
#       /  \
#     48    6
#    /  \
#  16    8 # 리프노드에서 시작

#        33
#       /  \
#     8     6  # 부모 확인
#    /  \
#  16   48

#        6
#       /  \
#     8     33
#    /  \
#  16   48

print(nums)
print(type(nums))

# [6,8,33,16,48]

 

*** 점토 합치기 => 합친 결과도 다시 계산에 포함시켜야 하므로 최소힙! => 데이터 압축할 때 (허프만 코딩)

=> 항상 작은 두 개를 먼저 합쳐야 총합이 최소가 된다.

* 허프만코딩: 자주 나오는 문자를 짧은 이진코드로, 덜 나오는 문자를 긴코드로 바꿔 전체 데이터를 압축하는 알고리즘, 덜 나오는 두 문자부터 합쳐 이진트리를 만들고, 경로를 따라 각 문제 고유한 코드(0과 1)를 부여한다.

 

1) [5,8,9,10]  => 오름차순정렬

- 5+8 =13

-13+9=22

-22+10 =32

- 13+22+32 = 67

 

2) [5,8,9,10] => 최소힙정렬

- 5+8 = 13

- 9+10 = 19

- 13+19 = 32

- 13+19+32 = 64

* 힙 구조 시각화: https://www.cs.usfca.edu/~galles/visualization/Heap.html