문제의 크기가 너무나 커서 접근하기 어려울 때, 우리는 그 문제의 크기를 줄여나가면서 해결책을 찾아보기도 한다.
예를들어 크기가 100인 문제가 있으면 이를 각각 50의 크기로 쪼개 부분문제를 만들어 이를 각각 해결하고,
해결한 문제의 답을 합쳐서 100의 크기의 문제를 해결하는 식이다.
이 알고리즘은 총 3종류의 단계가 있다.
- Divide
- Conquer
- Combine
- Divide 단계는 문제의 크기를 나누는 과정으로 문제의 크기를 계속 줄여준다는 점에서 recursive case로 표현된다
- Conquer 단계는 문제의 크기가 충분히 작아 답을 찾을 수 있는 단계라는 점에서 base case로 표현 가능하다.
그런데... 이게 말처럼 쉽지는 않다.
conquer를 하는 과정에서 문제 크기가 예상외로 충분히 작지 않아 이를 또 divide 해야할 때,,, 또 해야할 때,,, 이렇게 계속 진행하다보면 가지치듯이 나누어지는 분기점의 수가 늘어난다.
따라서 이 분기점을 얼마나 잘 해결하느냐에 따라 문제 해결을 할 수 있냐 없냐가 달라진다.
예시 1 - 1부터 n까지의 합
예를들어 1부터 100까지의 합을 구한다고 해보자. 컴퓨터는 암산하지 않지만 우리는 암산을 할 수 있는 크기를 충분히 작은 문제의 크기라고 할 때 divide를 암산이 가능한 범위까지 진행해야 한다.
def consecutive_sum(start, end):
container = [x for x in range(start, end+1)]
midIdx = len(container) // 2
if len(container) == 1:
return container[0]
return consecutive_sum(container[0], container[midIdx-1]) + consecutive_sum(container[midIdx], container[len(container)-1])컴퓨터는 바보여서 암산을 한 번에 한 숫자만 할 수 있다고 했을때 if문이 base case이고, 그보다 큰 경우에는
아래의 return문으로 재귀적으로 값을 계속 나누어주어야 한다.
예시 2 - 합병 정렬
합병 정렬 (Merge Sort)는 divide and conquer의 가장 근본되는 정렬 방식으로 정렬하기 쉬운 크기의 문제가 나올때 까지 문제의 크기를 계속 줄여나간다.
합병 정렬이란, 리스트의 크기를 계속 절반으로 줄여나간다.
- 나누어진 리스트의 길이가 1이다
- 그 리스트의 수가 2개이다
이 경우에 도달할 때 까지 계속해서 리스트를 divide 해 나간다.
이후에 combine을 위해 나누어진 리스트들을 정렬 후 계속 합병(merge)해 나간다.
합병을 하면서 나누어진 두 리스트의 값들을 오름차순으로 정리해 나간다.
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:]다음과 같이 남은 리스트를 붙여준다. 이때 각 리스트들은 combine 과정에서 정렬된 상태이기에 그대로 더해주면 된다.
midIdx = len(my_list) // 2
list1 = my_list[:midIdx]
list2 = my_list[midIdx:]위 코드는 리스트를 divide 해주는 코드이다.
리스트의 크기를 절반씩 줄여나가면서 문제의 크기를 줄여나간다.
이때 크기가 conquer할 수 있을 정도로 충분히 작아졌을 때
if len(my_list) == 2:
return merge(my_list[:1], my_list[1:])
elif len(my_list) == 1:
return my_list리스트를 merge한다.
위의 코드를 총 정리하면 아래 코드와 같이 merge sort 알고리즘이 완성된다.
def merge(list1, list2):
i = 0
j = 0
# 정렬된 항목들을 담을 리스트
merged_list = []
# list1과 list2를 돌면서 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
# list2에 남은 항목이 있으면 정렬 리스트에 추가
if i == len(list1):
merged_list += list2[j:]
# list1에 남은 항목이 있으면 정렬 리스트에 추가
elif j == len(list2):
merged_list += list1[i:]
return merged_list
# 합병 정렬
def merge_sort(my_list):
if len(my_list) == 2:
return merge(my_list[:1], my_list[1:])
elif len(my_list) == 1:
return my_list
midIdx = len(my_list) // 2
list1 = my_list[:midIdx]
list2 = my_list[midIdx:]
return merge(merge_sort(list1), merge_sort(list2))
예시 2 - 퀵 정렬
앞의 예시에서 합병 정렬을 살펴보았다.
divide and conquer 방식에서 합병 정렬은 divide와 conquer과정은 상대적으로 무난했으나 combine과정이 매우 복잡했다. (우리는 이를 merge 함수를 따로 선언해 구현했다)
그런데 퀵 정렬은 합병 정렬과 달리 combine 과정이 없다. 진짜 없냐? 없다. 진짜.
대신에 문제의 크기를 줄여나가는 divide 과정이 매우 복잡하다.
코드를 살펴보기에 앞서 대략적인 개념을 살펴보자.
퀵 정렬이란 pivot을 가지고 partitioning을 하며 정렬을 해 나가는 것이라 할 수 있다.
이에 총 4개의 지표가 사용되고 아래와 같다
- pivot index : partitioning의 기준이 되는 index. 보통 -1번 인덱스
- start index : small group의 시작 지표. 보통 0번 인덱스
- big index : big group의 시작 지표.
- i index : Unknown group의 시작 지표.
초기에 리스트의 -1번 인덱스를 pivot 인덱스로 지정한다.
그리고 start, i 그리고 b 인덱스를 0번 인덱스로 세팅해준다.
우리의 목표는 Unknown group의 값들을 각각 small group과 big group으로 분류해주는 것인데 이를 위해서 i 인덱스를 옮겨가며 살펴보아야 한다.
- pivot보다 i 값이 클 때 : b는 그대로, i는 하나 증가. b인덱스가 big group 지표이기에 pivot보다 크면 big group에 속해야 하기 때문.
- pivot보다 i 값이 작을 때 : b와 i의 값을 교환해준다. pivot보다 값이 작기 때문에 더이상 big group에 들어있을 수 없다. 따라서 big group의 값과 i의 값을 교환해 start 지표의 그룹으로 넣어준다. 그 후에 b와 i 둘 다 하나 증가.
- pivot index와 i index가 같을 때 : i의 값과 b의 값을 교환 (pivot index와 big group의 0번 인덱스 값을 교환)후 b의 값 하나 증가 (pivot을 구분해주기 위해.)
이 과정을 거치면 small group과 big group으로 문제가 나누어져서 문제의 크기가 줄어든다.
이 divide 과정이 끝난 후에 conquer을 위해 재귀적으로 위 과정을 반복해주면 된다.
먼저 퀵 정렬 알고리즘에서 값을 교환하는 과정이 많이 일어나기 때문에 따로 함수로 빼주었다.
def swap_elements(my_list, index1, index2):
my_list[index1], my_list[index2] = my_list[index2], my_list[index1](다른 언어와 달리 파이썬은 temporal 변수를 사용하지 않아도 돼서 값 교환이 편한 것 같다.)
divide 부분을 구현하면 다음과 같다.
def partition(my_list, start, end):
# 리스트 값 확인과 기준점 이하 값들의 위치 확인을 위한 변수 정의
i = start
b = 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
# pivot의 최종 인덱스를 리턴해 준다
return p
그리고 conquer 과정을 위해 위 과정을 재귀적으로 반복하게 해 줄 퀵 정렬 함수를 구현한다.
시작할 때 봤듯이 start 지표와 end 지표는 범위를 나누어주는 인덱스라 하였으므로 이를 이용해서 문제의 크기를 줄여나가면서 정복해주면된다.
이때 pivot 값 기준 좌 우 측의 리스트 길이가 1일 경우가 base case인 점을 고려하면,
end - start < 1 인 경우에는 combine을 해주면 되는 것인데, 퀵 정렬에서는 combine과정이 없으므로 그냥 return을 해주면 된다.
근데 길이가 1이면 end - start == 0 이면 되는거 아닌가?
아니다! 예를 들어서
list_ = [2, 3, 4, 1], start = 0, end = 3인 경우를 생각해보자.
partition(list_, start, end)는 pivot index로 0을 리턴하기 때문에
재귀적으로 conquer하는 과정에서 start, pivot -1 의 경우 -1을 리턴하기 때문에 무한 재귀 루프에 빠지게 된다.
if end - start < 1:
return
def quicksort(my_list, start, end):
if end - start < 1:
return
p = partition(my_list, start, end)
# small group partition
quicksort(my_list, start, p-1)
# big group partition
quicksort(my_list, p+1, end)
그런데 우리가 정렬을 할 때 시작인덱스와 끝 인덱스를 굳이 지정해줘서 쓰지 않지 않나?
이를 위해 위 코드를 조금만 더 손봐주면,
def quicksort(my_list, start = 0 , end = None):
if end == None:
end = len(my_list) - 1
if end - start < 1:
return
p = partition(my_list, start, end)
quicksort(my_list, start, p-1)
quicksort(my_list, p+1, end)옵셔널 파라미터를 이용해서 사용자가 처음 함수에 접근했을 때 인덱스를 따로 입력하지 않아도 되고, 재귀적으로 conquer을 할때는 따로 quicksort 함수가 인덱스를 자동으로 넣었을 때 갱신할 수 있도록 만들었다.
2021-10-17
'알고리즘 > 개념' 카테고리의 다른 글
| 메...모...정..리.. (0) | 2022.06.20 |
|---|---|
| Dynamic programming (1) | 2021.10.24 |
| BruteForce 알고리즘 (0) | 2021.10.16 |
| 정렬 알고리즘 (0) | 2021.10.16 |
| 탐색 알고리즘 (0) | 2021.10.16 |