[Algorithm] 분할 정복

분할 정복

분할 정복은 직접 해결할 수 있을 정도로 간단한 문제가 될 때까지 문제를 재귀적으로 쪼갠 다음, 그 하위의 결과들을 조합하여 원래 문제의 결과로 만들어 낸다.

• 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.
• 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
• 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

분할 정복의 대표적인 알고리즘은 머지 소트(병합 정렬)이 있으며, 유클리드 호제법(최대공약수 알고리즘)도 이에 해당된다.

 

병합 정렬

배열을 절반으로 나누어 각각 정렬한 후 병합하는 방식

def merge_sort(arr):
    if len(arr) <= 1:
        return arr  # 기본 케이스: 길이가 1 이하이면 그대로 반환

    mid = len(arr) // 2  # 배열을 반으로 나눔
    left_half = merge_sort(arr[:mid])  # 왼쪽 부분 정렬
    right_half = merge_sort(arr[mid:])  # 오른쪽 부분 정렬

    return merge(left_half, right_half)  # 정렬된 두 부분을 병합 -> 정복

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 남은 요소들 추가
    result.extend(left[i:])
    result.extend(right[j:])

    return result

# 테스트
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("정렬된 배열:", sorted_arr)

유클리드 호제법

큰 수를 작은 수로 나눈 나머지를 활용하여 재귀적으로 최대공약수를 구하는 방식

def gcd(a, b):
    if b == 0:
        return a  # b가 0이면 a가 최대공약수
    return gcd(b, a % b)  # 유클리드 호제법 재귀 호출

# 테스트
a, b = 56, 98
print(f"{a}와 {b}의 최대공약수:", gcd(a, b))