코딩테스트 알고리즘 정리

코딩테스트 필수 알고리즘 총정리

코딩테스트에서 자주 등장하는 주요 알고리즘들을 정리해보았습니다. 각 알고리즘의 특징, 적용 상황, 그리고 예시 코드를 통해 실전에서 어떤 알고리즘을 선택해야 할지 파악할 수 있습니다.

목차

1. DFS (깊이 우선 탐색)
2. BFS (너비 우선 탐색)
3. 완전탐색
4. 백트래킹
5. 비트마스킹
6. 그리디
7. 이분탐색
8. DP (동적계획법)
9. 펜윅트리

1. DFS (깊이 우선 탐색)

핵심 개념

DFS는 그래프나 트리에서 한 경로를 끝까지 탐색한 후 다른 경로를 탐색하는 알고리즘입니다.

주요 특징

• 재귀 또는 스택을 이용하여 구현
• 메모리: O(V) (V: 정점의 개수)
• 시간복잡도: O(V + E) (E: 간선의 개수)

적용 상황

• 모든 경로를 방문해야 할 때
• 연결된 컴포넌트 찾기
• 사이클 탐지가 필요할 때

예시 코드

const dfs = (graph, start, visited = new Set()) => {
    visited.add(start);
    console.log(start);

    for (let neighbor of graph[start]) {
        if (!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
};

2. BFS (너비 우선 탐색)

핵심 개념

BFS는 시작점에서 가까운 정점부터 차례대로 탐색하는 알고리즘입니다.

주요 특징

• 큐를 이용하여 구현
• 최단 경로 보장
• 레벨 단위 탐색 가능

적용 상황

• 최단 거리/경로 찾기
• 레벨 단위로 탐색이 필요할 때
• 두 노드 사이의 최소 이동 횟수

예시 코드

const bfs = (graph, start) => {
    const visited = new Set([start]);
    const queue = [start];

    while (queue.length > 0) {
        const vertex = queue.shift();
        console.log(vertex);

        for (let neighbor of graph[vertex]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
};

3. 완전탐색

핵심 개념

가능한 모든 경우를 탐색하여 정답을 찾는 방법입니다.

주요 특징

• 모든 경우를 고려하므로 정확한 답 보장
• 시간복잡도가 높음 (보통 O(N!))
• 입력 크기가 작을 때 사용 가능

적용 상황

• N이 15 이하로 작은 경우
• 모든 경우를 고려해야 할 때
• 최적해를 보장해야 할 때

예시 코드

const permutations = (arr) => {
    if (arr.length <= 1) return [arr];

    const result = [];
    for (let i = 0; i < arr.length; i++) {
        const current = arr[i];
        const remaining = [...arr.slice(0, i), ...arr.slice(i + 1)];
        const perms = permutations(remaining);

        for (let perm of perms) {
            result.push([current, ...perm]);
        }
    }
    return result;
};

4. 백트래킹

핵심 개념

가지치기를 통해 불필요한 경우를 제외하고 탐색하는 방법입니다.

주요 특징

• 완전탐색의 최적화 버전
• 조건을 만족하지 않는 경우 즉시 중단
• 상태 공간 트리를 활용

적용 상황

• 제약 조건이 있는 완전탐색
• N-Queen 문제
• 조합/순열 문제

예시 코드

const solveNQueens = (n) => {
    const board = new Array(n).fill().map(() => new Array(n).fill('.'));
    const result = [];

    const isValid = (row, col) => {
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
            if (col - (row-i) >= 0 && board[i][col-(row-i)] === 'Q') return false;
            if (col + (row-i) < n && board[i][col+(row-i)] === 'Q') return false;
        }
        return true;
    };

    const backtrack = (row) => {
        if (row === n) {
            result.push(board.map(row => row.join('')));
            return;
        }

        for (let col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 'Q';
                backtrack(row + 1);
                board[row][col] = '.';
            }
        }
    };

    backtrack(0);
    return result;
};

5. 비트마스킹

핵심 개념

정수의 이진수 표현을 활용하여 집합을 효율적으로 표현하는 기법입니다.

주요 특징

• 빠른 집합 연산
• 메모리 효율적
• 32개 이하의 원소를 다룰 때 유용

적용 상황

• 작은 크기의 집합 처리
• DP 상태 압축
• 빠른 집합 연산이 필요할 때

예시 코드

const setBit = (num, pos) => num | (1 << pos);
const clearBit = (num, pos) => num & ~(1 << pos);
const toggleBit = (num, pos) => num ^ (1 << pos);
const checkBit = (num, pos) => (num & (1 << pos)) !== 0;

6. 그리디

핵심 개념

현재 상황에서 가장 좋아 보이는 선택을 하는 알고리즘입니다.

주요 특징

• 지역적 최적해가 전체 최적해가 되는 경우에 사용
• 빠른 실행 시간
• 정당성 증명이 중요

적용 상황

• 최적 부분 구조를 가질 때
• 정렬을 통해 해결 가능한 경우
• 선택의 순서가 중요할 때

예시 코드

const coinChange = (amount, coins) => {
    coins.sort((a, b) => b - a);
    let remaining = amount;
    const result = {};

    for (let coin of coins) {
        if (remaining >= coin) {
            result[coin] = Math.floor(remaining / coin);
            remaining %= coin;
        }
    }
    return result;
};

7. 이분탐색

핵심 개념

정렬된 배열에서 값을 찾거나 최적화 문제를 해결하는 알고리즘입니다.

주요 특징

• 빠른 검색 속도 (O(log N))
• 정렬된 데이터 필요
• 구현이 까다로울 수 있음

적용 상황

• 정렬된 배열에서 값 찾기
• 최적화 문제 (파라메트릭 서치)
• 값의 범위가 큰 경우

예시 코드

const binarySearch = (arr, target) => {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] === target) return mid;
        if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
};

8. DP (동적계획법)

핵심 개념

작은 부분 문제의 해를 저장하여 큰 문제를 해결하는 알고리즘입니다.

주요 특징

• 중복되는 부분 문제 활용
• 메모이제이션으로 성능 향상
• 최적 부분 구조 필요

적용 상황

• 최적화 문제
• 경우의 수 계산
• 부분 문제가 중복되는 경우

예시 코드

const fibonacci = (n) => {
    const dp = new Array(n + 1);
    dp[0] = 0;
    dp[1] = 1;

    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
};

9. 펜윅트리

핵심 개념

구간 합을 빠르게 계산하고 업데이트할 수 있는 자료구조입니다.

주요 특징

• 구간 합 계산: O(log N)
• 값 업데이트: O(log N)
• 1-based 인덱스 사용

적용 상황

• 구간 합 계산이 필요할 때
• 빈번한 업데이트가 있을 때
• 누적 합이 필요한 경우

예시 코드

class FenwickTree {
    constructor(n) {
        this.tree = new Array(n + 1).fill(0);
    }

    update(idx, delta) {
        while (idx < this.tree.length) {
            this.tree[idx] += delta;
            idx += idx & (-idx);
        }
    }

    sum(idx) {
        let sum = 0;
        while (idx > 0) {
            sum += this.tree[idx];
            idx -= idx & (-idx);
        }
        return sum;
    }

    rangeSum(l, r) {
        return this.sum(r) - this.sum(l - 1);
    }
}

알고리즘 선택 가이드

문제를 풀 때 다음 단계를 따라 적절한 알고리즘을 선택하세요:

1. 문제 크기 확인
   • N ≤ 15: 완전탐색 고려
   • 15 < N ≤ 100,000: 일반적인 알고리즘
   • N > 100,000: 효율적인 알고리즘 필요
2. 키워드 분석
   • "최단 경로" → BFS
   • "모든 경우" → 완전탐색/백트래킹
   • "최대/최소" → 그리디 또는 DP
   • "구간 합" → 펜윅트리
3. 시간 복잡도 검증
   • 제한 시간 내 해결 가능한지 확인
   • 메모리 제한 고려
4. 알고리즘 특성 고려
   • 부분 문제 중복 → DP
   • 정렬된 데이터 → 이분탐색
   • 선택의 순서 중요 → 그리디

🔎 기본 알고리즘 특징 표

알고리즘	주요 키워드	적용 상황	시간복잡도	특징/주의사항
DFS(깊이 우선 탐색)	• 경로 탐색• 사이클 검출• 연결 요소	• 모든 경로를 방문해야 할 때• 그래프/트리의 깊이 탐색• 백트래킹 구현	O(V+E)	• 재귀/스택 사용• 메모리: O(V)
BFS(너비 우선 탐색)	• 최단 경로• 최소 시간• 레벨 단위	• 최단 거리 찾기• 레벨별 탐색• 가까운 노드부터	O(V+E)	• 큐 사용• 메모리: O(V)
완전탐색	• 모든 경우• 가능한 모든• 조합/순열	• 크기가 작은 입력(N≤15)• 최적해 보장 필요• 모든 경우 확인	O(N!)	• 입력 크기 제한• 시간 제한 주의
백트래킹	• 가지치기• 조건 만족• 상태 공간	• 제약 조건이 있는 완전탐색• 최적화 문제• N-Queen 등	O(N!)	• 불필요한 탐색 제거• 조건 설계 중요
비트마스킹	• 상태 표현• 집합 연산• 메모리 최적화	• 작은 집합(크기≤32)• 빠른 집합 연산• DP 상태 압축	O(1)	• 비트 연산자 활용• 메모리 효율적
그리디	• 최적 선택• 정렬• 최대/최소	• 부분 최적해=전체 최적해• 정렬로 해결 가능• 선택의 순서	O(N log N)	• 정당성 증명 필요• 반례 검증 중요
이분탐색	• 최적화• 매개 변수• 정렬된 배열	• 정렬된 데이터• 최대값의 최소화• 파라메트릭 서치	O(log N)	• 정렬 필수• 구현 실수 주의
DP(동적계획법)	• 부분 문제• 메모이제이션• 최적 부분 구조	• 중복되는 부분 문제• 최적화 문제• 경우의 수	문제별 상이	• 점화식 도출• 상태 정의 중요
펜윅트리	• 구간 합• 업데이트• 누적 합	• 빈번한 업데이트• 구간 합 계산• 인덱스 트리	O(log N)	• 1-based 인덱스• 구현 난이도 높음

📌 알고리즘 선택 기준

1. 입력 크기에 따른 선택

입력 크기	추천 알고리즘	시간복잡도
N ≤ 15	완전탐색, 백트래킹	O(N!), O(2^N)
N ≤ 100,000	정렬, 그리디	O(N log N)
N ≤ 10,000,000	선형 탐색	O(N)
N > 10,000,000	이분탐색, 펜윅트리	O(log N)

2. 문제 유형별 키워드

키워드	추천 알고리즘
"최단 경로", "최소 시간"	BFS
"모든 경우", "가능한 모든"	완전탐색, 백트래킹
"최대값의 최소화"	이분탐색
"구간 합", "누적 합"	펜윅트리
"경우의 수", "최적값"	DP
"상태", "집합"	비트마스킹

3. 시간 제한에 따른 허용 시간복잡도

입력 크기	허용 시간복잡도
N ≤ 500	O(N^3)
N ≤ 2,000	O(N^2)
N ≤ 100,000	O(N log N)
N ≤ 10,000,000	O(N)
N > 10,000,000	O(log N)