코딩 테스트 패턴
15개 핵심 알고리즘 패턴으로 코딩 테스트를 정복하세요
array
0/3
string
0/2
tree
0/1
graph
0/4
dp
0/3
design
0/2
투 포인터
Two Pointers
정렬된 배열에서 두 개의 포인터를 양 끝 또는 같은 방향으로 이동시키며 조건을 만족하는 쌍이나 구간을 효율적으로 탐색하는 기법입니다. 브루트포스 O(n²)를 O(n)으로 줄일 수 있습니다.
슬라이딩 윈도우
Sliding Window
배열이나 문자열에서 연속된 부분 구간(윈도우)을 한 칸씩 밀면서 최적값을 찾는 기법입니다. 고정 크기와 가변 크기 두 가지 변형이 있으며, 중첩 반복문 없이 O(n)에 해결할 수 있습니다.
구간 병합
Interval Merge
시작점과 끝점으로 표현된 구간(interval)들을 정렬한 후, 겹치는 구간을 합치거나 새 구간을 삽입하는 기법입니다. 스케줄링, 회의실 배정 등 구간 관련 문제의 핵심 패턴입니다.
해시맵 활용
HashMap Pattern
해시맵(딕셔너리)을 사용하여 요소의 빈도수를 세거나, 이전에 본 값을 O(1)로 조회하는 기법입니다. 중복 검사, 그룹핑, 보완값 찾기 등 가장 범용적으로 사용되는 패턴입니다.
문자열 매칭
String Matching
문자열 내에서 패턴을 찾거나, 팰린드롬/아나그램 등 문자열 특성을 분석하는 기법입니다. 브루트포스부터 KMP, 라빈-카프 등 고급 알고리즘까지 면접에서 자주 출제됩니다.
이진 트리 순회
Tree Traversal
이진 트리의 노드를 체계적으로 방문하는 기법입니다. 전위(Pre), 중위(In), 후위(Post), 레벨(Level) 순회 4가지가 있으며, 재귀와 반복(스택/큐) 두 가지 구현 방식을 모두 알아야 합니다.
BFS (너비 우선 탐색)
BFS (Breadth-First Search)
큐를 사용하여 시작 노드에서 가까운 노드부터 탐색하는 기법입니다. 가중치가 없는 그래프에서 최단 경로를 보장하며, 레벨별 탐색이 필요한 문제에 적합합니다.
DFS (깊이 우선 탐색)
DFS (Depth-First Search)
스택 또는 재귀로 한 경로를 끝까지 탐색한 후 되돌아오는 기법입니다. 모든 경로 탐색, 연결 컴포넌트 카운팅, 백트래킹 문제에 적합하며, 구현이 직관적입니다.
이진 탐색
Binary Search
정렬된 데이터에서 탐색 범위를 절반씩 줄여가며 O(log n)에 답을 찾는 기법입니다. 단순 값 찾기뿐 아니라, 조건을 만족하는 최소/최대값을 찾는 "매개변수 탐색"이 코딩 테스트에서 핵심입니다.
위상 정렬
Topological Sort
DAG(방향 비순환 그래프)에서 선후 관계를 만족하는 순서를 결정하는 알고리즘입니다. 선수과목, 빌드 의존성, 작업 스케줄링 등 "순서가 정해진" 문제에서 사용됩니다.
1차원 DP
1D Dynamic Programming
하나의 상태 변수(보통 인덱스 i)로 정의되는 DP입니다. 이전 결과를 활용하여 현재 값을 계산하며, 피보나치부터 최적화 문제까지 DP의 기본이 됩니다. 공간 최적화로 O(1)까지 줄일 수 있습니다.
2차원 DP
2D Dynamic Programming
두 개의 상태 변수(i, j)로 정의되는 DP입니다. 격자 경로, 두 문자열 비교, 부분 구간 등의 문제에서 사용되며, 2차원 테이블을 채워가는 방식으로 풀이합니다.
배낭 문제
Knapsack Problem
제한된 용량(무게, 금액 등) 내에서 가치를 최대화하는 선택 문제입니다. 0/1 배낭(각 아이템 한 번)과 완전 배낭(무한 사용)으로 나뉘며, 부분집합 합(Subset Sum)도 변형입니다.
스택/큐 활용
Stack/Queue Pattern
스택(LIFO)과 큐(FIFO)의 특성을 활용하여 괄호 매칭, 단조 스택(Monotonic Stack), 히스토리 관리 등을 효율적으로 처리하는 기법입니다. 특히 단조 스택은 "다음으로 큰/작은 원소" 문제의 핵심입니다.
그리디
Greedy Algorithm
매 순간 가장 최적인 선택을 하여 전체 최적해를 구하는 기법입니다. DP와 달리 이전 선택을 재고하지 않으며, "지역 최적 = 전역 최적"이 성립할 때만 사용 가능합니다. 증명이 중요합니다.