본문으로 건너뛰기

완전탐색(Brute Force)

완전탐색이란?​

완전탐색은 가능한 모든 경우를 다 확인해보는 방법입니다.

마치 잃어버린 열쇠를 찾기 위해 집 안의 모든 곳을 다 뒤져보는 것과 같습니다.

  • 확실하게 답을 찾을 수 있습니다
  • 하지만 시간이 오래 걸릴 수 있습니다
문제: [1, 2, 3] 배열에서 합이 3인 두 수 찾기

완전탐색 접근:
1 + 2 = 3 ✓ (답 찾음!)
1 + 3 = 4
2 + 3 = 5

모든 경우를 확인해서 답을 찾았습니다.

기본 구현 방법들​

이중 반복문​

// 배열에서 합이 target인 두 수의 인덱스 찾기
function twoSumBruteForce(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
}

const nums = [2, 7, 11, 15];
const target = 9;
console.log(twoSumBruteForce(nums, target)); // [0, 1]

재귀를 이용한 완전탐색​

// 배열의 모든 부분집합 구하기
function getAllSubsets(arr) {
    const result = [];
    
    function backtrack(index, currentSubset) {
        if (index === arr.length) {
            result.push([...currentSubset]);
            return;
        }
        
        // 현재 원소를 포함하지 않는 경우
        backtrack(index + 1, currentSubset);
        
        // 현재 원소를 포함하는 경우
        currentSubset.push(arr[index]);
        backtrack(index + 1, currentSubset);
        currentSubset.pop();
    }
    
    backtrack(0, []);
    return result;
}

console.log(getAllSubsets([1, 2, 3]));
// [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

순열 생성​

// 배열의 모든 순열 구하기
function getAllPermutations(arr) {
    const result = [];
    
    function backtrack(currentPerm, remaining) {
        if (remaining.length === 0) {
            result.push([...currentPerm]);
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            currentPerm.push(remaining[i]);
            const newRemaining = remaining.filter((_, index) => index !== i);
            backtrack(currentPerm, newRemaining);
            currentPerm.pop();
        }
    }
    
    backtrack([], arr);
    return result;
}

console.log(getAllPermutations([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

성능 비교​

Two Sum 문제 비교​

function compareTwoSumMethods() {
    const size = 5000;
    const nums = Array.from({length: size}, () => Math.floor(Math.random() * 1000));
    const target = nums[0] + nums[1]; // 답이 있도록 설정
    
    // 완전탐색 방법
    function twoSumBruteForce(nums, target) {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] === target) {
                    return [i, j];
                }
            }
        }
        return [];
    }
    
    // 해시맵 방법
    function twoSumHashMap(nums, target) {
        const map = new Map();
        for (let i = 0; i < nums.length; i++) {
            const complement = target - nums[i];
            if (map.has(complement)) {
                return [map.get(complement), i];
            }
            map.set(nums[i], i);
        }
        return [];
    }
    
    // 정렬 + 투 포인터 방법
    function twoSumTwoPointers(nums, target) {
        const indexed = nums.map((num, i) => [num, i]).sort((a, b) => a[0] - b[0]);
        let left = 0, right = indexed.length - 1;
        
        while (left < right) {
            const sum = indexed[left][0] + indexed[right][0];
            if (sum === target) {
                return [indexed[left][1], indexed[right][1]].sort((a, b) => a - b);
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return [];
    }
    
    // 성능 테스트
    let start = performance.now();
    twoSumBruteForce(nums, target);
    let end = performance.now();
    const bruteForceTime = end - start;
    
    start = performance.now();
    twoSumHashMap(nums, target);
    end = performance.now();
    const hashMapTime = end - start;
    
    start = performance.now();
    twoSumTwoPointers(nums, target);
    end = performance.now();
    const twoPointersTime = end - start;
    
    console.log(`완전탐색: ${bruteForceTime.toFixed(2)}ms`);
    console.log(`해시맵: ${hashMapTime.toFixed(2)}ms`);
    console.log(`투 포인터: ${twoPointersTime.toFixed(2)}ms`);
}

해시맵 방법이 가장 빠르고, 완전탐색은 가장 느립니다

부분집합 생성 비교​

function compareSubsetMethods() {
    const arr = [1, 2, 3, 4, 5, 6, 7, 8];
    
    // 재귀 방법
    function subsetsRecursive(arr) {
        const result = [];
        
        function backtrack(index, current) {
            if (index === arr.length) {
                result.push([...current]);
                return;
            }
            
            backtrack(index + 1, current);
            current.push(arr[index]);
            backtrack(index + 1, current);
            current.pop();
        }
        
        backtrack(0, []);
        return result;
    }
    
    // 비트마스크 방법
    function subsetsBitmask(arr) {
        const result = [];
        const n = arr.length;
        
        for (let mask = 0; mask < (1 << n); mask++) {
            const subset = [];
            for (let i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    subset.push(arr[i]);
                }
            }
            result.push(subset);
        }
        
        return result;
    }
    
    // 반복적 방법
    function subsetsIterative(arr) {
        let result = [[]];
        
        for (let num of arr) {
            const newSubsets = result.map(subset => [...subset, num]);
            result = result.concat(newSubsets);
        }
        
        return result;
    }
    
    // 성능 테스트
    let start = performance.now();
    subsetsRecursive(arr);
    let end = performance.now();
    const recursiveTime = end - start;
    
    start = performance.now();
    subsetsBitmask(arr);
    end = performance.now();
    const bitmaskTime = end - start;
    
    start = performance.now();
    subsetsIterative(arr);
    end = performance.now();
    const iterativeTime = end - start;
    
    console.log(`재귀 방법: ${recursiveTime.toFixed(2)}ms`);
    console.log(`비트마스크: ${bitmaskTime.toFixed(2)}ms`);
    console.log(`반복적 방법: ${iterativeTime.toFixed(2)}ms`);
}

비트마스크 방법이 가장 빠르고 메모리 효율적입니다

최적화 기법들​

가지치기(Pruning)​

// N-Queen 문제 (완전탐색 + 가지치기)
function solveNQueens(n) {
    const result = [];
    const board = Array(n).fill().map(() => Array(n).fill('.'));
    
    function isValid(row, col) {
        // 같은 열에 퀸이 있는지 확인
        for (let i = 0; i < row; i++) {
            if (board[i][col] === 'Q') return false;
        }
        
        // 왼쪽 대각선 확인
        for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] === 'Q') return false;
        }
        
        // 오른쪽 대각선 확인
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] === 'Q') return false;
        }
        
        return true;
    }
    
    function 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;
}

console.log(solveNQueens(4));

메모이제이션​

// 피보나치 수열 (완전탐색 vs 메모이제이션)
function compareFibonacci() {
    // 완전탐색 (매우 느림)
    function fibBruteForce(n) {
        if (n <= 1) return n;
        return fibBruteForce(n - 1) + fibBruteForce(n - 2);
    }
    
    // 메모이제이션
    function fibMemo(n, memo = {}) {
        if (n <= 1) return n;
        if (memo[n] !== undefined) return memo[n];
        
        memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
        return memo[n];
    }
    
    // 반복문 (가장 빠름)
    function fibIterative(n) {
        if (n <= 1) return n;
        let prev = 0, curr = 1;
        for (let i = 2; i <= n; i++) {
            [prev, curr] = [curr, prev + curr];
        }
        return curr;
    }
    
    const n = 35;
    
    let start = performance.now();
    fibBruteForce(n);
    let end = performance.now();
    const bruteTime = end - start;
    
    start = performance.now();
    fibMemo(n);
    end = performance.now();
    const memoTime = end - start;
    
    start = performance.now();
    fibIterative(n);
    end = performance.now();
    const iterTime = end - start;
    
    console.log(`완전탐색: ${bruteTime.toFixed(2)}ms`);
    console.log(`메모이제이션: ${memoTime.toFixed(2)}ms`);
    console.log(`반복문: ${iterTime.toFixed(2)}ms`);
}

메모이제이션을 사용하면 완전탐색도 매우 빨라집니다

실제 문제 예시​

조합 문제​

// n개 중 r개 선택하는 모든 조합
function getCombinations(arr, r) {
    const result = [];
    
    function combine(start, current) {
        if (current.length === r) {
            result.push([...current]);
            return;
        }
        
        for (let i = start; i < arr.length; i++) {
            current.push(arr[i]);
            combine(i + 1, current);
            current.pop();
        }
    }
    
    combine(0, []);
    return result;
}

console.log(getCombinations([1, 2, 3, 4], 2));
// [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

문자열 순열​

// 문자열의 모든 순열 생성
function getStringPermutations(str) {
    const result = [];
    const chars = str.split('');
    
    function permute(current, remaining) {
        if (remaining.length === 0) {
            result.push(current);
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            const newCurrent = current + remaining[i];
            const newRemaining = remaining.slice(0, i) + remaining.slice(i + 1);
            permute(newCurrent, newRemaining);
        }
    }
    
    permute('', str);
    return result;
}

console.log(getStringPermutations('abc'));
// ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

스도쿠 해결​

function solveSudoku(board) {
    function isValid(board, row, col, num) {
        // 행 확인
        for (let i = 0; i < 9; i++) {
            if (board[row][i] === num) return false;
        }
        
        // 열 확인
        for (let i = 0; i < 9; i++) {
            if (board[i][col] === num) return false;
        }
        
        // 3x3 박스 확인
        const boxRow = Math.floor(row / 3) * 3;
        const boxCol = Math.floor(col / 3) * 3;
        for (let i = boxRow; i < boxRow + 3; i++) {
            for (let j = boxCol; j < boxCol + 3; j++) {
                if (board[i][j] === num) return false;
            }
        }
        
        return true;
    }
    
    function solve(board) {
        for (let row = 0; row < 9; row++) {
            for (let col = 0; col < 9; col++) {
                if (board[row][col] === '.') {
                    for (let num = '1'; num <= '9'; num++) {
                        if (isValid(board, row, col, num)) {
                            board[row][col] = num;
                            
                            if (solve(board)) {
                                return true;
                            }
                            
                            board[row][col] = '.'; // 백트래킹
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    solve(board);
    return board;
}

완전탐색 vs 다른 알고리즘​

최대 부배열 합 문제​

function compareMaxSubarraySum() {
    const arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
    
    // 완전탐색 O(n³)
    function maxSubarrayBruteForce(arr) {
        let maxSum = -Infinity;
        
        for (let i = 0; i < arr.length; i++) {
            for (let j = i; j < arr.length; j++) {
                let sum = 0;
                for (let k = i; k <= j; k++) {
                    sum += arr[k];
                }
                maxSum = Math.max(maxSum, sum);
            }
        }
        
        return maxSum;
    }
    
    // 개선된 완전탐색 O(n²)
    function maxSubarrayBetter(arr) {
        let maxSum = -Infinity;
        
        for (let i = 0; i < arr.length; i++) {
            let sum = 0;
            for (let j = i; j < arr.length; j++) {
                sum += arr[j];
                maxSum = Math.max(maxSum, sum);
            }
        }
        
        return maxSum;
    }
    
    // 카데인 알고리즘 O(n)
    function maxSubarrayKadane(arr) {
        let maxSum = arr[0];
        let currentSum = arr[0];
        
        for (let i = 1; i < arr.length; i++) {
            currentSum = Math.max(arr[i], currentSum + arr[i]);
            maxSum = Math.max(maxSum, currentSum);
        }
        
        return maxSum;
    }
    
    // 성능 테스트
    let start = performance.now();
    maxSubarrayBruteForce(arr);
    let end = performance.now();
    const bruteTime = end - start;
    
    start = performance.now();
    maxSubarrayBetter(arr);
    end = performance.now();
    const betterTime = end - start;
    
    start = performance.now();
    maxSubarrayKadane(arr);
    end = performance.now();
    const kadaneTime = end - start;
    
    console.log(`O(n³) 완전탐색: ${bruteTime.toFixed(4)}ms`);
    console.log(`O(n²) 완전탐색: ${betterTime.toFixed(4)}ms`);
    console.log(`O(n) 카데인: ${kadaneTime.toFixed(4)}ms`);
}

효율적인 알고리즘이 있다면 완전탐색보다 그것을 사용하는 것이 좋습니다

언제 완전탐색을 사용하나요?​

사용하기 좋은 경우​

  • 데이터 크기가 작을 때 (보통 n ≤ 20)
  • 다른 효율적인 알고리즘을 모를 때
  • 정확한 답이 필요할 때
  • 문제의 구조가 복잡해서 최적화가 어려울 때

피해야 하는 경우​

  • 데이터 크기가 클 때
  • 시간 제한이 엄격할 때
  • 더 효율적인 알고리즘이 명확히 존재할 때

시간 복잡도 예시​

// 다양한 완전탐색의 시간 복잡도
function timeComplexityExamples() {
    console.log("완전탐색 시간 복잡도 예시:");
    console.log("- 이중 반복문: O(n²)");
    console.log("- 삼중 반복문: O(n³)");
    console.log("- 모든 부분집합: O(2ⁿ)");
    console.log("- 모든 순열: O(n!)");
    console.log("- 조합: O(C(n,r))");
    
    // 실제 실행 시간 비교 (작은 n으로)
    const n = 10;
    
    console.log(`\nn = ${n}일 때 예상 연산 횟수:`);
    console.log(`O(n²): ${n * n}회`);
    console.log(`O(n³): ${n * n * n}회`);
    console.log(`O(2ⁿ): ${Math.pow(2, n)}회`);
    
    // n!은 너무 크므로 작은 값으로
    const smallN = 7;
    let factorial = 1;
    for (let i = 1; i <= smallN; i++) {
        factorial *= i;
    }
    console.log(`O(n!) (n=${smallN}): ${factorial}회`);
}

완전탐색은 가장 기본적이면서도 확실한 방법입니다. 비효율적일 수 있지만, 문제를 이해하고 해결 방법을 찾는 첫 번째 단계로 매우 유용합니다.