동호의 블로그

1. 분할 정복 알고리즘

분할 정복(Divide and Conquer) 알고리즘은 큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘이다.

문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다.

2. 동작 방식

문제를 작은 부분 문제들로 분할한다.

분할된 부분 문제들을 각각 재귀적으로 해결한다.

부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다.

3. 병합 정렬(Merge Sort)

병합 정렬(Merge Sort)은 대표적인 분할 정복 알고리즘을 사용하는 정렬 알고리즘이다.

분할과 정복을 모두 사용하여 리스트를 반으로 나누어 각각을 재귀적으로 정렬하고, 정렬된 두 개의 부분 리스트를 합쳐 전체 리스트를 정렬하는 방식

동작 과정

분할: 입력 리스트를 반으로 나눈다.

정복: 각각의 부분 리스트를 재귀적으로 병합 정렬한다.

결합: 정렬된 부분 리스트를 합쳐 전체 리스트를 정렬한다.

파이썬 구현 코드 -


# 입력 리스트를 반으로 나누고 재귀적으로 호출하여 각각을 정렬하는 재귀 함수
def merge_sort(arr):
    # Base Case: 배열 길이가 1 이하이면 정렬할 필요 없음
    if len(arr) <= 1:
        return arr
    
    # Recursive Case: 배열을 반으로 나누어 정렬
    mid = len(arr) // 2
    left_sorted = merge_sort(arr[:mid])
    right_sorted = merge_sort(arr[mid:])

    # 두 정렬된 배열을 병합하여 반환
    return merge(left_sorted, right_sorted)

# 두 개의 정렬된 리스트를 인수로 받아, 두 리스트를 비교하여 작은 순서대로 result 리스트에 삽입하고, 남은 요소를 추가하여 반환
def merge(left, right):
    sorted_arr = []
    i, j = 0, 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

참고 자료

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

1. 분할 정복(Divide and Conquer)이란? 큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘 문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다. 대표적인 예로, 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다. 2. 동작 방식 문제를 작은 부분 문제들로 분할한다. 분할된 부분 문제들을 각각 재귀적으로 해결한다. 부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다. 3. 시간 복잡도 시간 복잡도는 일반적으로 부분 문제의 개수, 분할된 문제의 크기, 분할과정의 복잡도에 따라 결정된다. 대부분의 경우, 분할 정복 알고리즘은 재귀적인 방법으로 문제를 해결하므로, 재귀 호출의 깊이에 따라 ..

https://eunsun-zizone-zzang.tistory.com/72