분할 정복 Divide and Conquer

/
큰 문제를 여러 개의 작은 문제로 나눠 해결하고 결과를 결합해 하나의 해결 방법을 얻는 알고리즘 (재귀에 대한 이해 필요!)

분할 정복 방식 :

1. Divide - 큰 문제를 부분 문제로 분할
2. Conquer - 각 부분 문제를 정복 (base case까지 반복 : 문제가 충분히 작아서 바로 풀 수 있는 경우)
3. Combine - 부분 문제의 솔루션 합치기

Conquer 단계 안에서 1~3번을 다시 반복하는 재귀적인 풀이가 필요해질 수도 있다.

분할 정복 예제 :

➲ 1부터 n까지의 합

1. Divide : n을 반으로 나눈다.
2. Conquer : 각 부분 문제를 재귀적으로 푼다. (각각 더하기 반복)
   • base case : 하나씩 더하며 시작점이 마지막에 도달했을 때
3. Combine : 각 더한 값을 합친다.

1. 1~4의 합, 5~8의 합으로 분할
2. 10, 26
   • 1~2의 합, 3~4의 합 구하기
     - 1~1의 합, 2~2의 합 구하기
   • 5~6의 합, 7~8의 합 구하기
     - 5~5의 합, 6~6의 합 구하기
3. 5050

# 1부터 n까지의 합
def consecutive_sum(start, end):
    # base case        
    if end == start:
        return start

    # 부분 문제를 반으로 나눠주기 위해서 문제의 정중앙을 정의한다 (Divide)
    mid = (start + end) // 2

    # 각 부분 문제를 재귀적으로 풀고(Conquer), 부분 문제의 답을 서로 더한다(Combine).
    return consecutive_sum(start, mid) + consecutive_sum(mid + 1, end)

➲ 합병 정렬 Merge sort

1. Divide : 리스트 슬라이싱을 통해 반으로 나눈다.
2. Conquer : 왼쪽 리스트와 오른쪽 리스트를 각각 정렬한다. (재귀; 나누고 합치기)
   • base case : list의 길이가 0이거나 1로, 이미 정렬된 상태
3. Combine : 정렬된 두 리스트를 하나의 정렬된 리스트로 합병한다. (왼쪽 오른쪽 각각 가장 작은 값들을 비교하면서 더 작은 값을 먼저 정렬)

# 합병 정렬
def merge(list1, list2):
    i, j = 0, 0 
    merged_list = []
    
    while i < len(list1) and j < len(list2):
        if list1[i] > list2[j] :
            merged_list.append(list2[j])
            j += 1
        else :
            merged_list.append(list1[i])
            i += 1
            
        if i == len(list1) :
            merged_list += list2[j:]
        elif j == len(list2) :
            merged_list += list1[i:]
    return merged_list

# mid 변수로 리스트를 반씩 나눌 수 있게 준비했다. (divide)
# merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고,
# merge 함수로 정렬된 두 리스트를 합쳐(combine)준다
def merge_sort(my_list):
    if len(my_list) <= 1 :
        return my_list
    mid = len(my_list) // 2
    return merge(merge_sort(my_list[:mid]), merge_sort(my_list[mid:]))

➲ 퀵 정렬 Quick sort

1. Divide : 파티션 Partition; 리스트를 나누는 과정 진행
   • 리스트에서 기준점 Pivot 정하기
   • 피벗 Pivot 기준 왼쪽에 작은 값, 오른쪽에 큰 값으로 나누어 정렬
2. Conquer : 피벗 왼쪽에 있는 값과 피벗 오른쪽에 있는 값을 각각 퀵 정렬한다.
   • base case : 피벗 양쪽으로 값이 하나씩밖에 없는 경우

# 퀵 정렬

# 두 요소의 위치를 바꿔주는 helper function
def swap_elements(my_list, index1, index2):
    my_list[index1], my_list[index2] = my_list[index2], my_list[index1]

# 퀵 정렬에서 사용되는 partition 함수
def partition(my_list, start, end):
    # 리스트 값 확인과 기준점 이하 값들의 위치 확인을 위한 변수 정의
    i, b = start, start
    p = end

    while i < p:
        # i 인덱스의 값이 기준점보다 작으면 i와 b 인덱스에 있는 값들을 교환하고 b를 1 증가 시킨다
        if my_list[i] <= my_list[p]:
            swap_elements(my_list, i, b)
            b += 1
        i += 1

    # b와 기준점인 p 인덱스에 있는 값들을 바꿔준다
    swap_elements(my_list, b, p)
    p = b
    return p   # pivot의 최종 인덱스

def quicksort(my_list, start=0, end=None):
	if end == None:
        end = len(my_list) - 1
    # base case
    if end - start < 1:
        return

    # my_list를 두 부분으로 나누어주고,
    # partition 이후 pivot의 인덱스를 리턴받는다
    pivot = partition(my_list, start, end)

    # pivot의 왼쪽, 오른쪽 부분 정렬
    quicksort(my_list, start, pivot - 1)
    quicksort(my_list, pivot + 1, end)

🌟 개발 블로그 참고 🌟
알고리즘과 자료구조 살펴보기

코드잇 알고리즘패러다임