코딩 테스트 대비! 파이썬으로 분할 정복(Divide and Conquer) 기법 구현하기

파이썬으로 분할 정복(Divide and Conquer) 기법 구현하기


문제 설명

주어진 배열을 오름차순으로 정렬하는 병합 정렬(Merge Sort) 알고리즘을 분할 정복 기법으로 구현하세요.


예시 입출력

입력: nums = [38, 27, 43, 3, 9, 82, 10]
출력: [3, 9, 10, 27, 38, 43, 82]

솔루션 코드

def merge_sort(nums):
    if len(nums) <= 1:
        return nums

    mid = len(nums) // 2
    left = nums[:mid]
    right = nums[mid:]

    left = merge_sort(left)
    right = merge_sort(right)

    return merge(left, right)

def merge(left, right):
    result = []
    i, j = 0, 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

# 테스트 케이스
nums = [38, 27, 43, 3, 9, 82, 10]
print("정렬 결과:", merge_sort(nums))

코드 설명

이 포스팅에서는 분할 정복(Divide and Conquer) 기법을 활용한 병합 정렬 알고리즘을 파이썬으로 구현했습니다. 분할 정복 기법은 복잡한 문제를 작은 부분 문제로 나누어 해결하고, 이를 결합하여 전체 문제를 해결하는 방식입니다. 이 기법은 코딩 테스트와 실무에서 다양하게 활용되므로 반드시 학습해야 합니다.

병합 정렬(Merge Sort)은 분할 정복 기법을 활용한 대표적인 정렬 알고리즘입니다. 주어진 배열을 절반으로 분할하여 각각 정렬한 뒤, 두 정렬된 배열을 병합하는 방식으로 동작합니다.

1. 분할(Divide): 주어진 배열을 절반으로 분할합니다.
2. 정복(Conquer): 분할된 부분 배열을 재귀적으로 정렬합니다.
3. 결합(Combine): 정렬된 두 부분 배열을 병합하여 전체 배열을 정렬합니다.

코드에서는 `merge_sort` 함수에서 분할 정복 기법을 구현했습니다. 기본 단계에서는 길이가 1 이하인 배열을 그대로 반환합니다. 그렇지 않은 경우, 배열을 절반으로 분할하고 각각을 `merge_sort`에 재귀 호출하여 정렬합니다. 이후 `merge` 함수를 호출하여 정렬된 두 부분 배열을 병합합니다.

`merge` 함수에서는 두 정렬된 배열을 병합하는 과정을 구현했습니다. 두 배열에서 작은 값부터 차례로 결과 배열에 추가하고, 남은 요소들을 이어 붙입니다.

분할 정복 기법은 복잡한 문제를 작은 부분 문제로 나누어 해결하므로, 효율적인 알고리즘 설계가 가능합니다. 특히 병합 정렬은 시간 복잡도가 O(n log n)으로 효율적이며, 안정 정렬(stable sort)의 특성을 가지고 있습니다.

이처럼 분할 정복 기법은 다양한 알고리즘 문제에 응용될 수 있으므로, 코딩 테스트와 실무에서 중요한 기술입니다. 이 기법을 잘 익히면 복잡한 문제도 체계적으로 해결할 수 있습니다.