[Algorithm] 분할 정복(Divide&Conquer) ft. 합병 정렬, 퀵 정렬

 

이번 포스팅에서 다룰 알고리즘은 '분할 정복'이다.
Divide and Conquer

이 알고리즘은 문자 그대로, 분해해서 해결하는 것을 메인 흐름으로 가져간다.

밑의 그림을 보면 이해될 것이다.

 

* 실습 환경은 windows 10/ vscode에서 이뤄졌습니다.

 

 

 

 

 

 

 

📍 정의

 

한 번에 해결하기 어려운 문제(시간문제, 공간문제 등)를 잘게 쪼개고 각개 격파한 후, 하나의 답을 도출하는 알고리즘. 

분할 정복 알고리즘은 다음 세 개의 프로세스를 가진다. 

 

 

 

 

📍 Process

 

(1) Divide : 문제를 정의하고, 잘게 쪼개는 과정이다. 이 단계에서 문제를 잘 쪼개야 손쉽게 문제를 해결할 수 있다.

(2) Conquer : 잘게 쪼개진 문제를 해결할 시간이다. 분할 알고리즘의 문제는 쪼개도 사실상 같은 문제들이다.

(3) Obtain : 각자 해결되어 도출된 답을 하나로 합쳐서 최종 답안을 얻는다. 

 

 

 

 

📍 대표적인 알고리즘

 

(1) 합병정렬 : 정렬된 리스트를 Merge 하는 과정에서 효율적으로 정렬시키는 것을 목표로 하는 알고리즘.

(2) 퀵정렬 : pivot(기준점)을 기준으로 리스트를 나눠서 정렬하는 알고리즘.

 

두 알고리즘 모두 결국 (1) 나누고 (2) 해결하고 (3) 다시 리스트를 합치는 과정을 가진다. 이 과정 속에는 재귀 알고리즘도 포함된다. 처음 하나의 리스트를 두 개로 나누고, 두 개가 다시 네 개로 나뉘고. 잘게 나눠진 문제들을 해결하면서 다시 큰 답으로 돌아오는 형식이다. 

합병 정렬과 퀵 정렬을 살펴보면서 분할 정복 개념을 완벽하게 이해해보자.

 

 

 

 

 

📌 합병정렬

 

 

 

 

[Divide]

=> 리스트를 반으로 나눈다.

[Conquer] 

=> 나눈 리스트에서 재귀적으로 각각 합병 정렬 실행

[Obtain] 

=> 두 개의 정렬된 리스트를 합병하여 리턴

 

 

🎨 합병 정렬 코드

 

합병정렬 알고리즘은 두 개의 함수로 이뤄진다.

 

(1) 합병정렬 : 리스트에 대하여 합병 정렬을 시행하는 함수

(2) merge 함수 : 합병 정렬된 리스트를 병합하는 함수

 

# 합병정렬

def merge_sort(array):
  n = len(array)
  if (n <= 1):
    return array
  else:
  	# 중간에 반으로 딱 가르기
    mid = n // 2
    
    # 왼쪽 리스트에 대하여 합병정렬 실행
    left = merge_sort(array[0:mid])
    
    # 오른쪽 리스트에 대하여 합병정렬 실행
    right = merge_sort(array[mid:n])
    
    # merge 함수를 통해 정렬된 하나의 리스트로 만들기
    return merge(left, right)




# merge 함수(두 리스트를 정렬된 리스트로 합치기)

def merge(left, right):
  merged_list = []
  i = j= 0


  # 두 개의 리스트의 요소들을 비교해가며 순서대로 리스트에 적재
  while (i < len(left) and j < len(right)):
    if (left[i] < right[j]):
      merged_list.append(left[i])
      i += 1
    else:
      merged_list.append(right[j])
      j += 1
  
  
  # 남은 요소들은 모두 뒤에 합쳐주기
  if (i < len(left)):
    merged_list += left[i : len(left)]
  else:
    merged_list += right[j : len(right)]
  
  
  # 합병된 리스트 return
  return merged_list

 

결과

s = [1,34,56,7,8,9,10]
print(f"합병 정렬을 실행한 결과 : {merge_sort(s)}")


합병 정렬을 실행한 결과 : [1, 7, 8, 9, 10, 34, 56]

 

 

 

 

 

 

 

📌 퀵 정렬

 

 

 

[Divide]

=> 기준 값(pivot)을 기준으로 less, equal, more 리스트로 나눈다.

[Conquer]

=> 나눈 리스트(less, more)에서 재귀적으로 퀵 정렬 실행

[Obtain]

=> 정렬된 리스트를 리턴

 

 

🎨 퀵정렬 코드

 

def quicksort(array):

  # 길이가 1 이하인 경우, 그대로 반환합니다.
  if len(array) <= 1:
    return array
  
  # 기준 값을 배열을 맨 끝으로 잡습니다.
  pivot = array[-1]
  
  # less, more, equal 리스트 생성
  less, more, equal = [], [], []
  
  # pivot 값과 비교하여 리스트를 세 개로 나눕니다.
  for each in range(len(array)):
    each = array.pop()
    if each < pivot:
      less.append(each)
    elif each > pivot:
      more.append(each)
    else:
      equal.append(each)
  
  # less, more 리스트에 대하여 다시 재귀적으로 퀵 정렬을 시행하고, 합쳐주는 return 코드를 짭니다.
  return quicksort(less) + equal + quicksort(more)

 

결과

s = [1,34,56,7,8,9,10]
print(f"퀵 정렬을 실행한 결과 : {quicksort(s)}")


퀵 정렬을 실행한 결과 : [1, 7, 8, 9, 10, 34, 56]

 

 

 

지금까지 분할 정복 알고리즘과 더불어, 합병 정렬/퀵 정렬에 대해 알아보았다. 

개념을 익혔다면 문제를 풀며 연습해보아야 한다. 백준을 통해 자신의 개념을 시험해보자!

 

 

https://www.acmicpc.net/step/20

분할 정복 단계