완전탐색 vs 그리디 vs 백트래킹: 코딩테스트 알고리즘 완벽 가이드

입사를 위한 코딩테스트를 준비하면서 가장 답답했던 부분이 뭘까요? 바로 "이 문제는 어떤 알고리즘을 써야 하지?"라는 고민입니다. 특히 완전탐색, 그리디, 백트래킹은 직관적으로 비슷해 보이면서도 완전히 다른 접근 방식을 가지고 있어서, 많은 사람들이 헷갈려 합니다.
 
저도 처음 이 세 가지를 공부할 때 계속 섞어서 생각했거든요. "다 모든 경우를 다 확인하는 거 아닌가?" 이런 식으로요. 하지만 실제로는 각각의 알고리즘이 문제를 푸는 방식이 완전히 다르고, 효율성 측면에서도 큰 차이가 있습니다.
 
이 글은 제가 코딩테스트를 준비하면서 깨달은 것들과 실제로 문제를 풀면서 적용한 경험을 바탕으로 작성했습니다. 함께 이 세 가지 알고리즘의 차이를 명확히 하고, 언제 어떤 것을 사용해야 하는지 정확히 알아봅시다.

세 알고리즘의 기본 개념부터 이해하기

완전탐색(Brute Force)이란?

완전탐색은 가장 직관적인 방법입니다. 말 그대로 모든 가능한 경우를 다 확인해서 답을 찾는 것이죠.
 
예를 들어, 1부터 100까지의 숫자 중에서 3의 배수를 모두 찾으라고 하면, 1부터 100까지 하나하나 체크하는 식입니다. 비효율적으로 들리겠지만, 문제의 범위가 작거나 다른 최적화 방법이 없을 때는 이게 정답입니다.
 
완전탐색의 가장 큰 특징은 "일단 모든 경우의 수를 살펴본다"는 것입니다. 시간이 걸리더라도 답을 반드시 찾을 수 있다는 장점이 있지만, 데이터가 조금만 많아져도 매우 비효율적이 된다는 단점이 있습니다.

그리디(Greedy) 알고리즘이란?

그리디는 "현재의 최적선택이 전체의 최적선택을 만든다"는 가정 하에 작동하는 알고리즘입니다. 각 단계에서 가장 좋아 보이는 선택을 하고, 그 선택이 이전 단계로 돌아가 다시 고려되지 않습니다.
 
동전 거스름돈 문제를 생각해보세요. 큰 단위 동전부터 최대한 많이 사용하면 최소 개수의 동전으로 거스름돈을 만들 수 있습니다. 이게 그리디의 방식입니다.
 
그리디의 핵심은 "지금 당장 최고의 선택을 한다"는 것입니다. 매우 빠르고 효율적이지만, 그 문제가 정말로 그리디로 풀리는 문제인지 증명해야 한다는 어려움이 있습니다.

백트래킹(Backtracking)이란?

백트래킹은 "가능한 모든 경우를 탐색하되, 불가능한 경우는 미리 제외하고 진행"하는 방식입니다.
 
예를 들어, 스도쿠를 푼다고 생각해보세요. 한 칸에 숫자를 넣으면서 진행하다가, "어? 이 상태에서는 절대 해답이 없겠다"는 걸 깨닫으면 그 길을 포기하고 다른 길을 시도합니다. 이게 바로 백트래킹입니다.
 
백트래킹의 특징은 "가능성이 없는 경로는 탐색하지 않는다"는 것입니다. 완전탐색보다는 효율적이지만, 여전히 탐색 범위가 클 수 있습니다.

세 알고리즘을 정확히 구분하기

지금까지의 설명이 너무 개념적이었다면, 이제 실제로 어떻게 다른지 보여드리겠습니다.

예제: N개의 숫자 중에서 합이 K가 되는 부분집합 찾기

완전탐색으로 푼다면

def brute_force(numbers, target):
    n = len(numbers)

    result = []
    
    # 모든 부분집합을 생성 (2^n개)
    for mask in range(1 << n):
        subset = []
        total = 0
        for i in range(n):
            if mask & (1 << i):
                subset.append(numbers[i])
                total += numbers[i])        
        if total == target:
            result.append(subset)    

    return result

완전탐색은 정말 간단합니다. N개의 숫자가 있으면 2^N개의 부분집합을 모두 만들어서 합을 확인합니다. 정확하지만 느립니다.

백트래킹으로 푼다면

def backtracking(numbers, target, index=0, current=[], current_sum=0):

    # 현재 합이 target을 초과하면 더 이상 탐색하지 않음 (가지치기)
    if current_sum > target:
        return []    

    # 현재 합이 target과 같으면 결과 저장
    if current_sum == target:
        return [current[:]]    

    # 모든 숫자를 다 살펴봤으면 종료
    if index >= len(numbers):
        return []
        
    result = []    

    # 현재 숫자를 포함하는 경우
    current.append(numbers[index])
    result.extend(backtracking(numbers, target, index + 1, current, current_sum + numbers[index]))
    current.pop()    

    # 현재 숫자를 포함하지 않는 경우
    result.extend(backtracking(numbers, target, index + 1, current, current_sum))    

    return result

백트래킹은 좀 더 똑똑합니다. 이미 target을 넘어서면 더 이상 그 경로를 탐색하지 않습니다. "이 길은 답이 없겠다"고 판단하고 돌아가는 것이죠.

그리디로 푼다면

실은... 이 문제는 그리디로 풀기 어렵습니다! 그리디가 모든 문제에 작동하는 건 아니거든요. 예를 들어 [1, 2, 3, 4, 5]에서 합이 5인 부분집합을 찾을 때, 그리디로 큰 것부터 선택하면 [5]를 고르는데, 사실 [2, 3], [1, 4] 등도 답입니다. 그리디는 하나의 경로만 탐색하기 때문에 모든 답을 찾지 못합니다.

시간 복잡도로 비교하기

이제 성능 측면에서 비교해봅시다.

• 완전탐색: 일반적으로 O(2^n) 또는 O(n!)의 시간복잡도를 가집니다. 데이터가 조금만 많아져도 급격히 느려집니다.
• 백트래킹: 최악의 경우 O(2^n)이지만, 가지치기를 통해 실제로는 훨씬 빠릅니다. 불가능한 경로를 미리 제외하기 때문입니다.
• 그리디: 보통 O(n log n) 정도로 매우 빠릅니다. 하지만 그 문제가 정말로 그리디로 풀리는지 증명해야 합니다.

숫자로 보면

• n=20일 때: 완전탐색은 약 100만 번, 백트래킹은 경우에 따라 1천~10만 번, 그리디는 수백 번

실전: 언제 어떤 알고리즘을 쓸까?

이제 가장 중요한 부분입니다. 코딩테스트에서 문제를 마주했을 때, 어떻게 접근할까요?

완전탐색을 사용해야 할 때

1. 데이터 범위가 매우 작을 때 (보통 n ≤ 20)
2. 다른 최적화 방법이 없을 때
3. 모든 경우를 다 확인해야 할 때 (예: 모든 부분집합 찾기, 모든 순열 찾기)

예를 들어, "길이 15 이하의 배열에서 특정 조건을 만족하는 모든 부분집합 찾기"라는 문제가 있으면, 2^15 = 32,768개 정도만 확인하면 되므로 완전탐색이 적합합니다.

실제 코드 예시

def find_all_subsets_with_sum(arr, target):
    result = []
    n = len(arr)

    for mask in range(1 << n):
        subset = []
        subset_sum = 0
        
        for i in range(n):
            if mask & (1 << i):
                subset.append(arr[i])
                subset_sum += arr[i])        

        if subset_sum == target:
            result.append(subset)    

    return result

백트래킹을 사용해야 할 때

1. 데이터 범위가 중간 정도이고 (n ≤ 30~40)
2. 가지치기를 통해 탐색 공간을 줄일 수 있을 때
3. 현재 상태가 불가능하다는 걸 미리 알 수 있을 때

"N-Queen 문제", "스도쿠 풀기", "조합론 문제 중 일부" 등이 백트래킹의 전형적인 예입니다.

실제 코드 예시 - N-Queen

def solve_nqueens(n):
    result = []
    board = ['.' * n for _ in range(n)]

    def is_safe(row, col):
        # 같은 열 확인
        for i in range(row):
            if board[i][col] == 'Q':
                return False        

        # 왼쪽 위 대각선 확인
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j -= 1

        # 오른쪽 위 대각선 확인
        i, j = row - 1, col + 1
        while i >= 0 and j < n:
            if board[i][j] == 'Q':
                return False
            i -= 1
            j += 1        

        return True    

    def backtrack(row):
        if row == n:
            result.append(board[:])
            return        

        for col in range(n):
            if is_safe(row, col):
                board[row] = board[row][:col] + 'Q' + board[row][col+1:]
                backtrack(row + 1)
                board[row] = board[row][:col] + '.' + board[row][col+1:]    

    backtrack(0)

    return result

그리디를 사용해야 할 때

1. 최적 부분 구조(Optimal Substructure)가 성립할 때 - 전체 문제의 최적해가 부분 문제의 최적해로 이루어질 때
2. 탐욕 선택 속성(Greedy Choice Property)이 성립할 때 - 현 단계에서의 최적 선택이 전체 최적해를 만들 때
3. 데이터 범위가 크더라도 효율적일 때 (n ≤ 100,000 이상)

"동전 거스름돈", "활동 선택", "분수 배낭 문제" 등이 그리디의 대표적인 예입니다.

실제 코드 예시 - 동전 거스름돈

def coin_change(coins, amount):
    coins.sort(reverse=True)  # 큰 단위부터
    count = 0    

    for coin in coins:
        count += amount // coin
        amount %= coin    

    return count if amount == 0 else -1

코딩테스트에서의 전략

문제를 읽으면서 체크할 사항들

1단계: 데이터 범위 확인

• n ≤ 20 → 완전탐색/백트래킹 가능
• n ≤ 100,000 → 그리디나 동적프로그래밍 필요

2단계: 문제의 특성 파악

• "모든 경우를 다 찾아라" → 완전탐색
• "최적의 선택을 찾아라" → 그리디나 동적프로그래밍
• "조건을 만족하는 하나의 해를 찾아라" → 백트래킹

3단계: 가지치기 가능성 검토

• 현재 상태에서 불가능함을 미리 알 수 있는가?
• 그렇다면 백트래킹을 고려하세요.

실제 코딩테스트 문제 분석

예제 1: "크기가 N인 배열에서 K개를 뽑아 합이 최대인 경우를 찾아라" (N ≤ 100)

이 문제는 그리디입니다. 가장 큰 K개를 선택하면 되기 때문입니다.

예제 2: "문자열 S의 모든 부분 문자열을 찾아라" (|S| ≤ 1000)

이 문제는 완전탐색입니다. 모든 부분 문자열의 개수는 O(n^2)이므로, 범위 내에서 전부 생성할 수 있습니다.

예제 3: "체스판에 N개의 킹을 배치해서 서로 공격할 수 없게 하려면?" (N ≤ 8)

이 문제는 백트래킹입니다. 한 위치에 킹을 배치한 후, 그 킹이 공격할 수 있는 영역을 제외하고 계속 배치합니다.

실전 팁과 주의사항

복합적인 상황에서는?

가끔은 한 가지 알고리즘만으로 풀기 어려운 경우도 있습니다.
예를 들어, "0-1 배낭 문제"는 동적프로그래밍으로 풀지만, 각 상태 내에서 최적 선택을 할 때 그리디의 개념이 들어갑니다.
또한, "복잡한 제약 조건이 있는 배치 문제"는 백트래킹의 기본 틀에 동적프로그래밍의 메모이제이션을 더해야 할 때도 있습니다.

완전탐색으로 시작하되, 최적화할 준비하기

코딩테스트 중에 시간이 부족할 때는 완전탐색으로 먼저 정답을 맞춘 후, 시간이 남으면 최적화하는 것도 전략입니다.
실제로 백트래킹도 결국 "제약 조건을 통해 완전탐색을 최적화한 것"이니까요.

그리디의 함정 주의

그리디는 매우 유혹적입니다. 빠르고 간단하기 때문입니다. 하지만 그 문제가 정말로 그리디로 풀리는지 반드시 확인해야 합니다.
반례를 하나라도 찾을 수 있다면, 그리디는 틀렸다는 뜻입니다.

입사를 위한 코딩테스트는 단순히 알고리즘을 많이 아는 것이 아니라, 어느 상황에 어떤 알고리즘을 적용할지 판단하는 능력을 보는 것입니다.

완전탐색은 가장 직관적이지만 느리고, 백트래킹은 조금 더 똑똑하지만 구현이 복잡하고, 그리디는 빠르지만 증명이 필요합니다.

지금부터는 문제를 풀 때마다 "이 문제는 왜 완전탐색이 아니라 백트래킹을 써야 하지?", "이 문제는 정말 그리디가 최적해를 보장할까?"라고 자문해보세요.

그런 고민의 과정 속에서 알고리즘에 대한 이해가 깊어지고, 실제 코딩테스트에서도 빠르게 올바른 접근 방식을 찾을 수 있게 됩니다.

여러분도 충분히 할 수 있습니다. 이 세 가지 알고리즘의 차이를 명확히 한 후, 다양한 문제를 풀면서 경험을 쌓으면, 코딩테스트도 충분히 좋은 결과를 얻을 수 있을 거예요.

화이팅!

코딩테스트 입출력 처리와 파싱 노하우: 실전 팁과 주의사항