기본 자료구조

2.1 배열 (Array)

이론

• 정의: 같은 타입의 데이터가 연속적으로 저장된 자료구조. 인덱스를 통해 접근이 빠름(O(1)).
• 특징:
  • 크기가 고정(동적 배열은 예외)
  • 삽입/삭제가 느림(O(n)), 인덱스 접근이 빠름(O(1))
• 활용: 데이터 집합 저장, 반복문과 함께 사용

실습 코딩 (Python)

# 배열 선언 및 기본 연산
arr = [10, 20, 30, 40, 50]

# 인덱스 접근
print(arr[2])  # 30 삽입 (맨 뒤에)
arr.append(60)

# 삭제 (인덱스 1의 원소 삭제)
del arr[1]

# 전체 출력
for item in arr:
    print(item)

2.2 연결 리스트 (Linked List)

이론

• 정의: 각 노드가 데이터와 다음 노드의 참조(포인터)를 가지는 자료구조.
• 특징:
  • 동적 크기, 메모리 효율적
  • 임의 접근 느림, 삽입/삭제 빠름(포인터만 조정)
• 종류: 단일/이중/원형 연결 리스트

실습 코딩 (Python, 단일 연결 리스트)

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = new_node

    def print_list(self):
        cur = self.head
        while cur:
            print(cur.data, end=' ')
            cur = cur.next
        print()

# 사용 예시
ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)
ll.print_list()  # 10 20 30

2.3 스택 (Stack) & 큐 (Queue)

이론

• 스택:
  • LIFO(Last-In, First-Out) 구조
  • 주요 연산: push(삽입), pop(삭제)
• 큐:
  • FIFO(First-In, First-Out) 구조
  • 주요 연산: enqueue(삽입), dequeue(삭제)

실습 코딩

스택 (Python)

stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())  # 3
print(stack)        # [1, 2]

큐 (Python, collections.deque 사용)

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
print(queue.popleft())  # 1
print(queue)            # deque([2, 3])

 

2.4 해시 테이블 (Hash Table)

이론

• 정의: 키(Key)에 값을 매핑하는 자료구조. 해시 함수를 사용해 인덱스 결정.
• 특징:
  • 평균적으로 삽입/삭제/탐색 O(1)
  • 충돌 발생 가능(해결법: 체이닝, 오픈 어드레싱 등)
• 활용: 사전, 집합, 캐시 등

실습 코딩 (Python dict 사용)

# 해시 테이블 = 딕셔너리
hash_table = {}
hash_table['apple'] = 100
hash_table['banana'] = 200

print(hash_table['apple'])  # 100# 키 존재 여부 확인
if 'banana' in hash_table:
    print("banana 있음")

2.5 트리 (Tree) & 그래프 (Graph)

이론

• 트리:
  • 계층적 자료구조, 루트 노드에서 시작, 부모-자식 관계
  • 이진 트리, 이진 탐색 트리(BST), 힙 등 다양한 종류
• 그래프:
  • 노드(정점)와 간선(엣지)로 구성
  • 방향/무방향, 가중치/비가중치 등 다양한 형태

실습 코딩

이진 트리 (Python)

class TreeNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# 트리 생성
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

# 중위 순회
def inorder(node):
    if node:
        inorder(node.left)
        print(node.data, end=' ')
        inorder(node.right)

inorder(root)  # 2 1 3

그래프 (인접 리스트, Python)

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1],
    4: [2]
}

# 1번 노드와 연결된 노드 출력
print(graph[1])  # [2, 3]

2.6 힙 (Heap), 우선순위 큐 (Priority Queue)

이론

• 힙:
  • 완전 이진 트리 기반, 부모 노드가 자식 노드보다 크거나(최대 힙) 작음(최소 힙)
  • 삽입/삭제 O(log n)
• 우선순위 큐:
  • 우선순위가 높은 데이터가 먼저 나오는 큐
  • 힙으로 구현하는 경우가 많음

실습 코딩 (Python heapq 모듈)

import heapq

# 최소 힙
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)
print(heapq.heappop(heap))  # 5 최대 힙 (음수로 변환하여 사용)
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -20)
print(-heapq.heappop(max_heap))  # 20