1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def merge_sort(arr):
    """병합 정렬: 분할 정복으로 리스트를 정렬한다. 최선/평균/최악 모두 O(n log n)이다."""
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)


def _merge(left, right):
    """정렬된 두 리스트를 하나의 정렬된 리스트로 합친다 (O(n))."""
    merged = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1

    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


if __name__ == "__main__":
    data = [5, 2, 9, 1, 5, 6]
    print(merge_sort(data))  # [1, 2, 5, 5, 6, 9]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def quick_sort(arr):
    """퀵 정렬: 피벗 기준으로 분할해 정렬한다. 평균 O(n log n), 최악 O(n^2)."""
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]

    return quick_sort(left) + middle + quick_sort(right)


if __name__ == "__main__":
    data = [5, 2, 9, 1, 5, 6]
    print(quick_sort(data))  # [1, 2, 5, 5, 6, 9]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import random
import timeit


def compare_sorting_performance():
    """정렬 함수 3종의 실행 시간을 비교한다."""
    data = [random.randint(1, 100_000) for _ in range(5_000)]

    results = {
        "merge_sort": timeit.timeit(lambda: merge_sort(data.copy()), number=5),
        "quick_sort": timeit.timeit(lambda: quick_sort(data.copy()), number=5),
        "sorted (Timsort)": timeit.timeit(lambda: sorted(data), number=5),
    }

    for name, elapsed in sorted(results.items(), key=lambda x: x[1]):
        print(f"{name}: {elapsed:.4f}초 (5회 합산)")


if __name__ == "__main__":
    compare_sorting_performance()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def binary_search(arr, target):
    """정렬된 리스트에서 이진 탐색으로 target의 인덱스를 찾는다 (O(log n))."""
    left, right = 0, 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


if __name__ == "__main__":
    numbers = [1, 3, 5, 7, 9, 11, 13]
    print(binary_search(numbers, 7))   # 3
    print(binary_search(numbers, 4))   # -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import bisect


def bisect_search(arr, target):
    """bisect 모듈로 target의 존재 여부와 삽입 위치를 함께 찾는다."""
    index = bisect.bisect_left(arr, target)
    found = index < len(arr) and arr[index] == target
    return index, found


if __name__ == "__main__":
    numbers = [1, 3, 5, 7, 9, 11, 13]
    print(bisect_search(numbers, 7))   # (3, True)
    print(bisect_search(numbers, 4))   # (2, False), 4는 5 앞자리에 들어가야 함

    bisect.insort(numbers, 4)          # 정렬 상태를 유지하며 삽입
    print(numbers)                     # [1, 3, 4, 5, 7, 9, 11, 13]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

class Node:
    """연결 리스트의 노드: 값과 다음 노드에 대한 참조를 가진다."""
    def __init__(self, value):
        self.value = value
        self.next = None


class SinglyLinkedList:
    """단방향 연결 리스트: 앞쪽 삽입/삭제는 O(1), 탐색/뒤쪽 삽입은 O(n)이다."""

    def __init__(self):
        self.head = None
        self._size = 0

    def __len__(self):
        return self._size

    def prepend(self, value):
        """맨 앞에 노드를 추가한다 (O(1))."""
        node = Node(value)
        node.next = self.head
        self.head = node
        self._size += 1

    def append(self, value):
        """맨 뒤에 노드를 추가한다 (O(n), 꼬리 포인터가 없어 순회가 필요하다)."""
        node = Node(value)
        if self.head is None:
            self.head = node
        else:
            current = self.head
            while current.next is not None:
                current = current.next
            current.next = node
        self._size += 1

    def find(self, value):
        """값을 순차 탐색해 인덱스를 반환한다 (O(n))."""
        current = self.head
        index = 0
        while current is not None:
            if current.value == value:
                return index
            current = current.next
            index += 1
        return -1

    def delete(self, value):
        """첫 번째로 일치하는 값을 가진 노드를 삭제한다 (O(n))."""
        if self.head is None:
            return False
        if self.head.value == value:
            self.head = self.head.next
            self._size -= 1
            return True

        current = self.head
        while current.next is not None:
            if current.next.value == value:
                current.next = current.next.next
                self._size -= 1
                return True
            current = current.next
        return False

    def to_list(self):
        """디버깅용: 파이썬 리스트로 변환한다."""
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result


if __name__ == "__main__":
    ll = SinglyLinkedList()
    ll.append(1)
    ll.append(2)
    ll.prepend(0)
    print(ll.to_list())   # [0, 1, 2]
    print(ll.find(2))     # 2
    ll.delete(1)
    print(ll.to_list())   # [0, 2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

from collections import deque
import time


class Stack:
    """스택: LIFO. list.append/pop은 둘 다 끝에서 동작해 O(1)이다."""

    def __init__(self):
        self._items = []

    def push(self, item):
        self._items.append(item)

    def pop(self):
        if not self._items:
            raise IndexError("빈 스택에서 pop을 호출했다")
        return self._items.pop()

    def peek(self):
        return self._items[-1]

    def is_empty(self):
        return len(self._items) == 0


class ListQueue:
    """list로 구현한 큐: dequeue가 pop(0)이라 앞의 모든 요소를 당겨야 해 O(n)이다."""

    def __init__(self):
        self._items = []

    def enqueue(self, item):
        self._items.append(item)      # O(1)

    def dequeue(self):
        return self._items.pop(0)     # O(n), 비효율적

    def is_empty(self):
        return len(self._items) == 0


class DequeQueue:
    """collections.deque로 구현한 큐: 양쪽 끝 모두 O(1)이다."""

    def __init__(self):
        self._items = deque()

    def enqueue(self, item):
        self._items.append(item)       # O(1)

    def dequeue(self):
        return self._items.popleft()   # O(1)

    def is_empty(self):
        return len(self._items) == 0


def compare_queue_performance(n=20_000):
    """list 기반 큐와 deque 기반 큐의 dequeue 성능을 비교한다."""
    list_queue = ListQueue()
    deque_queue = DequeQueue()
    for i in range(n):
        list_queue.enqueue(i)
        deque_queue.enqueue(i)

    start = time.perf_counter()
    while not list_queue.is_empty():
        list_queue.dequeue()
    list_time = time.perf_counter() - start

    start = time.perf_counter()
    while not deque_queue.is_empty():
        deque_queue.dequeue()
    deque_time = time.perf_counter() - start

    print(f"list 기반 큐: {list_time:.4f}초")
    print(f"deque 기반 큐: {deque_time:.4f}초 (약 {list_time / deque_time:.0f}배 빠름)")


if __name__ == "__main__":
    compare_queue_performance()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

class BSTNode:
    """이진 탐색 트리의 노드."""
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BinarySearchTree:
    """이진 탐색 트리: 왼쪽 < 루트 < 오른쪽 불변식을 유지한다. 평균 O(log n), 편향 시 최악 O(n)."""

    def __init__(self):
        self.root = None

    def insert(self, value):
        if self.root is None:
            self.root = BSTNode(value)
            return
        self._insert(self.root, value)

    def _insert(self, node, value):
        if value < node.value:
            if node.left is None:
                node.left = BSTNode(value)
            else:
                self._insert(node.left, value)
        else:
            if node.right is None:
                node.right = BSTNode(value)
            else:
                self._insert(node.right, value)

    def search(self, value):
        return self._search(self.root, value)

    def _search(self, node, value):
        if node is None:
            return False
        if node.value == value:
            return True
        if value < node.value:
            return self._search(node.left, value)
        return self._search(node.right, value)

    def inorder(self):
        """중위 순회: 오름차순으로 정렬된 값을 반환한다."""
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node is None:
            return
        self._inorder(node.left, result)
        result.append(node.value)
        self._inorder(node.right, result)


if __name__ == "__main__":
    bst = BinarySearchTree()
    for value in [5, 3, 8, 1, 4, 7, 9]:
        bst.insert(value)

    print(bst.inorder())   # [1, 3, 4, 5, 7, 8, 9]
    print(bst.search(7))   # True
    print(bst.search(6))   # False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def is_balanced(expression):
    """괄호 짝이 맞는지 스택으로 검사한다. 여는 괄호는 push, 닫는 괄호는 짝을 pop해서 확인한다."""
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []

    for char in expression:
        if char in "([{":
            stack.append(char)
        elif char in ")]}":
            if not stack or stack.pop() != pairs[char]:
                return False

    return not stack


if __name__ == "__main__":
    print(is_balanced("(a[b]{c})"))   # True
    print(is_balanced("(a[b)c]"))     # False, 괄호가 교차됨
    print(is_balanced("((a)"))        # False, 짝이 부족함

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

from collections import deque


def bfs(graph, start):
    """인접 리스트로 표현된 그래프를 너비 우선 탐색한다 (O(V + E))."""
    visited = {start}
    order = []
    queue = deque([start])

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


if __name__ == "__main__":
    graph = {
        "A": ["B", "C"],
        "B": ["A", "D"],
        "C": ["A", "D"],
        "D": ["B", "C", "E"],
        "E": ["D"],
    }
    print(bfs(graph, "A"))   # ['A', 'B', 'C', 'D', 'E']

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import heapq


def dijkstra(graph, start):
    """가중치 그래프에서 start로부터 각 노드까지의 최단 거리를 구한다 (O((V+E) log V))."""
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_dist, node = heapq.heappop(pq)
        if current_dist > distances[node]:
            continue  # 이미 더 짧은 경로로 처리된 노드는 건너뛴다

        for neighbor, weight in graph[node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances


if __name__ == "__main__":
    weighted_graph = {
        "A": [("B", 4), ("C", 1)],
        "B": [("D", 1)],
        "C": [("B", 2), ("D", 5)],
        "D": [],
    }
    print(dijkstra(weighted_graph, "A"))   # {'A': 0, 'B': 3, 'C': 1, 'D': 4}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def coin_change(coins, amount):
    """최소 동전 개수 문제를 타뷸레이션(상향식 DP)으로 푼다 (O(amount * len(coins)))."""
    dp = [0] + [float("inf")] * amount

    for target in range(1, amount + 1):
        for coin in coins:
            if coin <= target and dp[target - coin] + 1 < dp[target]:
                dp[target] = dp[target - coin] + 1

    return dp[amount] if dp[amount] != float("inf") else -1


if __name__ == "__main__":
    print(coin_change([1, 3, 4], 6))   # 2, (3 + 3)
    print(coin_change([2], 3))         # -1, 홀수 금액은 짝수 동전으로 불가능

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

from collections import defaultdict


class SearchEngine:
    """단어-문서 역색인을 만들어 다중 단어 AND 검색을 지원하는 간이 검색 엔진."""

    def __init__(self):
        self.index = defaultdict(set)
        self.documents = {}

    def add_document(self, doc_id, text):
        """문서를 색인에 추가한다. 단어별로 문서 ID 집합을 유지한다."""
        self.documents[doc_id] = text
        for word in set(text.lower().split()):
            self.index[word].add(doc_id)

    def search(self, query):
        """공백으로 구분된 모든 단어를 포함하는 문서 ID를 교집합으로 찾는다."""
        words = query.lower().split()
        if not words:
            return set()

        result = self.index.get(words[0], set()).copy()
        for word in words[1:]:
            result &= self.index.get(word, set())
        return result


if __name__ == "__main__":
    engine = SearchEngine()
    engine.add_document(1, "python is a great programming language")
    engine.add_document(2, "java is also a programming language")
    engine.add_document(3, "python is easy to learn")

    print(engine.search("python programming"))    # {1}
    print(engine.search("programming language"))  # {1, 2}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

import heapq


def shortest_path(graph, start, end):
    """다익스트라로 최단 거리와 실제 경로를 함께 구한다."""
    distances = {node: float("inf") for node in graph}
    previous = {node: None for node in graph}
    distances[start] = 0
    pq = [(0, start)]

    while pq:
        current_dist, node = heapq.heappop(pq)
        if node == end:
            break
        if current_dist > distances[node]:
            continue

        for neighbor, weight in graph[node]:
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = node
                heapq.heappush(pq, (distance, neighbor))

    if distances[end] == float("inf"):
        return None, float("inf")

    path = []
    node = end
    while node is not None:
        path.append(node)
        node = previous[node]
    path.reverse()

    return path, distances[end]


if __name__ == "__main__":
    city_map = {
        "서울": [("대전", 140), ("강릉", 200)],
        "대전": [("서울", 140), ("대구", 150)],
        "강릉": [("서울", 200), ("대구", 220)],
        "대구": [("대전", 150), ("강릉", 220), ("부산", 90)],
        "부산": [("대구", 90)],
    }
    path, distance = shortest_path(city_map, "서울", "부산")
    print(f"경로: {' -> '.join(path)}, 총 거리: {distance}km")
    # 경로: 서울 -> 대전 -> 대구 -> 부산, 총 거리: 380km