코딩 테스트나 실제 개발 현장에서 우리는 종종 복잡하고 어려운 문제와 마주하게 됩니다. 어디서부터 어떻게 접근해야 할지 막막한 문제들 앞에서, 뛰어난 개발자들은 자신만의 ‘문제 해결 도구함’을 가지고 있습니다. 이 도구함에는 수십 년간 수많은 컴퓨터 과학자들이 정립해 온 강력한 알고리즘 설계 기법들이 들어있습니다. 그중에서도 가장 핵심적인 네 가지 기법, 바로 ‘분할과 정복’, ‘동적 계획법’, ‘탐욕법’, 그리고 ‘백트래킹’은 모든 개발자가 반드시 이해하고 있어야 할 필살기와 같습니다.
이 네 가지 기법은 단순히 특정 알고리즘을 암기하는 것이 아니라, 문제를 바라보는 서로 다른 ‘관점’과 ‘전략’을 제공합니다. 어떤 문제는 거대한 적을 잘게 쪼개어 무찌르는 것이 효과적이고(분할과 정복), 어떤 문제는 작은 성공의 기록들을 차곡차곡 쌓아 큰 성공을 만들어내야 합니다(동적 계획법). 때로는 눈앞의 최선이 결국 최종적인 최선으로 이어지기도 하며(탐욕법), 때로는 막다른 길에 다다랐을 때 과감히 되돌아 나오는 용기가 필요합니다(백트래킹).
본 글에서는 이 네 가지 핵심 알고리즘 설계 기법이 각각 어떤 철학을 가지고 있으며, 어떤 종류의 문제를 해결하는 데 특화되어 있는지 그 원리와 대표적인 예시를 통해 깊이 있게 비교 분석해 보겠습니다. 이 네 가지 열쇠를 손에 쥔다면, 여러분은 어떤 복잡한 문제 앞에서도 당황하지 않고 최적의 해결책을 찾아 나설 수 있는 훌륭한 문제 해결사로 거듭날 것입니다.
분할과 정복 (Divide and Conquer)
핵심 개념: 큰 문제를 작게 쪼개어 해결한다
분할과 정복은 이름 그대로, 해결하기 어려운 하나의 거대한 문제를 동일한 유형의 더 작은 여러 개의 하위 문제(Subproblem)로 ‘분할(Divide)’하고, 이렇게 작아진 하위 문제들을 재귀적으로 해결(‘정복, Conquer’)한 뒤, 그 결과들을 다시 ‘결합(Combine)’하여 원래 문제의 답을 구하는 방식입니다. 이는 마치 거대한 적군을 한 번에 상대하기 어려울 때, 여러 개의 소부대로 나누어 각개 격파한 후 다시 합류하는 전략과 같습니다.
분할과 정복 기법이 성공적으로 적용되기 위해서는 두 가지 전제 조건이 필요합니다. 첫째, 원래 문제를 더 작은 크기의 동일한 유형의 문제로 나눌 수 있어야 합니다. 둘째, 하위 문제들의 해결책을 합쳐서 원래 문제의 해결책을 효율적으로 만들어낼 수 있어야 합니다. 이 기법은 주로 재귀(Recursion) 함수를 통해 매우 자연스럽게 구현됩니다.
분할과 정복의 3단계 프로세스:
- 분할 (Divide): 원래 문제를 더 이상 나눌 수 없을 때까지 비슷한 유형의 작은 하위 문제들로 나눕니다.
- 정복 (Conquer): 하위 문제들이 충분히 작아져서 직접 해결할 수 있게 되면, 그 문제들을 해결합니다.
- 결합 (Combine): 해결된 하위 문제들의 답을 합병하여 원래의 큰 문제의 답을 구합니다.
이 기법의 가장 대표적인 예는 바로 ‘병합 정렬(Merge Sort)’과 ‘퀵 정렬(Quick Sort)’입니다.
적용 사례: 병합 정렬 (Merge Sort)
병합 정렬은 정렬되지 않은 하나의 거대한 배열을 더 이상 쪼갤 수 없을 때까지(원소가 1개가 될 때까지) 계속해서 반으로 나누고, 이렇게 나눠진 작은 배열들을 다시 정렬된 상태로 병합해 나가면서 전체 배열을 정렬하는 알고리즘입니다.
[8, 3, 5, 1, 6, 2, 7, 4] 라는 배열을 병합 정렬로 정렬하는 과정은 다음과 같습니다.
- 분할 (Divide):
- [8, 3, 5, 1] | [6, 2, 7, 4]
- [8, 3] | [5, 1] | [6, 2] | [7, 4]
- [8] | [3] | [5] | [1] | [6] | [2] | [7] | [4] (더 이상 나눌 수 없음)
- 정복 (Conquer): 원소가 하나인 배열은 이미 정렬된 상태이므로, 정복 단계는 사실상 완료되었습니다.
- 결합 (Combine):
- [8], [3] → [3, 8]
- [5], [1] → [1, 5]
- [6], [2] → [2, 6]
- [7], [4] → [4, 7]
- [3, 8], [1, 5] → [1, 3, 5, 8]
- [2, 6], [4, 7] → [2, 4, 6, 7]
- [1, 3, 5, 8], [2, 4, 6, 7] → [1, 2, 3, 4, 5, 6, 7, 8] (최종 결과)
이처럼 병합 정렬은 ‘나누는’ 행위와 ‘합치는’ 행위를 통해 복잡한 정렬 문제를 매우 안정적이고 효율적으로 해결합니다. 분할과 정복은 이처럼 문제가 명확하게 작은 단위로 나뉠 수 있고, 나중에 합치는 과정이 복잡하지 않을 때 매우 강력한 힘을 발휘합니다.
동적 계획법 (Dynamic Programming, DP)
핵심 개념: 한 번 푼 문제는 다시 풀지 않는다
동적 계획법은 분할과 정복과 마찬가지로 큰 문제를 작은 하위 문제들로 나누어 푼다는 점에서 유사합니다. 하지만 결정적인 차이가 있습니다. 분할과 정복에서 마주하는 하위 문제들은 서로 ‘독립적’인 반면, 동적 계획법이 해결하려는 문제의 하위 문제들은 서로 ‘중복’되는 경우가 많습니다. 즉, 동일한 하위 문제가 여러 번 반복해서 나타납니다.
동적 계획법은 이처럼 중복되는 하위 문제의 답을 매번 새로 계산하는 비효율을 막기 위해, 한 번 계산한 하위 문제의 답을 ‘메모이제이션(Memoization)’이라는 기법을 통해 특정 공간(보통 배열이나 해시 테이블)에 저장해 둡니다. 그리고 나중에 동일한 하위 문제를 다시 마주하게 되면, 새로 계산하지 않고 저장된 값을 즉시 가져다 사용하는 방식입니다. 이는 “과거의 경험을 기록하고 재활용하여 현재의 문제를 더 효율적으로 해결한다”는 철학을 담고 있습니다.
동적 계획법의 2가지 핵심 조건:
- 중복되는 하위 문제 (Overlapping Subproblems): 큰 문제를 작은 하위 문제로 나누었을 때, 동일한 하위 문제가 반복적으로 나타나야 합니다.
- 최적 부분 구조 (Optimal Substructure): 큰 문제의 최적의 해결책이 그 하위 문제들의 최적의 해결책들로 구성될 수 있어야 합니다.
이 기법의 가장 고전적인 예는 ‘피보나치 수열’ 계산과 ‘배낭 문제(Knapsack Problem)’입니다.
적용 사례: 피보나치 수열 계산
피보나치 수열은 F(n) = F(n-1) + F(n-2) 로 정의됩니다. 이를 재귀 함수로 단순하게 구현하면 다음과 같습니다.
Python
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
fibonacci(5)를 호출하면, 이 함수는 fibonacci(4)와 fibonacci(3)을 호출합니다. fibonacci(4)는 다시 fibonacci(3)과 fibonacci(2)를 호출합니다. 여기서 fibonacci(3)이 중복해서 호출되는 것을 볼 수 있습니다. n이 커질수록 이런 중복 호출은 기하급수적으로 늘어나 엄청난 비효율을 초래합니다.
동적 계획법(메모이제이션 사용)을 적용하면 다음과 같이 개선할 수 있습니다.
Python
memo = {} # 계산 결과를 저장할 딕셔너리 (캐시)
def fibonacci_dp(n):
if n in memo: # 이미 계산한 적이 있다면
return memo[n] # 저장된 값을 바로 반환
if n <= 1:
return n
result = fibonacci_dp(n-1) + fibonacci_dp(n-2)
memo[n] = result # 계산 결과를 저장
return result
이제 fibonacci_dp(3)이 한 번 계산되면 그 결과는 memo에 저장됩니다. 나중에 다른 경로에서 fibonacci_dp(3)이 다시 호출되더라도, 복잡한 재귀 호출 없이 memo에서 즉시 값을 가져오므로 계산 속도가 비약적으로 향상됩니다. 이처럼 동적 계획법은 중복 계산을 제거하여 시간 복잡도를 극적으로 줄이는 데 특화된 기법입니다.
탐욕법 (Greedy Algorithm)
핵심 개념: 매 순간의 최선이 결국 최고의 결과로 이어진다
탐욕법은 미래를 내다보지 않고, 매 단계마다 ‘지금 당장’ 가장 좋아 보이는 선택을 하는 방식으로 문제의 최적해를 찾아가는 기법입니다. 이는 마치 등산할 때 전체 지도를 보지 않고, 눈앞에 보이는 가장 가파른 오르막길로만 계속 올라가는 것과 같습니다. 이러한 ‘지역적 최적해(Locally Optimal Solution)’를 계속해서 선택해 나가다 보면, 결국 전체 문제의 ‘전역적 최적해(Globally Optimal Solution)’에 도달할 것이라는 희망적인 가정에 기반합니다.
탐욕법이 항상 올바른 답을 보장하는 것은 아닙니다. 눈앞의 이익에만 급급한 선택이 나중에는 더 큰 손해로 이어질 수도 있기 때문입니다. 따라서 탐욕법은 ‘탐욕적인 선택이 항상 최적해를 보장한다’는 정당성이 증명된 특정 문제 유형에만 적용할 수 있습니다.
탐욕법이 성공하기 위한 2가지 조건:
- 탐욕적 선택 속성 (Greedy Choice Property): 매 단계에서 하는 지역적으로 최적인 선택이, 나중에 고려해야 할 하위 문제들의 선택에 영향을 주지 않아야 합니다. 즉, 지금의 선택이 미래의 선택을 제한해서는 안 됩니다.
- 최적 부분 구조 (Optimal Substructure): 한 단계에서 탐욕적인 선택을 한 후 남은 하위 문제가, 원래 문제와 동일한 방식으로 최적해를 구할 수 있는 구조여야 합니다.
탐욕법의 대표적인 예로는 ‘거스름돈 문제’와 ‘최소 신장 트리(MST)’를 찾는 크루스칼(Kruskal) 알고리즘, ‘최단 경로’를 찾는 다익스트라(Dijkstra) 알고리즘이 있습니다.
적용 사례: 거스름돈 문제
손님에게 870원을 거슬러 줘야 하고, 우리에게는 500원, 100원, 50원, 10원짜리 동전이 충분히 있다고 가정해 봅시다. 이때 ‘최소 개수’의 동전으로 거슬러 주는 것이 목표입니다.
탐욕법적인 접근은 매우 간단합니다. “매 순간, 줄 수 있는 가장 큰 단위의 동전부터 준다.”
- 남은 돈: 870원. 가장 큰 단위는 500원. 500원 1개를 준다. (남은 돈: 370원)
- 남은 돈: 370원. 가장 큰 단위는 100원. 100원 3개를 준다. (남은 돈: 70원)
- 남은 돈: 70원. 가장 큰 단위는 50원. 50원 1개를 준다. (남은 돈: 20원)
- 남은 돈: 20원. 가장 큰 단위는 10원. 10원 2개를 준다. (남은 돈: 0원)
- 최종 결과: 500원(1), 100원(3), 50원(1), 10원(2) = 총 7개의 동전. 이것이 최적해입니다.
우리나라의 화폐 단위처럼 큰 단위가 작은 단위의 배수로 이루어진 경우에는 탐욕법이 항상 최적해를 보장합니다. 하지만 만약 화폐 단위가 500원, 400원, 100원이라면 어떨까요? 800원을 거슬러 줄 때, 탐욕법은 500원 1개, 100원 3개를 주어 총 4개의 동전을 사용하지만, 최적해는 400원 2개를 사용하는 2개입니다. 이처럼 탐욕법은 문제의 구조에 따라 적용 가능 여부가 결정되는, 신중하게 사용해야 하는 기법입니다.
백트래킹 (Backtracking)
핵심 개념: 막다른 길에 다다르면 되돌아 나온다
백트래킹은 가능한 모든 경우의 수를 탐색하는 ‘상태 공간 트리(State Space Tree)’를 만들면서 해를 찾아가는 기법입니다. 하지만 모든 경로를 무식하게 다 탐색하는 완전 탐색(Brute-force)과는 달리, 특정 경로로 탐색을 진행하다가 그 경로가 더 이상 해가 될 가능성이 없다고 판단되면, 과감하게 그 길을 포기하고 이전 단계로 되돌아와(Backtrack) 다른 가능한 경로를 탐색하는 방식입니다. 이는 마치 미로를 찾을 때, 한 길로 가다가 막다른 길을 만나면 왔던 길을 되돌아가 다른 갈림길부터 다시 탐색을 시작하는 것과 같습니다.
백트래킹은 ‘가지치기(Pruning)’라는 개념을 통해 불필요한 탐색을 줄여 효율을 높입니다. 어떤 노드로 이동했을 때, 그 노드에서부터는 더 이상 해를 찾을 수 없다는 것이 명백하다면(유망하지 않다면), 그 노드를 포함한 모든 하위 경로는 더 이상 탐색하지 않고 건너뜁니다.
백트래킹의 기본 절차:
- 현재 상태에서 다음으로 이동할 수 있는 모든 후보 경로를 찾는다.
- 각 후보 경로에 대해, 해가 될 가능성이 있는지(유망한지)를 검사한다.
- 만약 유망하다면, 그 경로로 이동(재귀 호출)한다.
- 만약 유망하지 않다면, 그 경로는 버리고 다음 후보 경로를 탐색한다.
- 모든 경로를 탐색했는데 해를 찾지 못했다면, 이전 단계로 되돌아간다.
백트래킹은 주로 조합 최적화 문제나 제약 만족 문제, 예를 들어 ‘N-Queens 문제’, ‘스도쿠 풀이’, ‘미로 찾기’ 등 모든 가능한 해를 탐색해야 하는 문제에 효과적으로 사용됩니다.
적용 사례: N-Queens 문제
N-Queens 문제는 N x N 크기의 체스판에 N개의 퀸을 서로 공격할 수 없도록 배치하는 모든 경우의 수를 찾는 고전적인 백트래킹 문제입니다. (퀸은 가로, 세로, 대각선 방향으로 제약 없이 움직일 수 있습니다.)
4-Queens 문제를 푼다고 가정해 봅시다.
- 1행: 첫 번째 퀸을 (1,1)에 놓습니다.
- 2행: 두 번째 퀸을 놓을 자리를 찾습니다. (2,1), (2,2)는 첫 번째 퀸의 공격 경로이므로 불가능합니다. (2,3)에 퀸을 놓습니다.
- 3행: 세 번째 퀸을 놓을 자리를 찾습니다. (3,1), (3,2), (3,3), (3,4) 모두 이전 퀸들의 공격 경로에 해당하여 놓을 수 없습니다. -> 막다른 길!
- 백트랙 (Backtrack): 3행에서 해가 없으므로, 이전 단계인 2행으로 되돌아갑니다. 2행에서 (2,3) 다음으로 가능한 위치는 (2,4)입니다. 두 번째 퀸을 (2,4)로 이동시킵니다.
- 3행 (재탐색): 이제 다시 세 번째 퀸을 놓을 자리를 찾습니다. (3,2)에 놓을 수 있습니다.
- 4행: 네 번째 퀸을 놓을 자리를 찾습니다. 모든 칸이 공격 경로에 해당하여 놓을 수 없습니다. -> 막다른 길!
- 백트랙 (Backtrack): 다시 3행으로, 그리고 2행으로, 최종적으로 1행까지 되돌아옵니다. 첫 번째 퀸의 위치가 (1,1)인 경우에는 해가 없다는 결론에 도달합니다.
- 이제 첫 번째 퀸을 (1,2)에 놓고 위 과정을 다시 반복합니다.
이처럼 백트래킹은 유망하지 않은 경로를 조기에 차단하고 되돌아 나오는 체계적인 탐색을 통해, 무식한 완전 탐색보다 훨씬 효율적으로 해를 찾아냅니다.
마무리: 어떤 문제에 어떤 열쇠를 사용할 것인가?
| 기법 | 핵심 아이디어 | 문제 유형 | 장점 | 단점 |
| 분할과 정복 | 큰 문제를 작은 문제로 쪼개서 해결 | 정렬, 행렬 곱셈 등 하위 문제가 독립적인 경우 | 효율적, 병렬 처리 용이 | 재귀 구조로 인한 오버헤드 |
| 동적 계획법 | 중복되는 하위 문제의 답을 기록하고 재활용 | 최단 경로, 배낭 문제 등 하위 문제가 중복되는 경우 | 매우 효율적 (중복 계산 제거) | 메모리 공간 필요, 점화식 도출 어려움 |
| 탐욕법 | 매 순간의 최선이 최종적인 최선이라 가정 | 거스름돈, 최소 신장 트리 등 탐욕적 선택이 보장되는 경우 | 매우 빠르고 구현이 간단 | 항상 최적해를 보장하지 않음 |
| 백트래킹 | 해가 될 가능성이 없는 경로는 포기하고 되돌아옴 | N-Queens, 스도쿠 등 모든 해를 탐색해야 하는 경우 | 불필요한 탐색을 줄여 효율적 | 최악의 경우 여전히 지수 시간 복잡도 |
알고리즘 설계 기법은 단순히 외워야 할 공식이 아니라, 문제의 본질을 꿰뚫어 보고 가장 효율적인 해결 경로를 설계하기 위한 사고의 틀입니다.
- 문제가 명확하게 독립적인 하위 문제들로 나뉜다면 분할과 정복을,
- 하위 문제들이 서로 얽혀 중복 계산이 많이 발생한다면 동적 계획법을,
- 매 순간의 최선의 선택이 최종 결과에 영향을 주지 않는 구조라면 탐욕법을,
- 그리고 가능한 모든 조합을 탐색하되 영리하게 불필요한 경로를 잘라내고 싶다면 백트래킹을 떠올려야 합니다.
이 네 가지 핵심 열쇠를 자유자재로 다룰 수 있게 될 때, 여러분은 어떤 복잡한 문제 앞에서도 자신감을 갖고 최적의 해결책을 설계할 수 있는 진정한 문제 해결 전문가로 성장할 수 있을 것입니다.