[파이썬] 알고리즘 패러다임 : Divide and Conquer (합병 정렬, 퀵 정렬)

2023.02.25 ~ 2023.02.26 코드잇 학습내용

 

🔎 Divide and Conquer 분할 정복

분할 정복 알고리즘(Divide and Conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 알고리즘. 퀵 정렬이나 합병 정렬로 대표되는 정렬 알고리즘 문제와 이진 탐색 알고리즘, 행렬 곱셈 등이 분할 정복 알고리즘을 사용

 

분할 정복 알고리즘은 보통 재귀 함수(recursive function)를 통해 자연스럽게 구현됨. 따라서 분할 정복을 이해하기 위해서는 재귀 개념에 대한 이해가 우선함. 

 

function F(x) : 
    # base case
    if F(x)의 문제가 간단:
        return F(x)을 직접 계산한 값 

    # 재귀함수
    x를 y1과 y2로 분할
    F(y1)과 F(y2)를 호출
    return F(y1), F(y2)로부터 F(x)를 구한 값

 

위와 같이 기존 문제를 작은 부분 문제로 나누어 각 부분 문제를 풀고 부분 문제의 솔루션을 이용해 기존의 큰 문제를 해결하는 방식

 

Divide and Conquer 3 steps
1. Divide
문제를 해결하기 쉽게 하기 위해 더 작은 부분 문제로 나눔.
이 단계는 부분 문제가 직접 해결이 가능할 때까지(base case) 충분히 작게 재귀적으로 행해짐 
2. Conquer
부분 문제를 독립적으로 푸는 단계.
이 단계에서는 문제에 따라 병렬 혹은 순차적으로 수행
3. Combine
원래의 문제를 해결하기 위해 부분 문제의 해결책을 결합하는 단계

 

분할 정복 알고리즘은 종종 알고리즘의 시간 복잡성을 지수에서 다항식, 로그 또는 선형 시간 복잡성으로 줄이기 때문에 효율성을 상당히 향상시킬 수 있음. 그러나 하위 문제와 해결책을 추적하기 위해 추가 메모리가 필요할 수 있음.

 

📖 Divide and Conquer 문제

⚙ start 부터 end까지의 합 구하기

① 문제를 최대한 작게 쪼개어 base case를 구한다. 

② 문제를 부분으로 나눈다 : start부터 end까지의 합 = start부터 mid까지의 합 + (mid+1)부터 end까지의 합

③ 부분 문제를 풀고 부분 문제의 합을 서로 더한다. (재귀함수 : 자기 자신을 호출하는 함수)

 

📖 합병 정렬 (Merge Sort)

1945년 존 폰 노이만에 의해 개발된 합병 정렬은 O(n log n) 비교 기반 정렬 알고리즘으로 분할 정복 알고리즘의 하나.

합병 정렬에서 궁극적인 목표는 전체 리스트를 정렬하는 것. 하위 문제는 하위 리스트를 정렬하는 것. 

 

▼▼ 합병 정렬 전개 과정 ▼▼

 

출처 : 칸 아카데미

 

합병 정렬 작동 방식
1. base case (탈출 조건)
리스트의 길이가 1 이하이면 이미 정렬된 것으로 봄
2. Divide
정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔
3. Conquer
각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬
4. Combine
두 부분 리스트를 다시 하나의 정렬된 리스트로 합병 

 

⚙ Combine을 위한 merge 함수 작성하기

두 개의 리스트를 정렬된 하나의 리스트로 합치는 함수

합병 정렬에서 combine에 해당

① 두 개의 리스트를 순서대로 정렬할 빈 리스트 생성 (merged_list)

② 반복문을 사용하여 list1과 list2의 값을 하나씩 비교하면서 확인

     → list1[i] 와 list2[j]의 값을 비교하여 더 작은 값을 merged-list에 추가하고, 추가된 list는 다음 인덱스로 넘어감

③ 만약, list1이나 list2에서 정렬을 다하여 i(j) == len(list1(2))가 되면 아직 정렬이 되지 않은 list를 merged_list에 추가

④ merged_list 리턴

 

합병 정렬에서는 위와 같이 combine에서 많은 일을 수행

▼▼▼ merge 함수 실행 과정 ▼▼▼

 

⚙ 합병 정렬 함수 merge_sort 작성하기

① base case 탈출 조건 작성 : my_list의 길이가 1 이하이면 이미 정렬된 것으로 보아 my_list 리턴

② my_list는 2개의 리스트로 divide 

③ 재귀 함수와 merge 함수를 사용하여 두 부분 리스트를 하나의 정렬된 리스트로 합병

 

📖 퀵정렬 (Quicksort)

combine 단계에서 많은 일을 수행하는 합병 정렬과 달리 퀵 정렬에서는 pivot과 partition을 사용하며 divide에서 많은 일을 수행

퀵 정렬에서 리스트를 나누는 과정(divide)을 partition이라고 함

 

⚙ 퀵 정렬을 위한 partition(divide) 함수 작성하기

partition의 2단계

① 리스트에서 pivot 즉, 기준점 정하기 (보통 첫 번째 혹은 마지막 값을 pivot으로 설정)

② pivot을 기준으로 값들을 새롭게 배치 : pivot 보다 작은 값은 왼쪽으로, 큰 값은 오른쪽에 배치

 

partition 작동 방식
def partition(my_list, start, end) :
    # pivot 기준점 : 기준점 pivot을 마지막 값으로 설정
    p = end
    # big 그룹이 시작되는 부분 (pivot 보다 큰 값)
    b = start    # 맨 처음 인덱스에서 시작
    # unknown(아직 pivot과 비교하지 않은 부분)의 시작점
    i = start    # 맨 처음 인덱스에서 시작
        if list[i] > p:
            big 그룹에 속함
            i += 1
        else: 
            small 그룹에 속함 → b의 시작점과 i의 위치를 바꿈 
            i += 1, b += 1
    # i가 pivot 위치까지 오면
       i의 위치와 b의 위치를 바꿈

 

▼▼▼ partition 함수 정의 ▼▼▼

 

▼▼▼ 내가 작성한 코드 ▼▼▼

차이점 : while문 안과 밖에서 if 문을 사용하여 작성 →  while문 밖 조건문, while문 안 else는 굳이 작성하지 않아도 됨

왜? i += 1은 조건을 만족할 때나 만족하지 않을 때 모두 실행되어야 하므로 if문을 my_list[i] <= my_list[p]하나로 작성하고 if 조건문이 끝나면 i += 1을 실행하도록 작성하면 코드 한 줄을 줄일 수 있음

또한, i == end는 while문이 끝났다는 것을 의미하므로 if문이 없더라도 실행이 되게 되어 있음

 

⚙ 퀵 정렬 함수(quick sort) 작성하기

Quicksort 작동 방식
1. Divide : partition
2. Conquer : pivot 왼쪽에 있는 값과 pivot 오른쪽에 있는 값을 각각 정렬 
3. Combine : 할일이 없음
4. base case : 리스트에 값이 하나밖에 없을 때

퀵 정렬 함수는 합병 정렬과 달리 정렬된 새로운 리스트를 리턴하는 게 아니라, 파라미터로 받는 리스트 자체를 정렬함

① base case 작성 : quicksort함수는 재귀적으로 호출되면서 파라미터 start와 end만 바뀜

    따라서 end - start < 0 (리스트의 길이가 0 또는 1인 경우) 이면 return

    퀵 정렬은 새로운 리스트를 리턴하는 것이 아니기 때문에 return만 작성하여 함수 호출을 끝냄

② Divide : partition 과정을 통해, pivot을 기준으로 리스트를 나눔

③ Conquer : pivot 왼쪽 부분과 pivot 오른쪽 부분을 각각 quicksort 함수로 정렬

     → 이부분에서 막혔음. 이렇게 작성했다고 생각했는데 왜 안 됐지...??

④ Combine : 없음

⑤ 추가 : quicksort에서 start와 end 파라미터가 없을 때에도 작동하도록 만들기 (옵셔널 파라미터 사용하기)

옵셔널 파라미터
파라미터 없이 함수를 호출할 수 있음 → 더 깔끔한 코드 작성 가능

사용 방법 
파라미터 = "값" 
함수 내 파라미터를 변수로 하는 값을 사용하고 싶으면 파라미터 = None 사용 후
함수 안에 if 파라미터 == None: 사용하여 기본값 지정

 

 

references

[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog

 

합병 정렬 - 위키백과, 우리 모두의 백과사전

 

병합 정렬이란? (개념 이해하기) | 알고리즘 | Khan Academy