[알고리즘] 분할정복(Divide and Conquer)

오늘은 분할정복에 대해서 설명해보도록 하겠습니다. 우선 분할정복이란 문제를 여러 개의 작은 하위 문제로 나누고, 각각을 독립적으로 해결한 뒤, 그 결과를 결합하여 전체 문제를 해결하는 방식입니다. 이렇게보면 동적계획법이랑 다른게 없어 보일 수 있습니다. 하지만 이 두 알고리즘은 두 차이점이 존재합니다.

 

분할정복vs동적계획법

분할정복 (Divide and Conquer)

• 아이디어: 문제를 여러 개의 작은 하위 문제로 나누고, 각각을 독립적으로 해결한 뒤, 그 결과를 결합하여 전체 문제를 해결하는 방식입니다.
• 특징
  • 하위 문제들이 서로 독립적입니다. 즉, 서로 겹치지 않으며, 동일한 부분 문제를 여러 번 해결하지 않습니다.
  • 예시는 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search) 등이 있습니다.
• 예시: 병합 정렬에서 배열을 반으로 나누어 각각 정렬한 후 두 개의 정렬된 배열을 병합하여 최종 결과를 얻습니다.

동적계획법 (Dynamic Programming)

• 아이디어: 문제를 작은 하위 문제로 나누는 것은 분할정복과 동일하지만, 동적계획법에서는 하위 문제들 간에 중복이 존재할 때, 그 중복된 계산을 피하기 위해서 메모이제이션(Memoization) 또는 테이블을 사용한 방법(Tabulation)으로 이미 계산한 결과를 저장하고 재활용합니다.
• 특징:
  • 중복된 하위 문제가 존재합니다.
  • 한 번 계산한 결과를 저장하여 다시 계산하지 않음으로써 효율성을 높입니다.
  • 대표적인 예시는 피보나치 수열(Fibonacci Sequence) 계산, 최장 공통 부분 수열(Longest Common Subsequence), 배낭 문제(Knapsack Problem) 등이 있습니다.
• 예시: 피보나치 수를 동적계획법으로 계산할 때, 이미 계산한 피보나치 값을 저장하여 다시 계산하지 않고 바로 사용합니다.

이렇게 봤을 때 나오는 큰 차이점은 동적계획법은 메모이제이션이랑 테이블을 이용한다는 사실을 알 수 있습니다. 하지만 오늘은 분할정복에 대해서 알아보도록 하겠습니다.

 

1. 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)은 분할정복 알고리즘의 일종으로, 배열을 계속해서 절반으로 나눈 뒤, 나눈 배열을 정렬하면서 병합하는 방식입니다.

병합정렬을 사용하는 예시 입니다.

병합정렬의 시간 복잡도에 대해서 설명하도록 하겠습니다.

아래의 그림에서 분할하는 과정에서 시간 복잡도는 O(log2n)입니다.

그리고 다시 다시 정복한하는 과정에서 비교해야 하므로 즉 n번이 발생하게 되므로 시간 복잡도는 O(nlog2n)이 발생하게 됩니다.

 

병합 정렬 코드

# 병합 정렬 함수
def merge_sort(arr):
    # 배열의 길이가 1 이하일 경우 바로 반환
    if len(arr) <= 1:
        return arr

    # 배열을 중간 기준으로 나누기
    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):
    sorted_arr = []
    i = j = 0

    # 두 배열을 비교하면서 작은 값을 결과 배열에 추가
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_arr.append(left[i])
            i += 1
        else:
            sorted_arr.append(right[j])
            j += 1

    # 남은 요소들을 결과 배열에 추가
    sorted_arr.extend(left[i:])
    sorted_arr.extend(right[j:])

    return sorted_arr

# 예시 배열
arr = [5, 4, 7, 8, 1, 3, 2, 6]

# 병합 정렬 실행
sorted_arr = merge_sort(arr)
print("정렬된 배열:", sorted_arr)

 

2. 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)은 분할 정복 알고리즘 중 하나로, 배열에서 피벗(pivot)을 기준으로 요소들을 두 그룹으로 나누고, 이를 재귀적으로 정렬하는 방식입니다.

pivot을 설정하고 이를 기준으로 작은 값은 왼쪽 큰 값은 오른쪽으로 위치를 조정합니다.

 

그림으로 예시를 표현했습니다. 다음으로는 코드의 예시를 보도록 하겠습니다.

 

퀵 정렬 코드

# 퀵 정렬 함수
def quick_sort(arr):
    # 배열의 길이가 1 이하이면 바로 반환
    if len(arr) <= 1:
        return arr

    # 피벗을 배열의 첫 번째 요소로 설정
    pivot = arr[0]
    
    # 피벗보다 작은 값들 (왼쪽)
    left = [x for x in arr[1:] if x < pivot]
    
    # 피벗보다 큰 값들 (오른쪽)
    right = [x for x in arr[1:] if x >= pivot]

    # 왼쪽과 오른쪽을 재귀적으로 정렬하고, 피벗을 가운데에 넣음
    return quick_sort(left) + [pivot] + quick_sort(right)

# 예시 배열
arr = [5, 4, 7, 8, 1, 3, 2, 6]

# 퀵 정렬 실행
sorted_arr = quick_sort(arr)
print("정렬된 배열:", sorted_arr)

 

3. 이분 탐색(Binary Search)

https://newkimjiwon.tistory.com/188

[알고리즘] 이분 탐색(Binary Search)

 

더 알아보기

이렇게 보면 1. 병합 정렬과 2. 퀵 정렬의 시간 복잡도는 똑같다는 사실을 알 수 있습니다. 하지만 많은 사람들은 정렬을 사용할 대 병합 정렬 대신 퀵 정렬을 사용하는 것을 알 수 있습니다. 그 이유는 다음과 같습니다.

1. 실제 상수 계수의 차이

퀵 정렬과 병합 정렬의 시간 복잡도가 O(N log N)으로 같더라도, 상수 계수의 차이가 있습니다. 시간 복잡도에서 상수 계수는 알고리즘의 실제 수행 시간에 영향을 미치는데, 퀵 정렬은 병합 정렬에 비해 상수 계수가 작습니다. 그 이유는

• 퀵 정렬은 제자리 정렬(in-place sort) 알고리즘입니다. 즉, 추가적인 배열을 사용하지 않고 주어진 배열 내에서 정렬을 수행합니다.
• 병합 정렬은 병합 단계에서 새로운 배열을 할당하여 정렬된 배열을 병합하기 때문에, 메모리 사용과 복사에 시간이 더 소요됩니다. 이로 인해 병합 정렬은 상수 계수가 더 크며, 퀵 정렬보다 메모리 사용도 더 큽니다.

2. 캐시 효율성

퀵 정렬은 배열의 요소들이 지역적으로 접근되기 때문에, CPU 캐시 메모리를 더 효과적으로 사용합니다. 캐시 히트율이 높아져 퀵 정렬이 더 빠르게 실행될 수 있습니다.

• 퀵 정렬에서는 파티션 과정에서 배열 내에서 인접한 요소들끼리 자주 비교하고 교환합니다. 따라서 메모리 접근 패턴이 비교적 연속적이라 캐시 효율이 높습니다.
• 반면, 병합 정렬은 병합 과정에서 배열의 다른 부분을 비교하고 결합해야 하기 때문에, 메모리 접근이 더 불규칙해질 수 있습니다. 그 결과 캐시 효율이 낮아질 수 있습니다.

3. 분할 방식

퀵 정렬은 최적의 경우 균형 잡힌 분할을 하여 두 하위 배열이 거의 같은 크기로 나뉩니다. 이렇게 되면 병합 정렬과 마찬가지로 O(N log N) 성능을 유지할 수 있습니다.

• 하지만 최악의 경우(매번 나누는 피벗이 매우 불균형하게 선택되는 경우)에는 O(N^2)가 될 수 있습니다. 그럼에도 불구하고, 대부분의 경우 퀵 정렬은 균형 잡힌 분할을 하여 빠르게 동작합니다.
• 병합 정렬은 항상 균형 있게 배열을 절반으로 나누지만, 병합 과정에서 추가적인 메모리와 연산이 필요합니다.

4. 실제 데이터 분포

퀵 정렬은 실무에서 사용되는 데이터의 분포가 적절할 때 매우 빠릅니다. 특히, 퀵 정렬은 평균적으로 파티션이 균형 있게 이루어질 때 매우 좋은 성능을 보입니다. 이와 달리 병합 정렬은 데이터 분포에 관계없이 고정된 방식으로 나누고 병합하므로, 최적화 여지가 적습니다.

요약

퀵 정렬이 병합 정렬보다 실제로 더 빠른 이유는 다음과 같습니다:

• 상수 계수가 작다 (제자리 정렬이므로).
• 메모리 효율성이 좋고, 추가 메모리 사용이 적다.
• 캐시 효율성이 높아 CPU 자원을 더 효과적으로 활용한다.
• 평균적으로 데이터 분포에 적응하여 좋은 성능을 보인다.

다만, 퀵 정렬의 경우 최악의 경우 O(N^2)가 될 수 있다는 단점이 있지만, 이는 보통 랜덤 피벗을 선택하거나 피벗 선택 전략을 개선하여 완화할 수 있습니다.