코딩테스트 준비를 시작했는데 어디서부터 손대야 할지 막막하신가요? 수백 가지 알고리즘을 모두 외울 필요는 없습니다. 코딩테스트 빈출 알고리즘 10가지만 확실히 내 것으로 만들어도, 국내 대부분의 기업 코딩테스트에서 통과선을 넘길 수 있습니다. 이 글에서는 삼성, 카카오, 네이버, 라인 등 주요 기업 코딩테스트에서 반복적으로 출제되는 핵심 알고리즘 10가지를 파이썬 코드와 함께 완벽하게 정리합니다. 개념 → 동작 원리 → 실전 코드 순서로 구성했으니, 처음부터 끝까지 따라오시면 됩니다.
목차
- 코딩테스트 알고리즘 선택 전략 – 무엇을 얼마나 공부해야 하는가?
- 탐색 알고리즘 – BFS & DFS
- 정렬 & 탐색 알고리즘 – 이진 탐색 & 정렬
- 최적화 알고리즘 – 그리디 & 동적 프로그래밍
- 그래프 알고리즘 – 다익스트라 & 유니온 파인드
- 고급 테크닉 – 투 포인터 · 슬라이딩 윈도우 · 백트래킹 · 소수 판별
1. 코딩테스트 알고리즘 선택 전략 – 무엇을 얼마나 공부해야 하는가?
코딩테스트를 처음 준비하는 분들이 가장 많이 저지르는 실수는 너무 많은 것을 공부하려다 아무것도 완성하지 못하는 것입니다. 알고리즘 교재를 펼치면 수십 가지 자료구조와 알고리즘이 나열되어 있어 압도당하기 쉽습니다. 하지만 실제 코딩테스트 출제 패턴을 분석해보면, 특정 유형이 반복적으로 출제된다는 사실을 알 수 있습니다.
기업별 출제 빈도 분석
| 알고리즘 유형 | 삼성 SW | 카카오 | 네이버 | 라인 |
|---|---|---|---|---|
| BFS / DFS | ⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐ | ⭐⭐⭐ |
| 동적 프로그래밍 | ⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐ |
| 그리디 | ⭐⭐ | ⭐⭐⭐ | ⭐⭐ | ⭐⭐ |
| 구현 / 시뮬레이션 | ⭐⭐⭐ | ⭐⭐ | ⭐⭐ | ⭐⭐ |
| 이진 탐색 | ⭐⭐ | ⭐⭐⭐ | ⭐⭐⭐ | ⭐⭐ |
| 그래프(다익스트라) | ⭐⭐ | ⭐⭐ | ⭐⭐⭐ | ⭐⭐⭐ |
학습 우선순위 로드맵
[1순위 - 필수 마스터]
BFS/DFS → 동적 프로그래밍 → 그리디 → 이진 탐색
[2순위 - 고득점 필요 시]
다익스트라 → 유니온 파인드 → 투 포인터
[3순위 - 상위권 목표 시]
백트래킹 → 슬라이딩 윈도우 → 소수 판별(에라토스테네스)
파이썬을 사용하면 collections.deque, heapq, bisect 등 강력한 내장 라이브러리 덕분에 코드 구현 시간을 크게 줄일 수 있습니다. 단, 파이썬은 C++보다 실행 속도가 느리므로 시간 복잡도를 항상 의식하며 코딩하는 습관이 필요합니다.
2. 탐색 알고리즘 – BFS & DFS
**BFS(너비 우선 탐색)**와 **DFS(깊이 우선 탐색)**는 코딩테스트 빈출 알고리즘 중 출제 빈도 1위를 다투는 핵심 유형입니다. 미로 탈출, 섬의 개수 세기, 최단 경로 찾기 등 다양한 문제가 이 두 알고리즘으로 해결됩니다.
알고리즘 1: BFS (너비 우선 탐색)
BFS는 시작점에서 가까운 노드부터 차례로 탐색합니다. 물에 돌을 던졌을 때 파문이 동심원으로 퍼져나가는 것과 같은 방식입니다. 최단 거리 문제에 최적입니다.
- 자료구조: 큐(Queue) → 파이썬
collections.deque - 시간복잡도: O(V + E) — V: 정점 수, E: 간선 수
- 핵심 사용 사례: 최단 경로, 레벨 탐색, 연결 요소 개수
python
from collections import deque
def bfs(graph, start, visited):
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft() # 큐 앞에서 꺼내기
print(node, end=' ')
for neighbor in graph[node]: # 인접 노드 순회
if not visited[neighbor]:
visited[neighbor] = True
queue.append(neighbor) # 큐 뒤에 추가
# 사용 예시
graph = {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []}
visited = {node: False for node in graph}
bfs(graph, 1, visited)
# 출력: 1 2 3 4 5 6
알고리즘 2: DFS (깊이 우선 탐색)
DFS는 한 방향으로 갈 수 있는 끝까지 파고든 뒤, 되돌아와 다른 방향을 탐색합니다. 미로에서 막다른 길에 부딪히면 왔던 길을 되짚어가는 방식과 동일합니다. 경우의 수, 순열, 조합 탐색에 적합합니다.
- 자료구조: 스택(Stack) 또는 재귀(Recursion)
- 시간복잡도: O(V + E)
- 핵심 사용 사례: 사이클 검출, 위상 정렬, 백트래킹
python
def dfs(graph, node, visited):
visited[node] = True
print(node, end=' ')
for neighbor in graph[node]:
if not visited[neighbor]:
dfs(graph, neighbor, visited) # 재귀 호출
# 사용 예시
graph = {1: [2, 3], 2: [4, 5], 3: [6], 4: [], 5: [], 6: []}
visited = {node: False for node in graph}
dfs(graph, 1, visited)
# 출력: 1 2 4 5 3 6
💡 BFS vs DFS 선택 기준: “최단 거리가 필요하다” → BFS / “모든 경우를 탐색해야 한다” → DFS
3. 정렬 & 탐색 알고리즘 – 이진 탐색 & 정렬
알고리즘 3: 이진 탐색 (Binary Search)
이진 탐색은 정렬된 배열에서 원하는 값을 찾을 때, 탐색 범위를 절반씩 줄여가는 알고리즘입니다. 도서관에서 책을 찾을 때 맨 앞부터 한 권씩 넘기는 것(선형 탐색, O(n))이 아니라, 중간 책을 펼쳐보고 앞/뒤 방향을 결정하는 방식(이진 탐색, O(log n))입니다.
- 시간복잡도: O(log N)
- 전제 조건: 배열이 반드시 정렬되어 있어야 함
- 핵심 사용 사례: “~이상의 최솟값”, “~이하의 최댓값” 파라메트릭 서치
python
# 방법 1: 직접 구현
def binary_search(arr, target):
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 # 찾지 못한 경우
# 방법 2: bisect 라이브러리 활용 (실전 추천)
from bisect import bisect_left, bisect_right
arr = [1, 3, 5, 7, 9, 11]
print(bisect_left(arr, 7)) # 출력: 3 (7이 삽입될 왼쪽 인덱스)
print(bisect_right(arr, 7)) # 출력: 4 (7이 삽입될 오른쪽 인덱스)
알고리즘 4: 정렬 (Sort) – 파이썬의 강점
파이썬의 내장 정렬은 팀소트(Timsort) 알고리즘을 사용하며, 시간복잡도는 O(N log N)으로 매우 효율적입니다. 코딩테스트에서 커스텀 정렬 기준을 적용하는 문제가 자주 출제됩니다.
python
# 기본 정렬
arr = [3, 1, 4, 1, 5, 9, 2, 6]
arr.sort() # 오름차순 in-place 정렬
sorted_arr = sorted(arr) # 새 리스트 반환
# 내림차순
arr.sort(reverse=True)
# 커스텀 정렬 (핵심 실전 패턴)
# 예: 학생 리스트를 성적 내림차순, 이름 오름차순으로 정렬
students = [("Alice", 90), ("Bob", 85), ("Carol", 90)]
students.sort(key=lambda x: (-x[1], x[0]))
# 출력: [('Alice', 90), ('Carol', 90), ('Bob', 85)]
# 문자열 길이 기준 정렬
words = ["apple", "kiwi", "banana", "fig"]
words.sort(key=len)
# 출력: ['fig', 'kiwi', 'apple', 'banana']
4. 최적화 알고리즘 – 그리디 & 동적 프로그래밍
알고리즘 5: 그리디 (Greedy)
그리디 알고리즘은 매 순간 가장 좋아 보이는 선택을 반복해 최적해를 구하는 방법입니다. “지금 당장 최선”을 선택하면 전체적으로도 최선이 되는 문제에 적용할 수 있습니다. 거스름돈 문제가 대표적인 예시입니다.
- 시간복잡도: 문제마다 다름 (보통 O(N) ~ O(N log N))
- 적용 조건: 탐욕적 선택 속성 + 최적 부분 구조
- 핵심 사용 사례: 거스름돈, 회의실 배정, 최소 스패닝 트리
python
# 예시: 거스름돈 문제
# 500, 100, 50, 10원 동전으로 n원을 만들 때 최소 동전 개수
def greedy_change(n):
coins = [500, 100, 50, 10]
count = 0
for coin in coins:
count += n // coin # 현재 동전으로 만들 수 있는 최대 개수
n %= coin # 나머지 금액
if n == 0:
break
return count
print(greedy_change(1260)) # 출력: 6 (500×2 + 100×2 + 50×1 + 10×1)
알고리즘 6: 동적 프로그래밍 (Dynamic Programming)
DP는 큰 문제를 작은 부분 문제로 나누어 풀고, 그 결과를 저장(메모이제이션)하여 재사용하는 기법입니다. 피보나치 수열을 예로 들면, 같은 계산을 반복하지 않고 한 번 계산한 값을 테이블에 저장해두는 것입니다.
- 시간복잡도: O(N) ~ O(N²) (문제에 따라 다름)
- 핵심 사용 사례: 피보나치, 배낭 문제, 최장 공통 부분 수열(LCS)
- 두 가지 접근법: 탑다운(재귀+메모이제이션) vs 바텀업(반복문+테이블)
python
# 피보나치 수열 – 세 가지 방법 비교
# 방법 1: 단순 재귀 (비효율, 지수 시간)
def fib_naive(n):
if n <= 1: return n
return fib_naive(n-1) + fib_naive(n-2)
# 방법 2: 탑다운 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)
# 방법 3: 바텀업 DP (반복문 + 테이블) ← 코딩테스트 추천
def fib_bottomup(n):
if n <= 1: return 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]
print(fib_bottomup(10)) # 출력: 55
# 실전 예시: 0/1 배낭 문제 (Knapsack)
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w] = i번째 물건까지 고려했을 때 무게 w 이하의 최대 가치
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# 현재 물건을 넣지 않는 경우
dp[i][w] = dp[i-1][w]
# 현재 물건을 넣는 경우 (무게가 허용될 때만)
if w >= weights[i-1]:
dp[i][w] = max(dp[i][w],
dp[i-1][w - weights[i-1]] + values[i-1])
return dp[n][capacity]
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
print(knapsack(weights, values, 8)) # 출력: 10
5. 그래프 알고리즘 – 다익스트라 & 유니온 파인드
알고리즘 7: 다익스트라 (Dijkstra)
다익스트라 알고리즘은 가중치 그래프에서 특정 노드로부터 모든 노드까지의 최단 거리를 구하는 알고리즘입니다. 네비게이션 앱이 최단 경로를 계산할 때 사용하는 원리와 동일합니다. 파이썬에서는 heapq(우선순위 큐)를 활용하면 효율적으로 구현됩니다.
- 시간복잡도: O((V + E) log V)
- 전제 조건: 간선 가중치가 음수가 아니어야 함
- 핵심 사용 사례: 도로 네트워크 최단 경로, 네트워크 지연 시간
python
import heapq
def dijkstra(graph, start):
# 거리 테이블 초기화 (무한대)
INF = float('inf')
dist = {node: INF for node in graph}
dist[start] = 0
# (거리, 노드) 형태의 우선순위 큐
heap = [(0, start)]
while heap:
current_dist, node = heapq.heappop(heap)
# 이미 처리된 노드는 스킵
if current_dist > dist[node]:
continue
for neighbor, weight in graph[node]:
distance = current_dist + weight
# 더 짧은 경로 발견 시 갱신
if distance < dist[neighbor]:
dist[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return dist
# 그래프: {노드: [(인접노드, 가중치), ...]}
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}
print(dijkstra(graph, 'A'))
# 출력: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
알고리즘 8: 유니온 파인드 (Union-Find)
유니온 파인드는 여러 노드가 같은 그룹(집합)에 속하는지 빠르게 판별하고, 두 그룹을 합치는 자료구조입니다. “두 사람이 같은 친구 그룹에 속하는가?”를 O(α(N)) 수준의 거의 상수 시간에 판별합니다.
- 시간복잡도: O(α(N)) — 사실상 O(1)에 가까운 역아커만 함수
- 핵심 사용 사례: 사이클 탐지, 최소 스패닝 트리(크루스칼), 네트워크 연결성
python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n)) # 초기: 각자가 자신의 부모
self.rank = [0] * n # 트리 높이 (랭크 압축용)
def find(self, x):
# 경로 압축: 루트를 직접 가리키도록 최적화
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # 이미 같은 집합 → 사이클 발생
# 랭크가 낮은 쪽을 높은 쪽에 연결
if self.rank[rx] < self.rank[ry]:
rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]:
self.rank[rx] += 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
# 사용 예시
uf = UnionFind(5)
uf.union(0, 1)
uf.union(2, 3)
print(uf.connected(0, 1)) # True
print(uf.connected(0, 2)) # False
uf.union(1, 2)
print(uf.connected(0, 3)) # True
6. 고급 테크닉 – 투 포인터 · 슬라이딩 윈도우 · 백트래킹 · 소수 판별
알고리즘 9-①: 투 포인터 (Two Pointer)
배열의 두 지점을 동시에 움직이며 조건을 만족하는 구간을 탐색합니다. O(N²)이 걸릴 문제를 O(N)으로 줄이는 핵심 최적화 기법입니다.
python
# 예시: 합이 target인 두 수의 인덱스 찾기 (정렬된 배열)
def two_pointer_sum(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return (left, right)
elif current_sum < target:
left += 1 # 합이 작으면 왼쪽 포인터를 오른쪽으로
else:
right -= 1 # 합이 크면 오른쪽 포인터를 왼쪽으로
return None
print(two_pointer_sum([1, 3, 5, 7, 9], 12)) # 출력: (2, 4) → 5+7=12
알고리즘 9-②: 슬라이딩 윈도우 (Sliding Window)
고정 크기 또는 가변 크기의 창(window)을 배열 위에서 밀어가며 특정 조건의 최적값을 탐색합니다. 연속된 구간의 합, 최댓값 등을 O(N)으로 처리합니다.
python
# 예시: 크기 k인 연속 부분 배열의 최대 합
def max_sliding_window_sum(arr, k):
window_sum = sum(arr[:k]) # 첫 번째 윈도우 합
max_sum = window_sum
for i in range(k, len(arr)):
# 새 원소 추가, 오래된 원소 제거
window_sum += arr[i] - arr[i - k]
max_sum = max(max_sum, window_sum)
return max_sum
print(max_sliding_window_sum([2, 1, 5, 1, 3, 2], 3)) # 출력: 9 (5+1+3)
알고리즘 10-①: 백트래킹 (Backtracking)
**모든 경우의 수를 탐색하되, 가능성이 없는 경로는 조기에 포기(가지치기)**하는 탐색 기법입니다. DFS 기반이며, N-Queen 문제, 순열/조합 생성, 스도쿠 풀이 등에 사용됩니다.
python
# 예시: N개 중 R개를 뽑는 모든 조합 출력
def backtrack_combination(n, r):
result = []
def dfs(start, path):
if len(path) == r:
result.append(path[:]) # 완성된 조합 저장
return
for i in range(start, n + 1):
path.append(i) # 선택
dfs(i + 1, path) # 다음 원소 탐색
path.pop() # 선택 취소 (백트래킹)
dfs(1, [])
return result
print(backtrack_combination(4, 2))
# 출력: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
알고리즘 10-②: 에라토스테네스의 체 (소수 판별)
N 이하의 모든 소수를 O(N log log N) 에 구하는 고전 알고리즘입니다. 하나씩 나눠보는 방식(O(N√N))보다 압도적으로 빠릅니다.
python
# 에라토스테네스의 체
def sieve_of_eratosthenes(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False # 0, 1은 소수 아님
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
# i의 배수를 모두 소수 아님으로 표시
for j in range(i*i, n + 1, i):
is_prime[j] = False
return [i for i in range(n + 1) if is_prime[i]]
print(sieve_of_eratosthenes(30))
# 출력: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
결론
코딩테스트 빈출 알고리즘 10가지를 BFS/DFS, 이진 탐색, 정렬, 그리디, 동적 프로그래밍, 다익스트라, 유니온 파인드, 투 포인터, 슬라이딩 윈도우, 백트래킹·소수 판별 순서로 파이썬 코드와 함께 완벽하게 정리했습니다. 이 10가지를 코드 없이 백지에서 작성할 수 있을 때까지 반복 연습하는 것이 합격의 지름길입니다. 오늘 당장 백준 온라인 저지나 프로그래머스에서 각 유형별로 문제 3개씩만 풀어보세요. 이론과 실전의 간격이 빠르게 좁혀질 것입니다.
답글 남기기