코딩테스트 알고리즘 완전정복: 핵심 개념 총정리

코딩테스트 알고리즘 완전정복

코딩테스트에서 자주 출제되는 핵심 알고리즘과 자료구조를 한 곳에 모았습니다. 각 알고리즘의 핵심 개념과 언제 사용하는지만 정확히 파악하면, 문제를 보는 순간 어떤 접근법을 써야 할지 바로 알 수 있습니다.

그래프 탐색

DFS (Depth-First Search) - 깊이 우선 탐색

핵심 개념:

한 방향으로 끝까지 탐색한 후, 막히면 되돌아와서 다른 경로 탐색
스택 또는 재귀로 구현

언제 사용?

✅ 모든 경로를 탐색해야 할 때
✅ 경로의 특성이 중요할 때 (백트래킹)
✅ 사이클 탐지
✅ 위상 정렬
✅ 연결 요소 찾기

시간 복잡도: O(V + E) - V: 정점, E: 간선

BFS (Breadth-First Search) - 너비 우선 탐색

핵심 개념:

가까운 노드부터 차례대로 탐색 (레벨 단위)
큐로 구현

언제 사용?

✅ 최단 거리를 구해야 할 때 (가중치 없는 그래프)
✅ 레벨별로 처리해야 할 때
✅ 최소 이동 횟수
✅ 최소 단계 수

시간 복잡도: O(V + E)

🎮 DFS vs BFS 시각화

아래 시각화로 두 알고리즘의 차이를 직접 확인하세요.

탐색 순서

알고리즘을 선택하고 재생 버튼을 눌러보세요

미방문

대기중 (Queue/Stack)

현재 방문

방문 완료

핵심 차이: DFS는 깊이 우선 (세로로), BFS는 너비 우선 (가로로) 탐색합니다.

정렬

퀵 정렬 (Quick Sort)

핵심 개념:

**피벗(Pivot)**을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
분할된 부분을 재귀적으로 정렬

특징:

평균 O(n log n), 최악 O(n²)
불안정 정렬 (같은 값의 순서가 바뀔 수 있음)
제자리 정렬 (추가 메모리 적음)

언제 사용?

일반적인 정렬이 필요할 때 (평균적으로 가장 빠름)

병합 정렬 (Merge Sort)

핵심 개념:

배열을 반으로 나누고, 각각 정렬한 후 병합
분할 정복 방식

특징:

항상 O(n log n) (최악의 경우에도 보장)
안정 정렬 (같은 값의 순서 유지)
추가 메모리 O(n) 필요

언제 사용?

안정 정렬이 필요할 때
최악의 경우에도 O(n log n)을 보장해야 할 때

힙 정렬 (Heap Sort)

핵심 개념:

힙(Heap) 자료구조를 이용한 정렬
최대 힙을 만들고, 루트를 하나씩 꺼내서 정렬

특징:

항상 O(n log n)
불안정 정렬
제자리 정렬

언제 사용?

메모리가 제한적이면서 O(n log n)을 보장해야 할 때

🎮 정렬 알고리즘 시각화

아래 시각화로 세 가지 정렬 알고리즘의 동작 방식을 직접 확인하세요.

속도:

기본

비교 중

교환 중

피벗

정렬 완료

핵심 차이: 퀵 정렬은 피벗 기준 분할, 병합 정렬은 분할 후 병합, 힙 정렬은 힙 구조 활용

탐색

이진 탐색 (Binary Search)

핵심 개념:

정렬된 배열에서 중간값과 비교하며 탐색 범위를 절반씩 줄임
탐색 범위: [left, right]

특징:

O(log n) - 매우 빠름
반드시 정렬된 상태여야 함

언제 사용?

✅ 정렬된 배열에서 특정 값 찾기
✅ "~이상", "~이하" 조건의 경계값 찾기
✅ 파라메트릭 서치

핵심 패턴:

while left <= right:
    mid = (left + right) // 2
    if 조건:
        answer = mid
        # 범위 조정
    else:
        # 범위 조정

🎮 이진 탐색 시각화

정렬된 배열에서 이진 탐색이 어떻게 동작하는지 확인하세요.

찾을 값:

속도:

탐색 가능

Left / Right

Mid (비교 중)

제외됨

찾음!

핵심: 매번 탐색 범위를 절반으로 줄여 O(log n) 시간에 탐색합니다.

파라메트릭 서치 (Parametric Search)

핵심 개념:

최적화 문제를 결정 문제로 변환
"최소값의 최대" 또는 "최대값의 최소"를 구할 때 사용
이진 탐색으로 답의 범위를 좁혀감

언제 사용?

✅ "~의 최소값을 최대화"
✅ "~의 최대값을 최소화"
✅ 조건을 만족하는 최소/최대값

예시:

나무 자르기 (최대 높이 구하기)
공유기 설치 (최대 거리 구하기)
예산 배분 (최대 예산 구하기)

동적 프로그래밍

DP (Dynamic Programming)

핵심 개념:

큰 문제를 작은 부분 문제로 나누어 해결
부분 문제의 결과를 메모이제이션하여 재사용
점화식을 세우는 것이 핵심

특징:

중복 계산 제거 → 시간 복잡도 대폭 감소
메모리 사용 (테이블 저장)

언제 사용?

✅ 최적 부분 구조: 부분 문제의 최적해로 전체 최적해를 구할 수 있음
✅ 중복 부분 문제: 같은 문제가 반복적으로 등장
✅ "최대", "최소", "개수" 구하기

DP vs 분할정복:

DP: 부분 문제가 중복됨 (메모이제이션 필요)
분할정복: 부분 문제가 독립적 (중복 없음)

대표 유형:

피보나치 수열
배낭 문제 (Knapsack)
최장 증가 부분 수열 (LIS)
최장 공통 부분 수열 (LCS)
편집 거리 (Edit Distance)

🎮 DP 시각화 - 피보나치 수열

동적 프로그래밍이 어떻게 중복 계산을 제거하는지 확인하세요.

N 값:

속도:

💡동적 프로그래밍 (DP): 작은 부분 문제의 결과를 테이블에 저장하고 재사용하여, 중복 계산을 제거합니다. 피보나치는 O(2ⁿ) → O(n)으로 최적화됩니다.

미계산

계산 중

참조 중

계산 완료

핵심: 작은 문제의 결과를 저장하고 재사용하여 O(2ⁿ) → O(n)으로 최적화합니다.

그리디

Greedy Algorithm

핵심 개념:

매 순간 최선의 선택을 하여 최종 해답에 도달
한 번 선택하면 번복하지 않음
증명이 중요 (항상 최적해를 보장하는지 확인 필요)

특징:

구현이 간단하고 빠름
모든 문제에 적용 불가 (최적해 보장 X인 경우 많음)

언제 사용?

✅ 탐욕적 선택 속성: 매 순간의 최선이 전체 최선
✅ 최적 부분 구조: 부분 문제의 최적해가 전체 최적해

그리디 vs DP:

그리디: 현재 최선 → 미래 고려 X
DP: 모든 경우 고려 → 최적해 보장

대표 유형:

활동 선택 문제
거스름돈 문제
회의실 배정
최소 신장 트리 (Kruskal, Prim)

분할 정복

Divide and Conquer

핵심 개념:

문제를 작은 부분 문제로 분할
각 부분 문제를 독립적으로 해결
결과를 합쳐서 전체 문제 해결

특징:

재귀적 구조
부분 문제가 중복되지 않음 (DP와의 차이)

언제 사용?

✅ 문제를 독립적인 부분으로 나눌 수 있을 때
✅ 부분 문제의 해를 합쳐 전체 해를 구할 수 있을 때

대표 예시:

병합 정렬
퀵 정렬
이진 탐색
거듭제곱 (분할 정복으로 O(log n))

백트래킹

Backtracking

핵심 개념:

모든 경우의 수를 탐색하되, **가지치기(Pruning)**로 불필요한 탐색 제거
DFS + 조건 검사 + 되돌리기

특징:

완전 탐색보다 빠름 (가지치기)
여전히 최악의 경우 지수 시간

언제 사용?

✅ 모든 경우를 확인해야 하지만, 조건으로 제외 가능한 경우가 많을 때
✅ "가능한 모든 조합" 찾기
✅ 제약 조건이 복잡한 문제

핵심 패턴:

1. 선택 (Choose)
2. 탐색 (Explore)
3. 되돌리기 (Unchoose)

대표 유형:

N-Queen
스도쿠
순열/조합 생성
부분집합 합

투 포인터

Two Pointers

핵심 개념:

두 개의 포인터를 이용해 배열/리스트를 효율적으로 탐색
보통 O(n²) → O(n)으로 최적화

패턴:

1. 양 끝에서 시작 (대칭 탐색)

left = 0, right = n-1
while left < right:
    # 조건에 따라 left++ 또는 right--

2. 같은 방향 (구간 탐색)

left = 0, right = 0
while right < n:
    # 조건에 따라 left 또는 right 이동

언제 사용?

✅ 정렬된 배열에서 두 수의 합 찾기
✅ 구간 합이 특정 조건을 만족하는 경우 찾기
✅ 연속된 부분 배열 문제

🎮 투 포인터 시각화

두 포인터가 어떻게 이동하며 목표값을 찾는지 확인하세요.

목표 합:

속도:

💡투 포인터 알고리즘: 정렬된 배열에서 두 포인터를 양 끝에서 시작하여, 합이 목표값보다 작으면 왼쪽 포인터를 오른쪽으로, 크면 오른쪽 포인터를 왼쪽으로 이동합니다.

미확인

Left 포인터

Right 포인터

확인 완료

정답!

핵심: 정렬된 배열에서 양 끝의 포인터를 조건에 따라 이동하여 O(n) 시간에 해결합니다.

슬라이딩 윈도우

Sliding Window

핵심 개념:

고정 크기 또는 가변 크기의 윈도우를 이동시키며 탐색
윈도우 내부의 합/최대/최소 등을 효율적으로 계산

특징:

O(n²) → O(n) 최적화
투 포인터의 특수한 형태

언제 사용?

✅ 연속된 부분 배열의 합/곱/최대/최소
✅ 고정 크기 윈도우 내의 통계
✅ 문자열 패턴 매칭

패턴:

고정 크기 윈도우:

window_sum = sum(arr[0:k])
for i in range(k, n):
    window_sum += arr[i] - arr[i-k]

가변 크기 윈도우:

left = 0
for right in range(n):
    # 윈도우 확장
    while 조건 위반:
        # 윈도우 축소 (left++)

🎮 슬라이딩 윈도우 시각화

고정 크기 윈도우가 어떻게 이동하며 최대값을 찾는지 확인하세요.

윈도우 크기:

속도:

💡슬라이딩 윈도우: 고정 크기의 윈도우를 한 칸씩 이동하며, 이전 계산 결과를 재사용하여 O(n) 시간에 최대/최소값을 찾습니다.

미확인

현재 윈도우

최대 합 윈도우

지나감

핵심: 윈도우를 한 칸씩 이동하며 이전 계산 결과를 재사용하여 O(n) 시간에 해결합니다.

자료구조

Stack (스택)

핵심 개념:

LIFO (Last In First Out) - 후입선출
push, pop, peek

언제 사용?

✅ 괄호 검사
✅ 함수 호출 (재귀)
✅ 되돌리기 (Undo)
✅ DFS 구현

Queue (큐)

핵심 개념:

FIFO (First In First Out) - 선입선출
enqueue, dequeue

언제 사용?

✅ BFS 구현
✅ 순서대로 처리
✅ 버퍼

Priority Queue / Heap (우선순위 큐 / 힙)

핵심 개념:

우선순위가 높은 요소를 먼저 처리
힙(Heap) 자료구조로 구현
Min Heap: 최소값 우선
Max Heap: 최대값 우선

특징:

삽입: O(log n)
삭제 (최소/최대값): O(log n)
조회 (최소/최대값): O(1)

언제 사용?

✅ 최소값/최대값을 반복적으로 꺼내야 할 때
✅ 다익스트라 알고리즘
✅ 중간값 찾기 (두 개의 힙 사용)
✅ K번째 큰/작은 수

Tree (트리)

핵심 개념:

계층적 구조
루트, 부모, 자식, 리프 노드
이진 트리, 이진 탐색 트리 (BST)

순회 방법:

전위 순회 (Preorder): 루트 → 왼쪽 → 오른쪽
중위 순회 (Inorder): 왼쪽 → 루트 → 오른쪽 (BST에서 정렬된 순서)
후위 순회 (Postorder): 왼쪽 → 오른쪽 → 루트

언제 사용?

✅ 계층적 데이터 표현
✅ 빠른 검색/삽입/삭제 (BST)
✅ 범위 쿼리

🎯 알고리즘 선택 가이드

문제 키워드	추천 알고리즘
"최단 거리", "최소 이동"	BFS
"모든 경로", "가능한 모든"	DFS, 백트래킹
"최대", "최소", "개수" (최적화)	DP
"정렬된 배열", "~이상/이하"	이진 탐색
"~의 최소를 최대화"	파라메트릭 서치
"매 순간 최선"	그리디
"연속된 부분 배열"	투 포인터, 슬라이딩 윈도우
"우선순위", "K번째"	힙

💡 핵심 정리

문제를 보면 1초 안에 알고리즘 카테고리를 파악하세요
시간 복잡도를 항상 고려하세요 (입력 크기 확인)
자료구조 선택이 알고리즘만큼 중요합니다
예외 케이스를 항상 생각하세요 (빈 배열, 크기 1, 중복 등)

코딩테스트는 결국 패턴 인식입니다. 각 알고리즘의 핵심 개념과 사용 시점만 정확히 알면, 대부분의 문제는 풀 수 있습니다! 🚀