Python 알고리즘 & 자료구조 완벽 가이드

📌 들어가며

1. 파이썬의 기본 객체 철학

1.1 객체 (Object)

1.2 컨테이너 (Container)와 시퀀스 (Sequence)

• 예시: list, tuple, dict, set

• 유용한 컨테이너들: collections 모듈의 deque, defaultdict, Counter

• 특징: 인덱스로 특정 위치에 접근하거나 슬라이싱으로 잘라낼 수 있습니다

• 예시: list, tuple, str

1.3 Iterable과 Iterator

• *Iterable (반복 가능한 객체)**는 for문으로 하나씩 요소를 꺼낼 수 있는 모든 객체입니다. 책 전체를 생각하면 이해하기 쉽습니다.

• 예시: 리스트, 문자열, 튜플, 딕셔너리, 집합 등

• *Iterator (반복자)**는 데이터의 흐름을 나타내는 객체로, next() 함수를 호출할 때마다 다음 요소를 반환합니다. 책갈피를 떠올리면 됩니다.

• 중요: Iterator는 한 번 사용하면 끝까지 소모되며, 재사용할 수 없습니다.

# Iterable 예시
my_list = [10, 20, 30]
for item in my_list:
    print(item, end=' ')  # 10 20 30
print()

# Iterator 직접 사용
my_iter = iter(my_list)

print(next(my_iter))  # 10
print(next(my_iter))  # 20
print(next(my_iter))  # 30
# print(next(my_iter))  # StopIteration 예외 발생

2. Mutable vs Immutable (수정 가능성)

2.1 Mutable (가변 객체)

• 예시: list, dict, set

my_list = [1, 2, 3]
print(f"변경 전 id: {id(my_list)}")
my_list.append(4)
print(f"변경 후 id: {id(my_list)}")  # id가 동일
print(my_list)  # [1, 2, 3, 4]

2.2 Immutable (불변 객체)

• 예시: int, float, str, tuple

• 장점: 값이 변하지 않아서 딕셔너리의 키나 집합의 원소로 사용할 수 있습니다

my_str = "hello"
print(f"변경 전 id: {id(my_str)}")
my_str = my_str + " world"
print(f"변경 후 id: {id(my_str)}")  # id가 달라짐
print(my_str)  # hello world

3. 복사와 함수 인자 전달

3.1 얕은 복사 (Shallow Copy) vs 깊은 복사 (Deep Copy)

얕은 복사

a = [1, 2, [10, 20]]
b = a  # 얕은 복사

b.append(3)
b[2].append(30)
print(f"a: {a}")  # [1, 2, [10, 20, 30], 3]
print(f"b: {b}")  # [1, 2, [10, 20, 30], 3]
print(f"같은 객체? {id(a) == id(b)}")  # True

깊은 복사

import copy

e = [[10, 20], 2, 3]
f = copy.deepcopy(e)

f[0].append(30)
print(f"e: {e}")  # [[10, 20], 2, 3]
print(f"f: {f}")  # [[10, 20, 30], 2, 3]

슬라이싱 또는 copy() 메서드

c = [[10, 20], 2, 3]
d = c[:]

d[0].append(30)
print(f"c: {c}")  # [[10, 20, 30], 2, 3] - 내부 리스트도 변경됨!
print(f"d: {d}")  # [[10, 20, 30], 2, 3]

# 2차원 리스트 깊은 복사 (코딩 테스트에서 자주 사용)
matrix = [[1, 2], [3, 4]]
copied_matrix = [row[:] for row in matrix]

3.2 함수 인자 전달 방식 (Call by Object Reference)

• Immutable 객체 (int, str): 함수 내에서 값을 변경하면 새 객체가 생성되므로, 원본은 바뀌지 않습니다

• Mutable 객체 (list, dict): 함수 내에서 객체의 내용을 변경하면 원본도 변경됩니다

# Immutable 예시
def change_num(n):
    n += 10
    print(f"함수 안: {n}")

num = 5
change_num(num)
print(f"함수 밖: {num}")  # 5 (변경 안됨)

# Mutable 예시
def change_list(lst):
    lst.append(100)
    print(f"함수 안: {lst}")

my_list = [1, 2, 3]
change_list(my_list)
print(f"함수 밖: {my_list}")  # [1, 2, 3, 100] (변경됨)

4. Packing & Unpacking

Packing (패킹)

Unpacking (언패킹)

# Packing
packed_tuple = 1, "hello", True
print(packed_tuple)  # (1, 'hello', True)

# Unpacking
a, b, c = packed_tuple
print(a, b, c)  # 1 hello True

# *를 이용한 Unpacking
numbers = [1, 2, 3, 4, 5]
first, *middle, last = numbers
print(f"first: {first}, middle: {middle}, last: {last}")
# first: 1, middle: [2, 3, 4], last: 5

# 함수 인자에서의 Packing
def my_func(*args, **kwargs):
    print(f"args(튜플): {args}")
    print(f"kwargs(딕셔너리): {kwargs}")

my_func(1, 2, 'a', name="Tom", age=20)
# args(튜플): (1, 2, 'a')
# kwargs(딕셔너리): {'name': 'Tom', 'age': 20}

5. 코딩 테스트 필수 라이브러리 및 함수

5.1 zip 함수

names = ["Tom", "Jerry", "Spike"]
ages = [25, 22, 30]

for name, age in zip(names, ages):
    print(f"{name} is {age} years old.")

5.2 itertools 모듈

from itertools import permutations, combinations

items = ['A', 'B', 'C']

# 순열
p = list(permutations(items, 2))
print(f"순열: {p}")
# [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

# 조합
c = list(combinations(items, 2))
print(f"조합: {c}")
# [('A', 'B'), ('A', 'C'), ('B', 'C')]

# 주의: 중복값이 있어도 위치 기반으로 동작
nums = [1, 2, 2]
p_nums = list(permutations(nums, 2))
print(f"[1, 2, 2] 순열: {p_nums}")

5.3 enumerate 함수

players = ["Messi", "Ronaldo", "Neymar"]

for index, player in enumerate(players):
    print(f"Index {index}: {player}")

# 1부터 시작
for rank, player in enumerate(players, start=1):
    print(f"Rank {rank}: {player}")

5.4 collections.deque (데크)

from collections import deque

dq = deque([1, 2, 3])

dq.append(4)          # 맨 뒤에 추가
dq.appendleft(0)      # 맨 앞에 추가
dq.pop()              # 맨 뒤에서 제거
dq.popleft()          # 맨 앞에서 제거

5.5 collections.defaultdict

from collections import defaultdict

# 문자 개수 세기
s = "programming"
char_count = defaultdict(int)
for char in s:
    char_count[char] += 1
print(char_count)

# 그래프 인접 리스트
edges = [[0, 1], [0, 2], [1, 3]]
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)
print(graph)

5.6 collections.Counter

from collections import Counter

fruits = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']
fruit_counter = Counter(fruits)

print(fruit_counter)  # Counter({'apple': 3, 'banana': 2, 'orange': 1})
print(fruit_counter['apple'])  # 3
print(fruit_counter.most_common(2))  # [('apple', 3), ('banana', 2)]

6. 문자열 처리 핵심 메서드

주요 메서드

• s.split(sep): 구분자 기준으로 잘라 리스트로 반환

• 'sep'.join(iterable): 요소들을 sep으로 연결

• s.replace(old, new): old를 new로 변경

• s.strip(), s.lstrip(), s.rstrip(): 공백 제거

• s.find(sub): sub의 첫 인덱스 반환 (없으면 -1)

• s.index(sub): sub의 첫 인덱스 반환 (없으면 ValueError)

• s.count(sub): sub의 등장 횟수 반환

sentence = "파이썬은 정말 강력합니다"
words = sentence.split()
new_sentence = "_".join(words)
print(new_sentence)

original = "hello world"
modified = original.replace("world", "python")
print(modified)  # hello python
print(original)  # hello world (원본 불변)

f-string

name = "Tom"
age = 10
print(f"이름: {name}, 나이: {age}, 10년 후: {age + 10}")

7. 그래프 표현과 탐색

7.1 그래프 표현법

인접 행렬 (Adjacency Matrix)

graph_matrix = [
    [0, 1, 0, 1],
    [1, 0, 1, 0],
    [0, 1, 0, 1],
    [1, 0, 1, 0]
]

# 인접 리스트로 변환
from collections import defaultdict

adj_list = defaultdict(list)
for i in range(len(graph_matrix)):
    for j in range(len(graph_matrix[i])):
        if graph_matrix[i][j] == 1:
            adj_list[i].append(j)

인접 리스트 (Adjacency List)

graph = {
    0: [1, 3, 6],
    1: [0, 3],
    2: [3],
    3: [0, 1, 2, 7],
    4: [5],
    5: [4, 6, 7],
    6: [0, 5],
    7: [3, 5]
}

7.2 깊이 우선 탐색 (DFS)

visited = [False] * 8

def dfs(cur_v):
    visited[cur_v] = True
    print(cur_v, end=' ')

    for next_v in graph[cur_v]:
        if not visited[next_v]:
            dfs(next_v)

dfs(0)

7.3 너비 우선 탐색 (BFS)

from collections import deque

def bfs(start_v):
    q = deque([start_v])
    visited = [False] * 8
    visited[start_v] = True

    while q:
        cur_v = q.popleft()
        print(cur_v, end=' ')

        for next_v in graph[cur_v]:
            if not visited[next_v]:
                visited[next_v] = True
                q.append(next_v)

bfs(0)

7.4 Grid (격자) 탐색

dr = [-1, 1, 0, 0]  # 상, 하
dc = [0, 0, -1, 1]  # 좌, 우

def dfs_grid(r, c, grid, visited):
    visited[r][c] = True
    print(f"({r}, {c}) 방문")

    for i in range(4):
        nr, nc = r + dr[i], c + dc[i]

        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
            if grid[nr][nc] == 1 and not visited[nr][nc]:
                dfs_grid(nr, nc, grid, visited)

7.5 그래프 응용: 연결 요소 개수 찾기

def count_networks(grid):
    if not grid:
        return 0

    row_len, col_len = len(grid), len(grid[0])
    visited = [[False] * col_len for _ in range(row_len)]
    count = 0

    def bfs_internal(r, c):
        q = deque([(r, c)])
        visited[r][c] = True

        while q:
            cr, cc = q.popleft()
            for i in range(4):
                nr, nc = cr + dr[i], cc + dc[i]
                if 0 <= nr < row_len and 0 <= nc < col_len and \
                   grid[nr][nc] == 1 and not visited[nr][nc]:
                    visited[nr][nc] = True
                    q.append((nr, nc))

    for r in range(row_len):
        for c in range(col_len):
            if grid[r][c] == 1 and not visited[r][c]:
                bfs_internal(r, c)
                count += 1

    return count

7.6 최단 거리 찾기 (BFS)

from collections import deque

def shortest_path(grid, start, end):
    row_len, col_len = len(grid), len(grid[0])
    distance = [[-1] * col_len for _ in range(row_len)]

    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]

    start_r, start_c = start
    end_r, end_c = end

    q = deque([(start_r, start_c)])
    distance[start_r][start_c] = 0

    while q:
        r, c = q.popleft()

        if r == end_r and c == end_c:
            return distance[r][c]

        for i in range(4):
            nr, nc = r + dr[i], c + dc[i]

            if 0 <= nr < row_len and 0 <= nc < col_len and \
               grid[nr][nc] == 1 and distance[nr][nc] == -1:
                distance[nr][nc] = distance[r][c] + 1
                q.append((nr, nc))

    return -1

8. 완전 탐색과 백트래킹

8.1 완전 탐색 (Exhaustive Search)

8.2 백트래킹 (Backtracking)

def backtrack(path):
    # 종료 조건
    if len(path) == 원하는_길이:
        ans.append(path[:])
        return

    # 다음 선택지 탐색
    for choice in 가능한_선택지들:
        # 선택
        path.append(choice)

        # 재귀
        backtrack(path)

        # 백트래킹 (상태 복구)
        path.pop()

8.3 가지치기 (Pruning)

def backtrack_with_pruning(path):
    # 가지치기
    if 현재_경로가_가망이_없음:
        return

    # 종료 조건
    if len(path) == 원하는_길이:
        ans.append(path[:])
        return

    # 재귀
    for choice in 가능한_선택지들:
        path.append(choice)
        backtrack_with_pruning(path)
        path.pop()

8.4 순열 (Permutation)

def permutations(nums, r):
    ans = []
    visited = [False] * len(nums)

    def backtrack(path):
        if len(path) == r:
            ans.append(path[:])
            return

        for i in range(len(nums)):
            if not visited[i]:
                visited[i] = True
                path.append(nums[i])

                backtrack(path)

                path.pop()
                visited[i] = False

    backtrack([])
    return ans

8.5 조합 (Combination)

def combinations(nums, r):
    ans = []

    def backtrack(start_index, path):
        if len(path) == r:
            ans.append(path[:])
            return

        for i in range(start_index, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return ans

8.6 부분 집합 (Subset)

def subsets(nums):
    ans = []

    def backtrack(start_index, path):
        ans.append(path[:])

        for i in range(start_index, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return ans

9. 다이나믹 프로그래밍 (Dynamic Programming)

9.1 0-1 배낭 문제 (Knapsack)

N, K = map(int, input().split())
c = [0] * (K + 1)

for _ in range(N):
    W, V = map(int, input().split())
    for j in range(K, W - 1, -1):
        c[j] = max(c[j], c[j - W] + V)

print(c[K])

9.2 최장 공통 부분 수열 (LCS)

str1 = input()
str2 = input()

table = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]

for i in range(1, len(str1) + 1):
    for j in range(1, len(str2) + 1):
        if str1[i - 1] == str2[j - 1]:
            table[i][j] = table[i - 1][j - 1] + 1
        else:
            table[i][j] = max(table[i - 1][j], table[i][j - 1])

print(table[len(str1)][len(str2)])

10. 최단 경로 알고리즘

10.1 다익스트라 (Dijkstra)

import heapq

def dijkstra(start, graph, n):
    distance = [float('inf')] * (n + 1)
    distance[start] = 0
    q = [(0, start)]

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for next_node, cost in graph[now]:
            new_cost = dist + cost
            if new_cost < distance[next_node]:
                distance[next_node] = new_cost
                heapq.heappush(q, (new_cost, next_node))

    return distance

10.2 플로이드-워셜 (Floyd-Warshall)

INF = int(1e9)

# 초기화
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if i == j:
            graph[i][j] = 0

# 플로이드-워셜
for k in range(1, n + 1):
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

11. 기타 필수 알고리즘

11.1 크루스칼 (Kruskal) - 최소 신장 트리

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a< b:
		parent[b] = a
		else:
		parent[a] = b

11.2 위상 정렬 (Topological Sort)

from collections import deque

def topology_sort(graph, indegree, v):
    result = []
    q = deque()

    # 진입차수가 0인 노드 큐에 삽입
    for i in range(1, v + 1):
        if indegree[i] == 0:
            q.append(i)

    while q:
        now = q.popleft()
        result.append(now)

        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    return result

11.3 유니온-파인드 (Union-Find) - 사이클 판별

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

v, e = map(int, input().split())
parent = [i for i in range(v + 1)]
cycle = False

for _ in range(e):
    a, b = map(int, input().split())

    # 사이클 판별
    if find_parent(parent, a) == find_parent(parent, b):
        cycle = True
        break
    else:
        union_parent(parent, a, b)

print("사이클 발생" if cycle else "사이클 없음")

12. 세그먼트 트리 (Segment Tree)

12.1 언제 사용하나요?

1. 구간 쿼리: 특정 구간 [L, R]의 합, 최댓값, 최솟값을 반복적으로 구해야 할 때

2. 데이터 변경: 배열의 특정 원소가 자주 변경될 때

12.2 핵심 연산

• 초기화 (build): O(N)

• 구간 쿼리 (query): O(log N)

• 업데이트 (update): O(log N)

12.3 구현 (구간 합)

class SegmentTree:
    def __init__(self, arr):
        self.arr = arr
        self.n = len(arr)
        self.tree = [0] * (4 * self.n)
        self.build(1, 0, self.n - 1)

    def build(self, node, start, end):
        if start == end:
            self.tree[node] = self.arr[start]
            return self.tree[node]

        mid = (start + end) // 2
        left_sum = self.build(node * 2, start, mid)
        right_sum = self.build(node * 2 + 1, mid + 1, end)

        self.tree[node] = left_sum + right_sum
        return self.tree[node]

    def update(self, node, start, end, index, value):
        if index < start or index > end:
            return

        if start == end:
            self.tree[node] = value
            return

        mid = (start + end) // 2
        self.update(node * 2, start, mid, index, value)
        self.update(node * 2 + 1, mid + 1, end, index, value)
        self.tree[node] = self.tree[node * 2] + self.tree[node * 2 + 1]

    def query(self, node, start, end, left, right):
        # 범위를 벗어난 경우
        if right < start or end < left:
            return 0

        # 범위에 완전히 포함된 경우
        if left <= start and end <= right:
            return self.tree[node]

        # 일부 겹치는 경우
        mid = (start + end) // 2
        left_sum = self.query(node * 2, start, mid, left, right)
        right_sum = self.query(node * 2 + 1, mid + 1, end, left, right)
        return left_sum + right_sum

# 사용 예시
arr = [1, 3, 5, 7, 9, 11]
seg_tree = SegmentTree(arr)

# 구간 [1, 4] 합 구하기
result = seg_tree.query(1, 0, seg_tree.n - 1, 1, 4)
print(f"구간 [1, 4]의 합: {result}")  # 24

# 인덱스 2를 6으로 변경
seg_tree.update(1, 0, seg_tree.n - 1, 2, 6)

# 다시 구간 [1, 4] 합 구하기
result = seg_tree.query(1, 0, seg_tree.n - 1, 1, 4)
print(f"구간 [1, 4]의 합: {result}")  # 25

12.4 응용: 구간 최솟값/최댓값

# build와 update에서
# self.tree[node] = left_sum + right_sum
self.tree[node] = min(left_result, right_result)  # 최솟값
# 또는
self.tree[node] = max(left_result, right_result)  # 최댓값

# query에서
# if right < start or end < left: return 0
if right < start or end < left:
    return float('inf')  # 최솟값의 경우
    # return -float('inf')  # 최댓값의 경우

# return left_sum + right_sum
return min(left_result, right_result)  # 최솟값
# 또는
return max(left_result, right_result)  # 최댓값

13. 기하학 (Geometry)

13.1 최대공약수 (GCD) & 최소공배수 (LCM)

from math import gcd

def get_gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def get_lcm(a, b):
    return a * b // get_gcd(a, b)

# 또는 라이브러리 사용
a, b = 12, 18
print(gcd(a, b))          # 6
print(a * b // gcd(a, b)) # 36

13.2 이항계수 (Binomial Coefficient)

def binomial_coefficient(n, k):
    memo = [[0] * (k + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            if j == 0 or j == i:
                memo[i][j] = 1
            else:
                memo[i][j] = memo[i - 1][j - 1] + memo[i - 1][j]

    return memo[n][k]

print(binomial_coefficient(5, 2))  # 10

13.3 거리 계산

# 유클리드 거리
def euclidean_distance(pt1, pt2):
    result = sum((pt2[i] - pt1[i]) ** 2 for i in range(len(pt1)))
    return result ** 0.5

# 맨해튼 거리
def manhattan_distance(pt1, pt2):
    return sum(abs(pt2[i] - pt1[i]) for i in range(len(pt1)))

print(euclidean_distance([5, 4, 3], [1, 7, 9]))  # 8.774...
print(manhattan_distance([5, 4, 3], [1, 7, 9]))  # 13

13.4 에라토스테네스의 체 (소수 찾기)

def prime_sieve(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False

    for i in range(2, int(n ** 0.5) + 1):
        if sieve[i]:
            for j in range(i * i, n + 1, i):
                sieve[j] = False

    return [i for i in range(n + 1) if sieve[i]]

primes = prime_sieve(100)
print(primes)

14. 유용한 테크닉

14.1 2차원 리스트 90도 회전

def rotate_90(matrix):
    row_len = len(matrix)
    col_len = len(matrix[0])
    result = [[0] * row_len for _ in range(col_len)]

    for r in range(row_len):
        for c in range(col_len):
            result[c][row_len - 1 - r] = matrix[r][c]

    return result

a = [
    [1, 2, 3, 4],
    [5, 6, 7, 8],
    [9, 10, 11, 12]
]

print(rotate_90(a))

14.2 2차원 리스트 초기화 주의사항

# ❌ 잘못된 방법 (모든 행이 같은 객체를 참조)
wrong = [[0] * 3] * 4

# ✅ 올바른 방법
correct = [[0] * 3 for _ in range(4)]

14.3 입력 처리 최적화

import sys
input = sys.stdin.readline

# 빠른 입력 처리
n = int(input())
arr = list(map(int, input().split()))

14.4 무한대 설정

INF = int(1e9)  # 10억
INF = float('inf')  # 파이썬의 무한대

15. 실전 팁

15.1 시간 복잡도 가늠하기

• N ≤ 10: O(N!) 가능

• N ≤ 20: O(2^N) 가능

• N ≤ 500: O(N³) 가능

• N ≤ 5,000: O(N²) 가능

• N ≤ 100,000: O(N log N) 권장

• N ≤ 10,000,000: O(N) 권장

15.2 자주 하는 실수

1. 인덱스 범위 초과: 배열 접근 전 항상 범위 체크

2. 얕은 복사 vs 깊은 복사: 2차원 리스트는 deepcopy 사용

3. Mutable 객체 함수 인자: 원본 변경에 주의

4. visited 초기화 위치: DFS/BFS에서 초기화 위치 확인

5. 경로 복사: path[:]로 복사해서 저장

15.3 디버깅 팁

# 변수 값 빠르게 확인
print(f"{변수명 = }")  # 파이썬 3.8+

# 함수 실행 시간 측정
import time
start = time.time()
# 코드 실행
print(f"실행 시간: {time.time() - start:.4f}초")

# 중간 상태 확인
import sys
print("디버그:", value, file=sys.stderr)

16. 마치며

참고 자료

• Python 공식 문서: https://docs.python.org/3/

• 백준 온라인 저지: https://www.acmicpc.net/

• 프로그래머스: https://programmers.co.kr/