투포인터, 슬라이딩 윈도우, BFS/DFS, DP 등 15개 코딩 테스트 핵심 패턴. 접근법, 시간복잡도, 의사코드, 대표 문제까지.
투포인터, 슬라이딩 윈도우, BFS/DFS, 이진 탐색, 동적 프로그래밍이 가장 빈출 패턴입니다. 이 5개를 먼저 익히면 대부분의 문제에 접근할 수 있습니다.
쉬운 패턴(투포인터, 해시맵)부터 시작해 중급(BFS/DFS, 이진 탐색, 슬라이딩 윈도우)을 거쳐 고급(DP, 위상 정렬)으로 진행하세요.
투포인터, 슬라이딩 윈도우, BFS/DFS, 이진 탐색, 동적 프로그래밍이 가장 빈출 패턴입니다. 이 5개를 먼저 익히면 대부분의 문제에 접근할 수 있습니다.
쉬운 패턴(투포인터, 해시맵)부터 시작해 중급(BFS/DFS, 이진 탐색, 슬라이딩 윈도우)을 거쳐 고급(DP, 위상 정렬)으로 진행하세요.
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 (Breadth-First Search)
큐를 사용하여 시작 노드에서 가까운 노드부터 탐색하는 기법입니다. 가중치가 없는 그래프에서 최단 경로를 보장하며, 레벨별 탐색이 필요한 문제에 적합합니다.
DFS (Depth-First Search)
스택 또는 재귀로 한 경로를 끝까지 탐색한 후 되돌아오는 기법입니다. 모든 경로 탐색, 연결 컴포넌트 카운팅, 백트래킹 문제에 적합하며, 구현이 직관적입니다.
Binary Search
정렬된 데이터에서 탐색 범위를 절반씩 줄여가며 O(log n)에 답을 찾는 기법입니다. 단순 값 찾기뿐 아니라, 조건을 만족하는 최소/최대값을 찾는 "매개변수 탐색"이 코딩 테스트에서 핵심입니다.
Topological Sort
DAG(방향 비순환 그래프)에서 선후 관계를 만족하는 순서를 결정하는 알고리즘입니다. 선수과목, 빌드 의존성, 작업 스케줄링 등 "순서가 정해진" 문제에서 사용됩니다.
1D Dynamic Programming
하나의 상태 변수(보통 인덱스 i)로 정의되는 DP입니다. 이전 결과를 활용하여 현재 값을 계산하며, 피보나치부터 최적화 문제까지 DP의 기본이 됩니다. 공간 최적화로 O(1)까지 줄일 수 있습니다.
2D Dynamic Programming
두 개의 상태 변수(i, j)로 정의되는 DP입니다. 격자 경로, 두 문자열 비교, 부분 구간 등의 문제에서 사용되며, 2차원 테이블을 채워가는 방식으로 풀이합니다.
Knapsack Problem
제한된 용량(무게, 금액 등) 내에서 가치를 최대화하는 선택 문제입니다. 0/1 배낭(각 아이템 한 번)과 완전 배낭(무한 사용)으로 나뉘며, 부분집합 합(Subset Sum)도 변형입니다.
Stack/Queue Pattern
스택(LIFO)과 큐(FIFO)의 특성을 활용하여 괄호 매칭, 단조 스택(Monotonic Stack), 히스토리 관리 등을 효율적으로 처리하는 기법입니다. 특히 단조 스택은 "다음으로 큰/작은 원소" 문제의 핵심입니다.
Greedy Algorithm
매 순간 가장 최적인 선택을 하여 전체 최적해를 구하는 기법입니다. DP와 달리 이전 선택을 재고하지 않으며, "지역 최적 = 전역 최적"이 성립할 때만 사용 가능합니다. 증명이 중요합니다.