Divide and Conquer(분할 정복)

Divide and Conquer(분할 정복)

분할 정복(Divide and Conquer)은 큰 문제를 작은 부분 문제로 분할하여 해결하는 알고리즘 설계 패러다임입니다.
이 패러다임은 문제를 더 작은 하위 문제로 분할한 다음, 각 하위 문제를 재귀적으로 해결하고, 그 결과를 합쳐서 원래 문제의 해를 얻는 방식으로 동작합니다.
이러한 분할 정복 접근 방식은 문제를 더 작고 관리하기 쉬운 부분으로 나누어서 효과적으로 해결하는 데 사용됩니다.

분할 정복 알고리즘은 보통 다음의 세 단계로 진행됩니다.

1. 분할(Divide): 주어진 문제를 더 작은 하위 문제로 분할합니다. 이때, 하위 문제는 원래 문제와 구조적으로 유사해야 합니다.

2. 정복(Conquer): 작은 하위 문제들을 재귀적으로 해결합니다. 이 단계에서 하위 문제의 크기가 충분히 작아질 때까지 알고리즘이 반복됩니다.

3. 결합(Combine): 작은 하위 문제들의 해를 결합하여 원래 문제의 해를 구합니다. 이 단계에서 작은 하위 문제들의 해를 합치거나 조합하여 최종 결과를 얻습니다.

예

아래 예시는 1부터 10까지의 합을 분할 정복을 사용하여 구하는 예시 코드입니다.

def divide_and_conquer_sum(start, end):
    if start == end:
        return start
    else:
        mid = (start + end) // 2
        left_sum = divide_and_conquer_sum(start, mid)
        right_sum = divide_and_conquer_sum(mid + 1, end)
        return left_sum + right_sum

# 예시: 1부터 10까지의 합
result = divide_and_conquer_sum(1, 10)
print("1부터 10까지의 합:", result)

위의 코드의 과정은 아래와 같습니다.

첫 번째 호출: divide_and_conquer_sum(1, 10)

• mid = 5
• left_sum = divide_and_conquer_sum(1, 5)
• right_sum = divide_and_conquer_sum(6, 10)
• return 15 + 40 = 55

divide_and_conquer_sum(1, 5) 호출

• mid = 3
• left_sum = divide_and_conquer_sum(1, 3)
• right_sum = divide_and_conquer_sum(4, 5)
• return 6 + 9 = 15

divide_and_conquer_sum(1, 3) 호출

• mid = 2
• left_sum = divide_and_conquer_sum(1, 2)
• right_sum = divide_and_conquer_sum(3, 3) (기본 케이스: return 3)
• return 3 + 3 = 6

divide_and_conquer_sum(1, 2) 호출

• mid = 1
• left_sum = divide_and_conquer_sum(1, 1) (기본 케이스: return 1)
• right_sum = divide_and_conquer_sum(2, 2) (기본 케이스: return 2)
• return 1 + 2 = 3

divide_and_conquer_sum(4, 5) 호출

• mid = 4
• left_sum = divide_and_conquer_sum(4, 4) (기본 케이스: return 4)
• right_sum = divide_and_conquer_sum(5, 5) (기본 케이스: return 5)
• return 4 + 5 = 9

divide_and_conquer_sum(6, 10) 호출

• mid = 8
• left_sum = divide_and_conquer_sum(6, 8)
• right_sum = divide_and_conquer_sum(9, 10)
• return 21 + 19 = 40

이하 과정도 비슷한 방식으로 계속되어, 최종 결과로 55를 얻게 됩니다.

이 코드의 세 단계는 다음과 같습니다.

1. 분할(Divide):

• 주어진 범위는 1부터 10까지입니다.
• 범위를 두 개의 하위 범위로 분할합니다. 중간 값인 5를 기준으로 왼쪽 범위는 1부터 5까지, 오른쪽 범위는 6부터 10까지가 됩니다.

2. 정복(Conquer):

• 왼쪽 범위인 1부터 5까지의 합을 구합니다.
  • 이를 위해 재귀를 사용해 분할(Divide)과정을 다시 거칩니다.
• 오른쪽 범위인 6부터 10까지의 합을 구합니다.

3. 결합(Combine):

• 왼쪽 범위와 오른쪽 범위의 합을 합칩니다.
  • 15 + 40 = 55