Algorithm Design Strategies (알고리즘 설계 전략)

"알고리즘을 설계할 때 완전 탐색, 백트래킹, 분할 정복, 동적 계획법(DP), 그리디를 어떤 조건으로 고르고, 서로 어떻게 이어지는가?" 이 페이지는 그 질문에 답한다. 원문 hub 노트는 백트래킹·완전 탐색·분할 정복을 탐색 기법으로, DP를 최적화로 분류한다.^[1] 원문 노트들은 서로를 비교한다. 백트래킹 노트는 완전 탐색과 비교하고 자신을 DFS의 최적화 형태로 보며, DP 노트는 그리디와 비교한다.^[2][3][4] 이 페이지는 다섯 전략을 그 비교 관계를 따라 차례로 놓고, 마지막에 고르는 기준을 한 표로 모은다.

완전 탐색 (Exhaustive Search)

• 완전 탐색은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해 보고 확인하는 기법이다. Brute-force 또는 generate-and-test 기법이라고도 부르며, 원문 노트의 제목은 "완전검색"이다.^[5]
• 여기서 force는 사람의 힘이 아니라 컴퓨터의 힘을 뜻한다.^[5:1]
• 완전 탐색은 모든 경우의 수를 시험한 뒤 최종 해법을 도출한다. 알고리즘 설계는 비교적 빨리 끝낼 수 있지만, 모든 경우를 생성하고 시험하므로 실행 속도는 느리다. 대신 해답을 찾아내지 못할 확률이 작다.^[6]
• 즉, 원문은 "설계에 드는 시간"과 "실행에 드는 시간"을 따로 평가한다. 완전 탐색은 앞의 것이 짧고 뒤의 것이 길다.^[6:1]
• 완전 탐색은 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.^[6:2]
• 먼저 완전 탐색으로 답을 구한 뒤, 성능을 높이려고 다른 알고리즘을 쓰고 해답을 확인하는 것이 바람직하다.^[7] 두 답을 서로 대조하는 방식으로 읽는 것은 이 Wiki의 판독이다.
• 경우의 수가 "작은지"는 Implementation Problem Approach의 입력 크기별 허용 복잡도 표로 가늠할 수 있다고 볼 수 있다.^[8] 이 연결은 이 Wiki의 해석이다.

백트래킹 (Backtracking)

• 백트래킹은 해를 찾으려고 상태 공간 트리를 탐색하다가, 현재 경로가 해가 될 수 없다고 판단되면 이전 단계로 되돌아가 다른 경로를 탐색하는 기법이다. 원문은 이를 깊이 우선 탐색(DFS)의 최적화 형태로 본다.^[3:1] DFS 자체는 Graph Algorithms가 다룬다.

• 위 표는 원문의 비교표를 옮긴 것이다.^[2:1]
• 백트래킹도 탐색의 모든 경우를 확인 대상으로 삼지만, 유망성을 검증해 불필요한 탐색을 차단해야 한다.^[9]
• 현재 상태에서 해를 찾을 가능성이 있으면 유망(promising)하다. 제약 조건을 이미 어겼거나 최적해가 될 수 없으면 비유망(non-promising)이며, 즉시 return한다.^[9:1]
• 가지치기(pruning)는 재귀 호출 때 조건문으로 현재 상태가 제약 조건을 어기는지 검사하고, 어기면 그 아래 하위 트리 전체를 탐색하지 않고 즉시 return하는 것이다.^[10]

루트
├─ 선택 1
│   ├─ 선택 1-1  ← [유망] 계속 탐색
│   │   └─ 선택 1-1-1  ← [해 발견]
│   └─ 선택 1-2  ← [비유망] 가지치기(Prune) → return
└─ 선택 2
    ├─ 선택 2-1  ← [비유망] 가지치기 → return
    └─ 선택 2-2  ← [유망] 계속 탐색

• 구현 틀은 종료 조건 확인 → 가지치기 → 선택 → 재귀 탐색 → 선택 취소(복원) 순서다.^[11]

boolean[] visited = new boolean[N + 1];

void backtrack(int depth, ...) {
    // 종료 조건 (해를 찾은 경우)
    if (depth == N) {
        // 결과 처리
        return;
    }

    for (int i = 1; i <= N; i++) {
        // 가지치기: 이미 방문했거나 제약 조건 위반
        if (visited[i] || !isValid(i)) continue;

        // 선택
        visited[i] = true;

        // 재귀 탐색
        backtrack(depth + 1, ...);

        // 선택 취소 (복원)
        visited[i] = false;
    }
}

• 대표 유형은 다음 세 가지다.^[12]
  • 순열 생성: N개 원소 가운데 R개를 순서 있게 고르며, visited 배열로 중복 선택을 막는다.
  • 부분집합 합(Subset Sum): 지금까지의 합이 목표값을 넘으면 가지치기한다(if (currentSum > target) return;).
  • N-Queen: 체스판에 N개의 퀸을 서로 공격할 수 없게 놓으며, 열과 대각선 충돌 여부를 가지치기 조건으로 쓴다.
• 시간 복잡도는 가지치기 효율에 따라 크게 달라진다. 최악의 경우 완전 탐색과 같지만, 실전에서는 탐색 공간을 크게 줄인다.^[13]

분할 정복 (Divide and Conquer)

• 분할 정복은 세 단계로 설계한다.^[14]
  • 분할(Divide): 해결할 문제를 여러 개의 작은 부분으로 나눈다.
  • 정복(Conquer): 나눈 작은 문제를 각각 해결한다.
  • 통합(Combine): 필요하다면 해결된 해답을 모은다.
• 2분할 top-down 접근에서는 크기 n인 문제를 크기 n/2인 부분 문제 두 개로 나누고, 각 부분 문제의 해를 결합해 전체 문제의 해를 만든다.^[15]

flowchart TD
    P["문제 (크기 n)"] -->|분할| S1["부분 문제 1 (크기 n/2)"]
    P -->|분할| S2["부분 문제 2 (크기 n/2)"]
    S1 -->|정복| A1["부분 문제 1의 해"]
    S2 -->|정복| A2["부분 문제 2의 해"]
    A1 -->|결합| R["전체 문제의 해"]
    A2 -->|결합| R

• 위 도식은 원문에 붙은 그림을 다시 그린 것이다. 그림은 세 번째 단계를 "결합"이라 부르고, 본문은 "통합(Combine)"이라 부르지만 같은 단계다.^[15:1]
• x의 n제곱을 반복으로 구하면 x를 n번 곱하므로 O(N)이다.^[16]

Iterative_Power(x, n)
	result <- 1
	
	FOR i in 1 -> n
		result <- result * x
	
	RETURN result

• 분할 정복으로 구하면 n이 짝수일 때 x^(n/2)를 한 번 구해 제곱하고, 홀수일 때 x^((n-1)/2)를 한 번 구해 제곱한 뒤 x를 곱한다. 원문은 이 방식을 O(log N)으로 적는다.^[17]

Recursive_Power(x, n)
	IF n  == 1 : RETURN x
	IF n is even
		y <- Recursive_Power(x, n/2);
		RETURN y*y
	ELSE
		y <- Recursive_Power(x, (n-1)/2)
		RETURN y*y*x

• 원문은 두 의사코드 블록에 pascal 표시를 붙였지만 Pascal 코드가 아니어서, 이 페이지에서는 text로 바꿔 옮겼다.^[17:1]
• 재귀 버전의 종료 조건은 n == 1뿐이라 n ≥ 1을 전제로 한다. n = 0이 들어오면 종료하지 않는다고 볼 수 있다. 이 판독은 이 Wiki의 해석이다.
• O(log N)이 되는 이유는 호출마다 n이 절반으로 줄고, 같은 부분 문제 x^(n/2)를 두 번 풀지 않고 y에 한 번 받아 제곱하기 때문이라고 볼 수 있다. Recursive_Power를 두 번 호출해 곱하면 이 이점이 사라진다. 이 분석은 이 Wiki의 해석이다.

동적 계획법 (Dynamic Programming)

• 동적 계획법은 복잡한 큰 문제를 작은 하위 문제로 나눠 풀고, 그 결과를 저장(메모이제이션)해 다시 써서 중복 연산을 막는 기법이다.^[18]
• DP는 두 조건이 함께 충족될 때 쓸 수 있다.^[19]
  • 중복되는 하위 문제(Overlapping Subproblems): 같은 작은 문제가 반복해서 나타난다. 예를 들어 피보나치에서는 fib(3)이 여러 번 호출된다.
  • 최적 부분 구조(Optimal Substructure): 부분 문제의 최적해를 조합해 전체 문제의 최적해를 만들 수 있다. 예를 들어 최단 경로의 부분 경로도 최단 경로다.
• 구현 방식은 두 가지다. Memoization(top-down)은 재귀와 결과 캐싱으로 필요한 부분 문제만 계산하고, Tabulation(bottom-up)은 반복문으로 표를 채우며 작은 문제부터 순서대로 계산한다.^[20]

int[] memo = new int[N + 1];
Arrays.fill(memo, -1);

int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // 캐시 히트
    return memo[n] = fib(n - 1) + fib(n - 2);
}

int[] dp = new int[N + 1];
dp[0] = 0; dp[1] = 1;
for (int i = 2; i <= N; i++)
    dp[i] = dp[i - 1] + dp[i - 2]; // 점화식

• 위 표는 원문 비교표를 옮긴 것이며, "실전 선호" 행은 원문 노트의 의견이다.^[20:1]
• 점화식은 세 단계로 설계한다.^[21]
  1. 상태 정의: dp[i] 또는 dp[i][j]가 무엇을 뜻하는지 정한다.
  2. 점화식 도출: 이전 상태로부터 현재 상태를 유도하는 관계식을 쓴다.
  3. 초기값 설정: base case(재귀의 종료 조건)를 정한다.
• 원문은 1차원 DP의 예로 계단 오르기를, 2차원 DP의 예로 배낭 문제를 든다.^[22]

// 예: 계단 오르기 (dp[i] = i번째 계단까지의 최대 점수)
dp[i] = Math.max(dp[i-1] + stair[i], dp[i-2] + stair[i]);

// 예: 배낭 문제 (dp[i][w] = i번째 물건까지 무게 w 이하일 때 최대 가치)
if (weight[i] <= w)
    dp[i][w] = Math.max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]);
else
    dp[i][w] = dp[i-1][w];

• 원문은 계단 오르기의 문제 조건(한 번에 오를 수 있는 칸 수, 연속으로 밟는 제한 여부)을 적지 않는다. 위 식은 한 번에 1칸이나 2칸을 오르고 다른 제한이 없는 경우의 식으로 읽힌다. 이 판독은 이 Wiki의 해석이다.
• 배낭 식은 dp[i-1] 행만 참조하므로, 물건마다 한 번만 고를 수 있는 형태로 읽힌다. 이 판독도 이 Wiki의 해석이다.

그리디와 DP

• 위 표는 원문 비교표를 옮긴 것이다.^[4:1]
• 그리디와 DP는 둘 다 최적 부분 구조를 요구하지만, 그리디는 탐욕 선택 속성을, DP는 중복 부분 문제를 추가로 요구한다.^[4:2]
• 원문은 그리디로 해결할 수 있으면 그리디를 먼저 쓰고, 확실하지 않으면 DP를 쓰라고 권한다.^[4:3]
• 원문은 그리디만 따로 다룬 노트를 두지 않는다. 그래서 탐욕 선택 속성의 정의나 그리디의 정당성 증명은 이 페이지에 없다.

고르는 기준과 혼동 지점

• 칸마다 원문 근거가 있지만, 다섯 전략을 한 표에 놓고 "이런 조건이면 고른다"로 읽는 조합은 이 Wiki가 만든 것이다.
• DP와 분할 정복은 둘 다 문제를 작은 문제로 나눈다.^[18:1][14:2] 원문에서 중복 부분 문제를 적용 조건으로 드는 쪽은 DP 노트뿐이므로, 이 점을 두 전략을 가르는 기준으로 볼 수 있다.^[19:2] 다만 분할정복 노트는 부분 문제가 서로 겹치지 않는다고 직접 말하지 않고, DP 노트도 분할정복을 관련 노트로 링크만 할 뿐 차이를 설명하지 않는다. 이 구분은 이 Wiki의 해석이다.
• 최단 경로 알고리즘도 이 구분에 놓인다. Dijkstra는 그리디로, Bellman-Ford와 Floyd-Warshall은 DP로 분류된다.^[23] 각 알고리즘이 왜 그 조건에서만 맞는지는 Shortest Path Algorithms가 다룬다.

관련

• Graph Algorithms: 백트래킹의 바탕인 DFS의 재귀·스택 구현을 다룬다.
• Shortest Path Algorithms: 그리디(Dijkstra)와 DP(Bellman-Ford, Floyd-Warshall)가 실제 문제에서 어떤 조건 차이로 갈리는지 보여 준다.
• Implementation Problem Approach: 입력 크기로 허용 시간 복잡도를 가늠해, 완전 탐색으로 충분한지 판단하는 데 쓴다.

테스트 질문

• 백트래킹은 완전 탐색과 무엇이 다르며, 최악의 경우 시간 복잡도는 어떻게 되는가?
• DP를 쓰려면 문제가 어떤 두 조건을 갖춰야 하고, 그리디의 적용 조건과는 무엇이 다른가?
• 분할 정복 거듭제곱이 반복 곱셈의 O(N)보다 빠른 O(log N)이 되는 이유는 무엇인가?

출처