[알고리즘 공부] 2. 분할 정복 알고리즘

 

 

 

 

 

 

안녕하세요 오늘은 분할 정복 (divide and conquer) 알고리즘에 대하여 알아보겠습니다. 

 

분할 정복(divide and conquer)은 문제를 더 작은 부분 문제로 분할하고 각 부분 문제를 재귀적으로 해결한 다음,

그 결과를 조합하여 전체 문제의 해답을 얻는 알고리즘 설계 패러다임입니다.

 

정렬, 수학, 그래프 알고리즘 등에 사용되며 오늘은 병합 정렬과 거듭제곱 예시를 통해 알아보겠습니다.

 

 

 

1. 병합 정렬 알고리즘 (Merge Sort)

 

병합 정렬은 분할 정복(divide and conquer) 전략을 사용하는 안정적인 정렬 알고리즘입니다.

이 알고리즘은 배열을 반으로 나눈 후, 각 부분을 재귀적으로 정렬하고,

두 정렬된 부분을 합병하여 최종 정렬된 배열을 만듭니다.

 

def merge_sort(arr):
    # 배열의 길이가 1 이하이면 배열을 그대로 반환합니다. 이미 정렬된 상태이기 때문입니다.
    if len(arr) <= 1:
        return arr
        
    # 배열을 중간 인덱스 mid를 기준으로 두 개의 하위 배열 left와 right로 나눕니다. ---> 분할
    mid = len(arr) // 2
    # merge_sort를 재귀적으로 호출하여 left와 right 하위 배열을 정렬합니다. ---> 정복
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    return merge(left, right)

# left와 right 배열의 요소를 비교하여 더 작은 값을 result에 추가하고 해당 인덱스를 증가시킵니다. ---> 합병
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]
print(merge_sort(arr))  # 출력: [3, 9, 10, 27, 38, 43, 82]

 

* 여기서 시간복잡도가 무엇인지 궁금하다면?

https://rhgustmfrh.tistory.com/176

[알고리즘 공부] * 시간복잡도란?

 

병합 정렬의 시간 복잡도

 

병합 정렬의 시간 복잡도는 항상 O(n log n)입니다.

이는 배열을 반으로 나누는 데 log n 단계가 걸리고,

각 단계에서 배열의 모든 요소를 병합하는 데 O(n) 시간이 걸리기 때문입니다.

 

공간 복잡도는 O(n)으로, 추가 배열을 사용하여 데이터를 저장하고 병합하는 동안 새로운 배열을 생성합니다.

 

 

 

응용 분야

병합 정렬은 다음과 같은 다양한 분야에서 응용될 수 있습니다:

 

대용량 데이터 정렬:

안정적인 O(n log n) 시간 복잡도로 대용량 데이터를 효율적으로 정렬할 수 있습니다.

특히 외부 정렬(external sorting)이 필요한 경우, 디스크에 저장된 데이터를 분할하고 정렬할 때 유용합니

 

연결 리스트 정렬:

연결 리스트에서 병합 정렬은 다른 정렬 알고리즘보다 효율적입니다.

연결 리스트에서 중간 지점을 찾고 분할한 후, 병합 과정을 통해 정렬할 수 있습니다.

 

분산 컴퓨팅:

분산 환경에서 데이터를 분할하여 각각의 노드에서 정렬한 후, 병합하여 전체 정렬된 데이터를 얻는 데 사용됩니다.

 

데이터베이스:

대규모 데이터베이스의 정렬 작업에서 병합 정렬이 사용됩니다.

특히 데이터베이스에서 정렬된 데이터를 병합하여 결과를 생성할 때 유용합니다.

 

온라인 쇼핑:

쇼핑 사이트에서 제품 목록을 정렬하여 사용자에게 보여줄 때 병합 정렬이 사용될 수 있습니다.

 

 

 

2. 거듭제곱 계산

 

주어진 코드는 분할 정복(Divide and Conquer) 전략을 사용하여 거듭제곱을 계산하는 함수입니다.

이 함수는 재귀적으로 거듭제곱 값을 계산하며,

지수(exponent)가 짝수인 경우와 홀수인 경우를 나누어 처리합니다.

이 코드는 O(log n) 시간 복잡도를 가지며, 효율적으로 큰 수의 거듭제곱을 계산할 수 있습니다.

 

def power(base, exponent):
    # exponent가 0이면, 어떤 수의 0승도 항상 1이므로 1을 반환합니다.
    if exponent == 0:
        return 1
    
    # exponent가 짝수인 경우, 
    # base^exponent는 (base^(exponent//2)) * (base^(exponent//2))와 같습니다. 
    # 따라서 base를 exponent의 절반에 해당하는 지수로 재귀적으로 계산한 값을 제곱하여 반환합니다.
    elif exponent % 2 == 0:
        half = power(base, exponent // 2)
        return half * half
        
    # exponent가 홀수인 경우, 
    # base^exponent는 (base^((exponent-1)//2)) * (base^((exponent-1)//2)) * base와 같습니다. 
    # 따라서 base를 exponent의 절반에 해당하는 지수로 재귀적으로 계산한 값을 제곱한 후 base를 한 번 더 곱하여 반환합니다.
    else:
        half = power(base, (exponent - 1) // 2)
        return half * half * base

# 테스트
base = 2
exponent = 10
print(power(base, exponent))  # 출력: 1024

 

 

분할 정복의 장점

이 알고리즘은 분할 정복 전략을 통해 연산 횟수를 줄입니다.

단순히 지수만큼 곱하는 반복문을 사용하는 방법은 O(n) 시간이 걸리지만,

분할 정복을 통해 이를 O(log n) 시간으로 줄일 수 있습니다. 이는 특히 큰 지수를 다룰 때 매우 효율적입니다.

 

응용 분야

이와 같은 거듭제곱 알고리즘은 여러 분야에서 사용될 수 있습니다:

 

암호학:

RSA와 같은 공개 키 암호화 알고리즘에서는 큰 수의 거듭제곱 연산이 빈번히 사용됩니다.

 

컴퓨터 그래픽스:

변환 행렬의 거듭제곱 계산이 필요할 때 사용됩니다.

 

물리학 및 공학:

시뮬레이션 및 모델링에서 반복적인 계산이 필요할 때 효율적인 거듭제곱 계산이 필요합니다.

 

수학적 계산:

수치 해석과 관련된 문제에서 빠른 거듭제곱 계산이 필요한 경우.