7-6. 그리디: 분할 정복 (Divide and Conquer)

1. 분할 정복 (Divide and Conquer) 개요

분할 정복(Divide and Conquer)은 문제를 더 작은 하위 문제(subproblems)로 나누어 해결하고, 하위 문제의 해결책을 결합하여 원래 문제의 해답을 도출하는 알고리즘 설계 패러다임입니다. 이는 복잡한 문제를 효율적으로 해결하는 강력한 방법이며, 다양한 알고리즘의 기반이 됩니다. 분할 정복은 다음 세 단계로 이루어집니다.

1. 분할(Divide): 주어진 문제를 동일하거나 유사한 여러 개의 하위 문제로 나눕니다.
2. 정복(Conquer): 하위 문제가 충분히 작으면, 직접 해결합니다. 그렇지 않다면, 재귀적으로 분할 정복 기법을 적용하여 해결합니다.
3. 결합(Combine): 하위 문제의 해결책을 결합하여 원래 문제의 해답을 구합니다.

분할 정복은 문제의 크기를 지속적으로 줄여나가기 때문에, 일반적으로 시간 복잡도를 개선하는 효과를 가져옵니다.

2. 분할 정복의 핵심 원리

분할 정복의 핵심은 문제를 작은 부분으로 나누어 해결하는 것입니다. 이 과정은 재귀적으로 이루어지며, 각 하위 문제는 원래 문제와 동일한 방식으로 해결됩니다.

1) 재귀적 구조

분할 정복 알고리즘은 재귀적인 구조를 가집니다. 즉, 알고리즘 자체가 자신을 호출하여 더 작은 문제를 해결합니다. 이는 문제를 분해하고, 분해된 문제에 다시 분할 정복을 적용하는 과정을 반복하기 때문입니다. 재귀 호출의 종료 조건은 하위 문제가 더 이상 분할할 수 없을 정도로 작아졌을 때입니다.

2) 효율성

분할 정복의 효율성은 문제의 크기를 줄이는 방식에 기인합니다. 문제를 작은 크기로 나누면, 개별 하위 문제를 해결하는 데 필요한 시간이 줄어듭니다. 또한, 하위 문제의 해결책을 결합하는 과정이 효율적으로 이루어진다면, 전체 알고리즘의 시간 복잡도를 줄일 수 있습니다.

3) 문제 유형

분할 정복 기법은 정렬, 검색, 행렬 연산 등 다양한 문제 해결에 사용됩니다. 특히, 다음과 같은 특징을 가진 문제에 적합합니다.

• 문제를 더 작은 동일한 형태로 분할할 수 있는 경우
• 하위 문제의 해결책을 결합하여 전체 문제의 해결책을 쉽게 구할 수 있는 경우

3. 분할 정복과 그리디 알고리즘의 결합: 예시

그리디 알고리즘은 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결합니다. 분할 정복은 문제를 나누어 해결하는 전략을 제공합니다. 이 두 가지를 결합하면, 특정 문제에 대해 효율적이고 효과적인 해결책을 도출할 수 있습니다.

1) 문제 정의: 최댓값 찾기

배열 arr에서 최댓값을 찾는 문제를 생각해 보겠습니다.

2) 그리디 접근 방식

그리디 알고리즘은 배열을 순회하면서 현재까지의 최댓값을 갱신합니다. 이 방법은 간단하지만, 분할 정복의 관점에서 최적의 해결책을 찾기 어려울 수 있습니다.

3) 분할 정복 접근 방식

분할 정복을 사용하여 배열에서 최댓값을 찾는 방법을 생각해 봅시다.

1. 분할: 배열을 두 개의 하위 배열로 나눕니다.
2. 정복: 각 하위 배열에서 재귀적으로 최댓값을 찾습니다. 하위 배열이 하나의 요소만 남으면, 해당 요소가 최댓값입니다.
3. 결합: 두 하위 배열의 최댓값 중 더 큰 값을 선택합니다.

다음은 파이썬 코드로 구현한 예시입니다.

def find_max_recursive(arr, left, right):
    # base case: single element
    if left == right:
        return arr[left]

    mid = (left + right) // 2

    # divide and conquer
    left_max = find_max_recursive(arr, left, mid)
    right_max = find_max_recursive(arr, mid + 1, right)

    # combine
    return max(left_max, right_max)

# 예시 사용
arr = [3, 7, 2, 9, 4, 1]
max_value = find_max_recursive(arr, 0, len(arr) - 1)
print(f"최댓값: {max_value}")  # 출력: 9

이 코드는 배열을 반으로 나누어 재귀적으로 최댓값을 찾습니다. 각 단계에서 두 하위 배열의 최댓값을 비교하여 최종 최댓값을 결정합니다.

4) 시간 복잡도 분석

이 알고리즘의 시간 복잡도는 $O(n)$입니다. 배열을 반으로 나누는 데 $O(1)$ 시간이 소요되고, 각 하위 배열에 대한 재귀 호출이 이루어지며, 각 하위 배열의 최댓값을 비교하는 데 $O(1)$ 시간이 소요됩니다. 재귀 호출의 깊이는 $log_2{n}$이므로, 전체 시간 복잡도는 $O(n)$이 됩니다.

4. 분할 정복과 그리디의 활용: 최적화 문제

분할 정복과 그리디 알고리즘은 최적화 문제에서 효과적인 해결 전략을 제공할 수 있습니다. 특히, 다음과 같은 경우에 유용합니다.

• 문제를 여러 개의 하위 문제로 나눌 수 있고, 각 하위 문제는 원래 문제와 동일한 구조를 가짐
• 각 하위 문제의 최적 해를 결합하여 전체 문제의 최적 해를 구할 수 있음
• 각 단계에서 그리디 선택(local optimum)이 전체 문제의 최적 해(global optimum)로 이어진다는 것을 보장할 수 있음

1) 예시: 활동 선택 문제 (Activity Selection Problem)

활동 선택 문제는 여러 개의 활동(activity) 중에서 서로 겹치지 않으면서 가장 많은 활동을 선택하는 문제입니다. 각 활동은 시작 시간과 종료 시간을 가집니다.

1. 그리디 선택: 종료 시간이 가장 빠른 활동을 먼저 선택합니다.
2. 분할: 선택된 활동 이후의 활동들을 하위 문제로 생각합니다.
3. 정복: 하위 문제에 대해 재귀적으로 그리디 선택을 적용합니다.
4. 결합: 선택된 활동들과 하위 문제의 해결책을 결합합니다.

2) 예시: 배낭 문제 (Knapsack Problem)

0/1 배낭 문제는 주어진 무게 제한 내에서 가장 가치 있는 품목들을 선택하여 배낭에 넣는 문제입니다.

• 그리디 선택: 품목의 가치/무게 비율이 가장 높은 품목을 먼저 선택합니다. (0/1 배낭 문제에서는 그리디 알고리즘이 최적의 해를 보장하지 않습니다. 분할 정복과 다른 알고리즘을 사용해야 합니다.)
• 분할: 품목을 선택하거나 선택하지 않는 두 가지 경우로 나눕니다.
• 정복: 각 경우에 대해 재귀적으로 배낭 문제를 해결합니다.
• 결합: 두 경우의 해결책 중 더 가치가 높은 것을 선택합니다. (분할 정복만으로는 완전한 해결이 어렵습니다.)

하지만, 이 문제의 경우 그리디 알고리즘만으로는 최적의 해를 보장할 수 없다는 점을 유의해야 합니다.

5. 분할 정복과 그리디 알고리즘의 차이점

분할 정복과 그리디 알고리즘은 모두 문제를 해결하는 데 사용되지만, 접근 방식과 적용 분야에서 차이가 있습니다.

6. 주의사항과 트러블슈팅

분할 정복 알고리즘을 설계하고 구현할 때 몇 가지 주의사항이 있습니다.

• 종료 조건: 재귀 호출이 무한히 반복되지 않도록, 올바른 종료 조건을 설정해야 합니다. 종료 조건은 하위 문제가 더 이상 분할할 수 없을 정도로 작아졌을 때입니다.
• 결합 단계: 하위 문제의 해결책을 결합하는 과정이 효율적이어야 합니다. 결합 단계의 시간 복잡도가 전체 알고리즘의 성능에 영향을 미칠 수 있습니다.
• 균형 분할: 하위 문제의 크기가 균형을 이루도록 분할하는 것이 중요합니다. 불균형한 분할은 알고리즘의 효율성을 저하시킬 수 있습니다.
• 중복 계산: 재귀 호출 과정에서 중복된 계산이 발생할 수 있습니다. 이러한 경우, 동적 계획법(Dynamic Programming)을 사용하여 중복 계산을 피할 수 있습니다.

7. 결론

분할 정복은 문제를 효과적으로 해결하기 위한 강력한 알고리즘 설계 기법입니다. 문제를 나누어 해결함으로써, 복잡한 문제를 단순화하고, 시간 복잡도를 개선할 수 있습니다. 그리디 알고리즘과 함께 사용하면, 최적화 문제에 대한 효율적인 해결책을 찾을 수 있습니다. 분할 정복의 개념을 이해하고, 다양한 문제에 적용해 봄으로써 알고리즘 설계 능력을 향상시킬 수 있습니다.