1. 분할 정복 알고리즘
•
분할 정복(Divide and Conquer) 알고리즘은 큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘이다.
◦
문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다.
2. 동작 방식
1.
문제를 작은 부분 문제들로 분할한다.
2.
분할된 부분 문제들을 각각 재귀적으로 해결한다.
3.
부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다.
3. 병합 정렬(Merge Sort)
.gif&blockId=1b35ca9b-265e-8156-9259-d6035fe7c158)
•
병합 정렬(Merge Sort)은 대표적인 분할 정복 알고리즘을 사용하는 정렬 알고리즘이다.
•
분할과 정복을 모두 사용하여 리스트를 반으로 나누어 각각을 재귀적으로 정렬하고, 정렬된 두 개의 부분 리스트를 합쳐 전체 리스트를 정렬하는 방식
•
동작 과정
1.
분할: 입력 리스트를 반으로 나눈다.
2.
정복: 각각의 부분 리스트를 재귀적으로 병합 정렬한다.
3.
결합: 정렬된 부분 리스트를 합쳐 전체 리스트를 정렬한다.
•
파이썬 구현 코드 -
# 입력 리스트를 반으로 나누고 재귀적으로 호출하여 각각을 정렬하는 재귀 함수
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
복사
