들어가며
알고리즘 문제들을 풀다 보면, 쉬운 문제들은 생각나는 대로 풀면 정답이 맞곤 하지만, 어느 정도 수준이 있는 문제를 풀기 위해서는 구현도 중요하지만 알고리즘 패러다임을 적극적으로 사용하여 시간복잡도를 계산하며 효율적인 알고리즘을 찾는 과정이 더 중요하다는 걸 깨닫게 되곤 한다. 거의 모든 문제에서 사용되는 알고리즘 패러다임을 모아서 정리해 보았다.
1. Brute Force(완전탐색)
말 그대로 "다 해보는" 방법이다. 가능한 모든 경우의 수를 탐색해서 정답을 찾는 방식으로, 가장 쉽게 생각해 낼 수 있고 단순하지만 데이터가 커질수록 기하급수적으로 계산에 필요한 시간이 늘어난다는 단점이 있다.
When ?
● 데이터 크기가 작을 때(n < 10000) 정도
● 다른 최적화 방법이 떠오르지 않을 때
● 정답을 검증하는 용도
주의할 점 : 시간복잡도가 O(n^2) 이상이기 때문에, n이 100만 이상이면 완전탐색은 사실상 불가능하다고 볼 수 있다.
예시 코드
# 예시: 배열에서 두 수의 합이 target인 쌍 찾기
def brute_force(arr, target):
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] + arr[j] == target:
return (arr[i], arr[j])
# 시간복잡도: O(n²)
자주 쓰는 메소드
permutations(순열 생성), combinations(조합 생성), product(중복 순열 생성)
from itertools import permutations, combinations, product
arr = [1, 2, 3]
# 순열 (순서 O)
list(permutations(arr, 2)) # [(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]
# 조합 (순서 X)
list(combinations(arr, 2)) # [(1,2),(1,3),(2,3)]
# 중복 순열
list(product(arr, repeat=2)) # [(1,1),(1,2),(1,3)...]2. Greedy Search(탐욕법)
매 순간 지금 당장 가장 좋은 선택을 하는 방법이다. 한 번 선택하면 되돌아가지 않은데, "현재의 최선 = 전체의 최선"이 성립하는 문제에서만 정답이 보장된다. 이게 성립하는지 판단하는 게 중요하다고 할 수 있다.
when?
● 정렬 후 순서대로 선택하는 문제
● 최소 횟수, 최소 비용 문제
● 기준이 명확하게 하나인 문제
주의할 점 : "지금 최선이 나중에 독이 되는 상황"에서는 사용 X(ex. 거스름돈 문제에서 동전 단위가 배수관계가 아닐 때)
예시 코드
# 예시: 회의실 배정 (끝나는 시간이 빠른 순으로 선택)
def greedy(meetings):
meetings.sort(key=lambda x: x[1]) # 끝시간 기준 정렬
count, end = 0, 0
for start, finish in meetings:
if start >= end:
count += 1
end = finish
return count
# 시간복잡도: O(n log n) - 정렬이 병목
자주 쓰는 메소드
sort/sorted(정렬, 거의 무조건 정렬 후 탐색한다), heapq(우선순위 큐)
# sort / sorted - Greedy는 정렬이 거의 항상 따라옴
arr.sort(key=lambda x: x[1]) # 두번째 요소 기준
arr.sort(key=lambda x: (x[1], x[0])) # 두번째 → 첫번째 기준
arr.sort(reverse=True) # 내림차순
# heapq - 최솟값을 빠르게 뽑을 때
import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappop(heap) # 1 (항상 최솟값)
# 최대힙은 음수로 변환
heapq.heappush(heap, -value)
-heapq.heappop(heap)3. Divide & Conquer(분할정복)
큰 문제를 작은 문제로 쪼개고 -> 각각 풀고 -> 결과를 합치는 방식이다. 재귀로 구현하는 경우가 많은데, 성립하려면 큰 문제와 작은 문제가 동일해야 한다.(재귀를 사용하기 때문)
when?
● 문제를 독립적인 부분으로 나눌 수 있을 때
● 정렬 문제(Merge Sort, Quick Sort)
● 거듭제곱, 행렬 곱셈 등
뒤에서 다룰 DP(다이내믹 프로그래밍)과 다른 점은 분할 정복은 나눈 부분 문제들이 독립적인 반면, DP는 나눈 부분 문제들이 서로 겹친다.
예시 코드
# 예시: 병합정렬
def merge_sort(arr):
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):
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
return result + left[i:] + right[j:]
# 시간복잡도: O(n log n)
자주 쓰는 메소드
sys.setrecursionlimit(재귀 길이 늘이기)
import sys
sys.setrecursionlimit(10**6) # 재귀 깊이 늘리기 (필수!)
# 거듭제곱 - 분할정복 대표 예시
def power(base, exp):
if exp == 0: return 1
if exp % 2 == 0:
half = power(base, exp // 2)
return half * half # 절반으로 쪼개서 재활용
return base * power(base, exp - 1)4. Dynamic Programming(동적 계획법)
"이미 푼 작은 문제의 답을 저장해 두고 재활용"하는 방식으로, 같은 계산을 반복하지 않아도 되어서 효율적이다. DP가 적용가능하려면 두 가지 조건이 필요한데,
● 최적 부분구조 : 큰 문제의 최적해가 작은 문제의 최적해로 구성됨
● 중복 부분문제 : 같은 부분 문제가 여러 번 등장
when?
● 최댓값/최솟값 문제
● 경우의 수를 구하는 문제
● "~할 수 있는가" 여부를 묻는 문제
Bottom-up vs Top-down
● Top-down : 재귀 + 메모이제이션
-> 메모이제이션(Memoization) : memo에서 온 말로, "계산 결과를 메모해 두고 재사용한다"는 의미
● Bottom-up : 반복문으로 작은 것부터 채워나가기
● 일반적으로 Bottom-up이 스택 오버플로우 위험이 없어서 더 안전
예시 코드
# ❌ 순수 재귀 - 같은 계산을 수없이 반복
def fib_recursive(n):
if n <= 1: return n
return fib_recursive(n-1) + fib_recursive(n-2)
# 시간복잡도: O(2^n) → n=50이면 이미 불가능
# ✅ Bottom-up DP - 한 번 계산한 값은 저장
def fib_dp(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2] # 이전 결과 재활용
return dp[n]
# 시간복잡도: O(n)
# ✅ Top-down DP - 재귀 + 메모이제이션
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_topdown(n):
if n <= 1: return n
return fib_topdown(n-1) + fib_topdown(n-2)자주 쓰는 메소드
@lru_cache(maxsize=None) : Least Recently Used로, 가장 최근에 안 쓴 것부터 버린다는 캐시 전략이다. 함수의 결과를 자동으로 저장해 주는 데코레이터로, 직접 딕셔너리로 메모이제이션 구현하는 것을 자동으로 해준다.
from functools import lru_cache
# ✅ lru_cache 사용
@lru_cache(maxsize=None) # None = 제한 없이 전부 저장
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
# ❌ 직접 구현하면 이렇게 해야 함
cache = {}
def fib(n):
if n in cache: return cache[n]
if n <= 1: return n
cache[n] = fib(n-1) + fib(n-2)
return cache[n]
# 둘이 완전히 동일하게 동작 - lru_cache가 위 과정을 자동으로 해줌5. Backtracking(백트래킹)
Brute Force처럼 모든 경우를 탐색하지만, 조건에 맞지 않으면 즉시 되돌아가서 탐색 범위를 줄인다. DFS 기반으로 구현하는 경우가 많은데, "가지치기(pruning)"을 얼마나 잘하느냐에 따라 성능이 결정된다.
when?
● 모든 조합 / 순열을 탐색해야 할 때
● 스도쿠 같은 제약조건 만족 문제
● 미로 탐색
예시 코드
# 예시: 1~n 중에서 m개를 고르는 조합
def backtracking(n, m):
result = []
def dfs(start, path):
if len(path) == m: # ① 완성되면 저장
result.append(path[:])
return
for i in range(start, n+1):
path.append(i)
dfs(i+1, path) # ② 다음 탐색
path.pop() # ③ 되돌아가기 (핵심!)
dfs(1, [])
return result자주 쓰는 메소드
set() : 집합(중복된 인자가 들어오면 알아서 추가 안 함), deque : 양방향 큐(앞쪽과 뒤쪽에서 모두 추가와 삭제가 가능한 배열)
# visited 배열 - 방문 체크
visited = [False] * n # 리스트로
visited = set() # 집합으로 (더 빠름)
visited.add(node) # 방문 처리
node in visited # 방문 확인
visited.discard(node) # 되돌아갈 때 제거
# BFS용 deque
from collections import deque
queue = deque()
queue.append(x) # 오른쪽 추가
queue.appendleft(x) # 왼쪽 추가
queue.popleft() # 왼쪽 제거 (O(1)) ← list.pop(0)은 O(n)이라 느림
6. 알고리즘 패러다임 전체 요약
