알고리즘 & 자료구조 심화 정리

목차

1. 이분탐색 (Binary Search)
2. 분할정복 (Divide and Conquer)
3. 스택 (Stack)
4. 큐 (Queue)
5. 우선순위 큐 (Priority Queue)
6. 연결 리스트 (Linked List)
7. 해시테이블 (Hash Table)

---

1. 이분탐색 (Binary Search)

개념

• 정의: 정렬된 배열에서 특정 값을 찾는 효율적인 탐색 알고리즘
• 핵심 아이디어: 탐색 범위를 반씩 줄여가며 목표값을 찾음
• 시간 복잡도: O(log n)
• 전제 조건: 배열이 정렬되어 있어야 함

시각화 예제

배열: [1, 3, 5, 7, 9, 11, 13]  target: 7

1단계: left=0, right=6, mid=3
       [1, 3, 5, 7, 9, 11, 13]
                  ↑
       arr[3] = 7 == target ✓ 찾음!

다른 예시 - target: 9
1단계: [1, 3, 5, 7, 9, 11, 13]  mid=3, arr[3]=7 < 9
                  ↑              → 오른쪽 탐색
2단계: [1, 3, 5, 7, 9, 11, 13]  mid=5, arr[5]=11 > 9  
                        ↑        → 왼쪽 탐색
3단계: [1, 3, 5, 7, 9, 11, 13]  mid=4, arr[4]=9 ✓
                     ↑

동작 원리

1. 배열의 중간 요소를 확인
2. 중간 요소가 찾는 값보다 크면 왼쪽 절반에서 탐색
3. 중간 요소가 찾는 값보다 작으면 오른쪽 절반에서 탐색
4. 값을 찾을 때까지 또는 탐색 범위가 없을 때까지 반복

장점과 단점

장점:

• 매우 빠른 탐색 속도 (O(log n))
• 메모리 효율적 (O(1) 공간 복잡도)

단점:

• 배열이 정렬되어 있어야 함
• 동적으로 변하는 데이터에는 부적합

Python 구현

def binary_search(arr, target):
    """기본 이분탐색"""
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if arr[mid] == target:
            return mid  # 찾음!
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽에서 찾기
        else:
            right = mid - 1  # 왼쪽에서 찾기
    
    return -1  # 못 찾음

# 사용 예시
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7))  # 3
print(binary_search(arr, 4))  # -1

# 파이썬 bisect 모듈 활용
import bisect
sorted_list = [1, 3, 5, 7, 9, 11, 13]
index = bisect.bisect_left(sorted_list, 7)
print(f"7의 위치: {index}")  # 3

---

2. 분할정복 (Divide and Conquer)

개념

• 정의: 큰 문제를 작은 부분 문제들로 나누어 해결하는 알고리즘 설계 기법
• 핵심 과정:
  1. 분할(Divide): 문제를 더 작은 부분 문제로 나눔
  2. 정복(Conquer): 부분 문제들을 재귀적으로 해결
  3. 결합(Combine): 부분 문제의 해를 결합하여 원래 문제의 해를 구함

시각화 예제 - 병합정렬

초기 배열: [64, 34, 25, 12, 22, 11, 90]

분할 과정:
[64, 34, 25, 12, 22, 11, 90]
       ↓ 분할
[64, 34, 25] [12, 22, 11, 90]
       ↓ 분할         ↓ 분할  
[64] [34, 25] [12, 22] [11, 90]
     ↓ 분할    ↓ 분할    ↓ 분할
[64] [34] [25] [12] [22] [11] [90]

정복(합치기) 과정:
[64] [34] [25] [12] [22] [11] [90]
     ↓ 합치기   ↓ 합치기   ↓ 합치기
[64] [25, 34] [12, 22] [11, 90]
       ↓ 합치기         ↓ 합치기
[25, 34, 64] [11, 12, 22, 90]
            ↓ 합치기
[11, 12, 22, 25, 34, 64, 90]

분할정복의 특징

• 재귀적 구조: 자기 자신을 호출하여 문제를 해결
• 최적 부분 구조: 부분 문제의 최적해가 전체 문제의 최적해에 기여
• 중복 부분 문제 없음: 각 부분 문제는 독립적

대표적인 분할정복 알고리즘

def merge_sort(arr):
    """병합정렬"""
    if len(arr) <= 1:
        return arr
    
    # 분할
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    # 합치기
    result = []
    i = j = 0
    
    # 두 배열을 비교하면서 합치기
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # 남은 요소들 추가
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def find_max(arr):
    """분할정복으로 최대값 찾기"""
    if len(arr) == 1:
        return arr[0]
    
    mid = len(arr) // 2
    left_max = find_max(arr[:mid])
    right_max = find_max(arr[mid:])
    
    return max(left_max, right_max)

# 사용 예시
numbers = [64, 34, 25, 12, 22, 11, 90]
print(merge_sort(numbers))  # [11, 12, 22, 25, 34, 64, 90]
print(find_max(numbers))    # 90

---

3. 스택 (Stack)

개념

• 정의: LIFO(Last In First Out) 원칙을 따르는 선형 자료구조
• 특징: 한 쪽 끝에서만 원소의 삽입과 삭제가 가능
• 주요 연산: push(), pop(), peek()

시각화 예제

스택 동작 과정:

초기 상태: []

push(1): [1]        ← top
push(2): [1, 2]     ← top  
push(3): [1, 2, 3]  ← top

pop():   [1, 2]     ← top (3 제거됨)
pop():   [1]        ← top (2 제거됨)

※ 스택은 접시 쌓기와 같음 - 마지막에 넣은 것이 먼저 나옴!

스택의 활용

• 함수 호출 관리: 함수 호출 스택
• 괄호 매칭: 괄호의 올바른 쌍 확인
• 웹 브라우저: 뒤로가기 기능
• 계산기: 후위 표기법 계산

Python 구현 (리스트 활용)

# 리스트를 스택으로 사용
stack = []

# 스택 연산들
def push(stack, item):
    stack.append(item)

def pop(stack):
    if stack:
        return stack.pop()
    return None

def peek(stack):
    if stack:
        return stack[-1]
    return None

def is_empty(stack):
    return len(stack) == 0

# 사용 예시
stack = []
push(stack, 1)
push(stack, 2)
push(stack, 3)
print(f"현재 스택: {stack}")        # [1, 2, 3]
print(f"peek: {peek(stack)}")       # 3
print(f"pop: {pop(stack)}")         # 3
print(f"현재 스택: {stack}")        # [1, 2]

# 괄호 매칭 예제
def check_brackets(s):
    """괄호가 올바른지 확인"""
    stack = []
    pairs = {'(': ')', '[': ']', '{': '}'}
    
    for char in s:
        if char in pairs:  # 여는 괄호
            stack.append(char)
        elif char in pairs.values():  # 닫는 괄호
            if not stack or pairs[stack.pop()] != char:
                return False
    
    return len(stack) == 0

print(check_brackets("()[]{}"))  # True
print(check_brackets("([)]"))    # False

---

4. 큐 (Queue)

개념

• 정의: FIFO(First In First Out) 원칙을 따르는 선형 자료구조
• 특징: 한 쪽 끝에서는 삽입, 다른 쪽 끝에서는 삭제가 일어남
• 주요 연산: enqueue(), dequeue()

시각화 예제

큐 동작 과정:

초기 상태: []

enqueue(1): [1]     ← rear
enqueue(2): [1, 2]  ← rear
enqueue(3): [1, 2, 3] ← rear
            ↑
           front

dequeue(): [2, 3]   ← rear (1 제거됨)
           ↑
          front

dequeue(): [3]      ← rear (2 제거됨)
           ↑
          front

※ 큐는 줄서기와 같음 - 먼저 온 사람이 먼저 나감!

큐의 활용

• BFS (너비 우선 탐색): 그래프 탐색
• 프로세스 스케줄링: 운영체제에서 프로세스 관리
• 프린터 대기열: 인쇄 작업 순서 관리

Python 구현 (deque 활용)

from collections import deque

# deque를 큐로 사용
queue = deque()

def enqueue(queue, item):
    queue.append(item)

def dequeue(queue):
    if queue:
        return queue.popleft()
    return None

def is_empty(queue):
    return len(queue) == 0

# 사용 예시
queue = deque()
enqueue(queue, 'A')
enqueue(queue, 'B')
enqueue(queue, 'C')
print(f"현재 큐: {list(queue)}")     # ['A', 'B', 'C']
print(f"dequeue: {dequeue(queue)}")  # A
print(f"현재 큐: {list(queue)}")     # ['B', 'C']

# BFS 간단 예제
def bfs_simple(graph, start):
    """간단한 BFS"""
    visited = set()
    queue = deque([start])
    result = []
    
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

# 사용 예시
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
print(bfs_simple(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']

---

5. 우선순위 큐 (Priority Queue)

개념

• 정의: 각 원소가 우선순위를 가지고 있으며, 우선순위가 높은 원소가 먼저 처리되는 자료구조
• 특징: 일반 큐와 달리 FIFO가 아닌 우선순위에 따라 처리

시각화 예제

우선순위 큐 동작 (숫자가 작을수록 우선순위 높음):

push(task1, 3): [(3, task1)]
push(task2, 1): [(1, task2), (3, task1)]  ← 우선순위 1이 앞으로
push(task3, 2): [(1, task2), (3, task1), (2, task3)]
                      ↓ 힙 정렬
                [(1, task2), (2, task3), (3, task1)]

pop(): task2 (우선순위 1)
pop(): task3 (우선순위 2)  
pop(): task1 (우선순위 3)

실제 활용: 응급실 환자 우선순위, 작업 스케줄링 등

우선순위 큐의 활용

• 다익스트라 알고리즘: 최단 경로 찾기
• 작업 스케줄링: 우선순위에 따른 작업 처리
• A* 알고리즘: 경로 탐색

Python 구현 (heapq 활용)

import heapq

# heapq를 우선순위 큐로 사용
pq = []

def push(pq, item, priority):
    """우선순위와 함께 원소 추가 (작은 값이 높은 우선순위)"""
    heapq.heappush(pq, (priority, item))

def pop(pq):
    """가장 높은 우선순위 원소 제거"""
    if pq:
        priority, item = heapq.heappop(pq)
        return item
    return None

def peek(pq):
    """가장 높은 우선순위 원소 확인"""
    if pq:
        return pq[0][1]
    return None

# 사용 예시
pq = []
push(pq, "응급환자", 1)      # 최우선
push(pq, "일반환자", 3)      # 낮은 우선순위  
push(pq, "중증환자", 2)      # 중간 우선순위

print(f"다음 환자: {pop(pq)}")  # 응급환자
print(f"다음 환자: {pop(pq)}")  # 중증환자
print(f"다음 환자: {pop(pq)}")  # 일반환자

# 최대 힙 (큰 값이 우선순위 높음)
max_heap = []
def push_max(heap, item):
    heapq.heappush(heap, -item)  # 음수로 변환

def pop_max(heap):
    if heap:
        return -heapq.heappop(heap)  # 다시 양수로
    return None

# 다익스트라 간단 예제  
def dijkstra_simple(graph, start):
    """간단한 다익스트라"""
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    
    while pq:
        current_dist, current = heapq.heappop(pq)
        
        if current_dist > distances[current]:
            continue
            
        for neighbor, weight in graph.get(current, []):
            distance = current_dist + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

---

6. 연결 리스트 (Linked List)

개념

• 정의: 노드들이 포인터로 연결된 선형 자료구조
• 구성 요소: 데이터 + 다음 노드 포인터

시각화 예제

연결 리스트 구조:

[데이터1] → [데이터2] → [데이터3] → None
   ↑           ↑           ↑
  노드1       노드2       노드3

삽입 과정:
기존: A → B → C → None
새 노드 X를 B 다음에 삽입:
결과: A → B → X → C → None

삭제 과정:  
기존: A → B → C → None
B 삭제:
결과: A → C → None (B의 연결을 끊고 A가 C를 직접 가리킴)

배열 vs 연결 리스트

특성	배열	연결 리스트
접근 시간	O(1)	O(n)
삽입/삭제	O(n)	O(1)
메모리 사용	연속적	비연속적

Python 구현 (딕셔너리 활용)

# 딕셔너리로 간단한 연결 리스트 구현
def create_linked_list():
    """연결 리스트 생성"""
    return {'head': None, 'nodes': {}}

def add_node(ll, node_id, data):
    """노드 추가"""
    ll['nodes'][node_id] = {'data': data, 'next': None}
    
    if ll['head'] is None:
        ll['head'] = node_id

def connect_nodes(ll, from_node, to_node):
    """노드 연결"""
    if from_node in ll['nodes']:
        ll['nodes'][from_node]['next'] = to_node

def traverse(ll):
    """연결 리스트 순회"""
    result = []
    current = ll['head']
    
    while current is not None:
        result.append(ll['nodes'][current]['data'])
        current = ll['nodes'][current]['next']
    
    return result

# 사용 예시
ll = create_linked_list()
add_node(ll, 'node1', 'A')
add_node(ll, 'node2', 'B') 
add_node(ll, 'node3', 'C')

connect_nodes(ll, 'node1', 'node2')
connect_nodes(ll, 'node2', 'node3')

print(traverse(ll))  # ['A', 'B', 'C']

# 리스트로 연결 리스트 시뮬레이션
def reverse_list(arr):
    """배열을 이용한 연결 리스트 뒤집기"""
    return arr[::-1]

def insert_at_position(arr, pos, value):
    """특정 위치에 삽입"""
    return arr[:pos] + [value] + arr[pos:]

def delete_at_position(arr, pos):
    """특정 위치 삭제"""
    return arr[:pos] + arr[pos+1:]

# 연결 리스트 활용 예제
numbers = ['A', 'B', 'C', 'D']
print(f"원본: {numbers}")
print(f"뒤집기: {reverse_list(numbers)}")
print(f"1번 위치에 X 삽입: {insert_at_position(numbers, 1, 'X')}")
print(f"2번 위치 삭제: {delete_at_position(numbers, 2)}")

---

7. 해시테이블 (Hash Table)

개념

• 정의: 키-값 쌍을 저장하는 자료구조로, 해시 함수를 사용하여 키를 배열의 인덱스로 변환
• 핵심: 빠른 검색, 삽입, 삭제 (평균 O(1))

시각화 예제

해시테이블 동작 과정:

해시 함수: hash(key) % 5

삽입:
"apple" → hash("apple") % 5 = 2  →  [0: , 1: , 2: apple, 3: , 4: ]
"banana" → hash("banana") % 5 = 1 → [0: , 1: banana, 2: apple, 3: , 4: ]
"orange" → hash("orange") % 5 = 2 → 충돌! 체이닝으로 해결
                                   [0: , 1: banana, 2: [apple, orange], 3: , 4: ]

검색:
"apple" → hash("apple") % 5 = 2 → 인덱스 2에서 찾음 ✓

해시테이블의 활용

• 딕셔너리/맵: 키-값 매핑
• 중복 제거: Set 자료구조
• 캐싱: 계산 결과 저장
• 데이터베이스 인덱싱: 빠른 검색

Python 구현 (딕셔너리 활용)

# 파이썬 딕셔너리는 해시테이블 구현체
hash_table = {}

def put(ht, key, value):
    """키-값 쌍 추가"""
    ht[key] = value

def get(ht, key):
    """키로 값 찾기"""
    return ht.get(key, None)

def delete(ht, key):
    """키-값 쌍 삭제"""
    if key in ht:
        del ht[key]
        return True
    return False

# 사용 예시
ht = {}
put(ht, "name", "Alice")
put(ht, "age", 25)
put(ht, "city", "Seoul")

print(f"이름: {get(ht, 'name')}")  # Alice
print(f"나이: {get(ht, 'age')}")   # 25
print(f"전체: {ht}")

# Counter를 이용한 빈도 계산
from collections import Counter

def count_frequency(text):
    """문자 빈도 계산"""
    return Counter(text)

text = "hello world"
freq = count_frequency(text)
print(f"문자 빈도: {freq}")  # Counter({'l': 3, 'o': 2, 'h': 1, ...})

# 활용 예제들
def two_sum(nums, target):
    """두 수의 합 찾기"""
    seen = {}
    
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    
    return []

def group_anagrams(words):
    """애너그램 그룹 찾기"""
    groups = {}
    
    for word in words:
        # 정렬된 문자열을 키로 사용
        key = ''.join(sorted(word))
        if key not in groups:
            groups[key] = []
        groups[key].append(word)
    
    return list(groups.values())

# 사용 예시
print(two_sum([2, 7, 11, 15], 9))  # [0, 1]
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

# Set 활용 (해시테이블 기반)
def find_duplicates(arr):
    """중복 요소 찾기"""
    seen = set()
    duplicates = set()
    
    for item in arr:
        if item in seen:
            duplicates.add(item)
        else:
            seen.add(item)
    
    return list(duplicates)

print(find_duplicates([1, 2, 3, 2, 4, 3, 5]))  # [2, 3]

---

정리

자료구조 선택 가이드

용도	추천 자료구조	파이썬 구현	이유
빠른 검색	해시테이블	dict, set	O(1) 평균 시간
정렬된 데이터 검색	이분탐색	bisect 모듈	O(log n) 시간
되돌리기 기능	스택	list	LIFO 특성
대기열 처리	큐	deque	FIFO 특성
우선순위 작업	우선순위 큐	heapq	우선순위에 따른 처리
동적 크기 조절	연결 리스트	list	효율적인 삽입/삭제

간단한 성능 비교

자료구조	검색	삽입	삭제	파이썬
배열	O(n)	O(n)	O(n)	list
해시테이블	O(1)	O(1)	O(1)	dict
스택	O(n)	O(1)	O(1)	list
큐	O(n)	O(1)	O(1)	deque
우선순위 큐	O(n)	O(log n)	O(log n)	heapq

`