[자료구조] 7. Divide and Conquer 이해하기(feat. 합병정렬, 퀵정렬, codestates, self tutorial)

 

 

 

 

 

안녕하십니까 다제입니다. 

 

오늘은 Divide and Conquer에 대해서 함께 공부를 해보도록 하겠습니다. 

 

해당 포스팅은 재귀 개념을 확실히 알고 있어야 합니다. 

 

혹시 모르시는 분들은 재귀함수 포스팅 글을 다시 한번 봐주시면 감사드리겠습니다. 

2021.05.16 - [Code] - [자료구조] 3. 재귀함수(Recursion) 이해하기 (feat. codestates, self_tutorial)

[자료구조] 3. 재귀함수(Recursion) 이해하기 (feat. codestates, self_tutorial)

 

 

먼저 합병정렬과 퀵 정렬을 배우기 이전 Divide and Conquer(분할정복)의 개념에 대해서 집고 넘어가겠습니다. 

 

우리가 문제를 풀려고 하는데, 너무 복잡하여 한번에 문제가 풀 수 없는 경우가 있습니다. 

 

이런 경우, 문제를 분할하여 문제를 풀어보신 경험이 있으실 겁니다.

 

이처럼 프로그래밍에서도 너무 복잡하여 한번에 풀 수 없는 문제를 부분문제로 나누어서 해결하고 다시 합치는 풀이방법을 Divide and Conquer(분할정복)라 합니다. 

 

Divide and Conquer(분할정복)가 재귀와 개념이 비슷하다고 말하는 이유는 충분히 나누어져 있지 않을 때는 반복하여 리스트를 쪼개기 때문입니다. 

 

Divide and Conquer(분할정복) 구성은 크게 1. Divide(나누기) / 2. Conquer(정복) / 3. Combine(결합) 나눌 수 있습니다. 

또한, 대표적인 정렬로는 합병정렬과 퀵정렬이 있습니다. 

 

이에, 지금부터 2가지 정렬에 대해서 자세히 살펴보도록 하겠습니다. 

 

 

 

---

 

 

1. 합병정렬 

1) 정의 

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정령된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 정렬방법 ( 해당 과정에서 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. )

 

2) 구성 

① Divide(분할) - 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. (20과 25를 기준으로 분할)

② Conquer(정복) - 부분 배열의 크기가 충분히 작지 않으면 순환 호출(재귀)를 이용하여 다시 분할과 정복을 반복한다. 부분 배열을 각각 정렬한다. ([21, 10, 12, 20]이 충분히 작지 않아 계속 반복 분할, 충분히 분할된 상태에서 정렬을 진행함)

③ Combine(결합) - 정렬된 두 리스트를 하나의 정렬된 리스트로 합병한다. 이때 각각의 배열은 정렬이 되어 있기에 비교하여 작은 값들을 오름차순으로 정렬한다. 

출처 : 이미지 링크 참조

출처 : 이미지 링크 참조

 

3) 장단점

  -. 장점

    * 안정적인 정렬방법 

    * 만약 레코드를 연결 리스트로 구성하면 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다. 

    * 이에, 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면 합병정렬은 퀵 정렬을 포함한 다른 어떤 정렬보다 효율적이다. 

  

  -. 단점

    * 만약 레코드를 배열(Array)로 구성하면 임시 배열이 필요하다. 

    * 레코드들의 크기가 큰 경우네는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다. 

 

4) 소스코드(vscode로 반드시 debug를 돌려보셔야 합니다!!!)

소스코드를 바로 보여드리면, 절대 바로 이해가 되지 않으실거 같아 나누어서 순차적으로 보여드리고자 합니다. 

먼저 병합의 역할을 하는 코드를 보여드리겠습니다. 

 

아래 merge 함수는 정렬된 두 리스트 list1과 list2를 받아서, 하나의 정렬된 리스트를 리턴하는 함수를 완성하세요

def merge(list1, list2):
	return 
    
print(merge([1],[]))
print(merge([],[1]))
print(merge([4, 7, 8, 10],[1, 3, 6, 15]))

 

일반적인 경우, sort를 통해서 바로 해결할 수 있습니다. 

def merge(list1, list2):
    return sorted(list1+list2)

 

그러나, 저희는 알고리즘 또는 알고리즘적 사고에 대해서 배우고 있다는 사실에 대해 기억해야합니다. 

이에, 파이썬 내부에서는 어떤 일이 일어나는지를 생각해보고 코드를 직접 구현해보겠습니다. 

# 일단 두개의 리스트를 합칠 수 있도록 빈 리스트를 만들어야한다는 생각이 나야 합니다. 
# 또한, 여기에서 반드시 구현되어야 하는 기능이 인덱스가 하나씩 증가하는 것과 
# 그 인덱스를 가지고 리스트의 값을 찾아 두개의 리스트를 비교해야하는 기능을 구현해야 합니다. 
# 그리고 마지막으로 어디까지 인덱스가 증가시켜야하는지에 대해서 설정을 해주어야 합니다. 


def merge(list1, list2):

    # 빈리스트를 만듭니다. 
    merge_list = []

    # 증가 시킬 인덱스를 i,j로 변수를 설정합니다. 
    i = 0
    j = 0
    
    # 입력받은 리스트중에 [] 빈 리스트가 들어올 수도 있습니다. 
    # 빈 리스트가 들어로는 경우를 대비하여 코드를 구현해야합니다. 
    # 두개의 리스트를 비교하기 위한 코드를 구현합니다. 
    # 두 개의 리스트를 비교하다보면 어느 리스트가 먼저 다 정렬되어 merge_list로 들어가는 경우
    # 더 이상 비교하지 못하도록 len(list1) > i and len(list2) > j 코드를 구현합니다. 
    while len(list1) > i and len(list2) > j :
        if list1[i] > list2[j]:
            merge_list.append(list2[j])
            j+=1
        else:
            merge_list.append(list1[i])
            i+=1
        
    # 위에 len(list1) > i and len(list2) > j가 실행되고 더 이상 비교할 것이 없다면
    # list1 이나, list2의 길이만큼 i와 j가 증가할 것이다. 
    # 이 말은 비교가 되지 않은 나머지 값들만 남아 있다는 말입니다. 
    # 이에, 그 나머지들을 merge_list 뒤에 붙여주는 코드를 작성합니다. 
    if i == len(list1):
        merge_list += list2[j:]
    
    elif j == len(list2):
        merge_list += list1[i:]
    
    return merge_list

 

지금까지 다루었던 코드가 멀까? 이러시는 분들이 계실 수 있습니다. 

우리가 리스트를 받았을 때 반으로 나누고 나눈 리스트들을 또 나누어 정렬을 하는 과정이 합병정렬이라고 말씀드렸는데요. 위에서 다룬 코드는 반으로 나눈 리스트들을 정렬하는 뒷 과정부터 배워보았습니다. 

이제 진짜로 한개의 리스트가 들어오면 어떻게 반으로 나누어야하는지에 대해서 코드로 알아보도록 하겠습니다. 

def merge_sort(my_list):
    # Divide and Conquer로 문제를 풀기 위해서는 문제를 더 작은 부분 문제로 나누고, 재귀적으로 부분 문제들을 해결해야 합니다.
    # 재귀적으로 문제를 풀 때에는 늘 base case와 recursive case가 있어야 하죠?
    # 합병 정렬의 base case는 리스트가 이미 정렬이 되어 있을 때인데요. 
    # 리스트의 길이가 00이거나 11이면 이미 정렬된 리스트라고 볼 수 있습니다.
    if len(my_list) < 2:
        return my_list

    # 이제 my_list를 반씩 나눈다(divide)
    # //는 몫을 구하는 파이썬의 코드입니다. 
    
    left_half = my_list[:len(my_list)//2]    # 왼쪽 반
    right_half = my_list[len(my_list)//2:]   # 오른쪽 반

    # merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고,
    # merge 함수로 정렬된 두 리스트를 합쳐(combine)주면 합병정렬이 끝나게 됩니다. 
    return merge(merge_sort(left_half), merge_sort(right_half))

 

위에서 두 단계로 나누어서 진행하였던 합병정렬을 아래와 같이 하나의 코드로 구현할 수 있습니다. 

그러나, 저는 기능별로 함수 단위를 나누는 것을 좋아하기 때문에 위에 코드를 더 선호합니다. 

왜냐하면 이렇게 한 개의 함수로 정의되어 있으면 다른 사람들도 보기 불편하고 저도 나중에 보았을 때 무슨 역할을 하는 함수지? 라고 생각할 수 있기 때문입니다. 

# MergeSort 소스코드


def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 1)배열의 중간을 찾는다.

        L = arr[:mid]  # 중간이 정해지면, 전체배열을 두 부분으로 나눈다. L은 나눠진 왼쪽 부분
        R = arr[mid:]  # R은 나눠진 오른쪽 부분

        mergeSort(L)  # 2)왼쪽 부분에 대해 정렬 함수 호출을 통해 정렬(재귀적으로 값을 분할정복)

        mergeSort(R)  # 3)오른쪽 부분에 대해 정렬함수 호출을 통해 정렬(재귀적으로 값을 분할정복)

        i = j = k = 0

        # Merge 정렬 과정(배열의 인덱스를 참조하여 비교->정렬->교환한다는 것을 알아야 한다.)
        while i < len(L) and j < len(R):
            if L[i] < R[j]:  # 오른쪽값 > 왼쪽값
                arr[k] = L[i]  # 왼쪽값을 결과를 위한 값에 저장한다.
                i += 1  # 왼쪽배열값의 인덱스를 +1 증가시키고, 결과를 위한 배열에 저장한다.
            else:  # 왼쪽값 > 오른쪽값
                arr[k] = R[j]  # 오른쪽값을 결과를 위한 값에 저장한다.
                j += 1  # 오른쪽배열값의 인덱스를 +1 증가시키고, 결과를 위한 배열에 저장한다.
            k += 1

        # 왼쪽부분과 오른쪽부분에 대해 중간정렬결과를 확인해볼 수 있다.
        # print(L)
        # print(R)

        # 왼쪽에 남은 요소가 있는지 확인
        while i < len(L):
            arr[k] = L[i]  # 정렬된 왼쪽값을 결과를 위한 배열에 저장
            i += 1
            k += 1

        # 오른쪽에 남은 요소가 있는지 확인
        while j < len(R):
            arr[k] = R[j]  # 정렬된 오른쪽값을 결과를 위한 배열에 저장
            j += 1
            k += 1


# # 정렬된 결과 출력
# def printList(arr):
#     for i in range(len(arr)):
#         print(arr[i], end=" ")
#     print()


# 위의 정렬 알고리즘을 테스트하기 위한 테스트 코드
arr_origin = [7, 3, 2, 16, 24, 4, 11, 9]
print("정렬되기 전 테스트 배열", end="\n")
# printList(arr)


# 병합정렬 알고리즘을 적용하기 위해 처음으로 병합정렬 함수를 호출한다.
mergeSort(arr_origin)

print("병합정렬로 정렬된 결과 배열: ", end="\n")

 

 

---

 

 

2. 퀵 정렬 

Divide and Conquer를 사용하는 또 다른 정렬은 바로 퀵정렬입니다. 

퀵 정렬은  ‘찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)’가 개발한 정렬 알고리즘 입니다. 
퀵 정렬은 불안정 정렬 에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

비교하여 정렬을 진행하다보니 합병정렬과 다르게 나누는 단계에서 많은 노력이 들어갑니다. 

 

 

1) 정의 

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다.

 

* 참고사항 *
리스트를 분할과정을 퀵정렬에서는 partition(파티션)이라고 합니다. 

파티션에서는 pivot을 정하고, pivot을 기준으로 값을 새롭게 정의하는 2가지의 일이 진행이 됩니다. 

 

 

2) 구성 

① 분할(Divide) : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)로 분할한다.
② 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다.(리스트의 크기가 0이나 1이 될 때까지 반복한다.)
③ 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.
순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

출처 : 이미지 링크 참조

 

 

3) 장단점

분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 

추가 메모리 공간을 필요로 하지 않는다. 

정렬된 리스트에서는 오히려 수행시간이 더 많이 걸린다. 

합병 정렬(merge sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.

 

 

4) 소스코드

def quick_sort(node, first, last):
  def partition(first,last):
    pivot = node[last]
    left = first
    #print(pivot, first,last)    # 확인용
    for right in range(first, last):
      if node[right] < pivot:
        node[left], node[right] = node[right], node[left]
        left += 1
    node[left], node[last] = node[last], node[left]
    return left

  # 첫번째 노드가 마지막 노드보다 작은 경우, 재귀진행
  if first < last:
    pivot = partition(first, last)
    quick_sort(node, first, pivot - 1)
    quick_sort(node, pivot + 1, last)


node = [54,26,93,17,77,31,44,55,20]
quick_sort(node,0,8)

print(node)

 

 

 

 

지금까지 분할정복에서 합병정렬과 퀵정렬에 대해서 알아보았습니다. 

 

분할정복은 생각보다 포스팅이 많이 어렵다는 것을 느꼈습니다. 진도가 쭉쭉 나가지 않아 매우 고생하였습니다.

 

여러분도 공부하실때 포기하고 싶다는 생각이 많이 드실텐데 함께 하시죠!

 

이해가 안되시면 꼭 댓글 부탁드립니다. 매일매일 댓글 확인중에 있습니다.  

 

오늘도 방문하여 주셔서 감사합니다.