Divide and Conquer(분할 정복)
복잡하거나 큰 문제를 여러 개로 나눠서 푸는 방법.
비슷한 크기로 문제를 분할하고, 해결된 문제를 제외하고 동일한 크기로 문제를 다시 분할한다.
병렬적으로 문제를 해결할 수 있다.
- 단점: 동일한 문제를 다시 푼다. 문제해결함수가 재귀적으로 호출될 수 있으므로 메모리가 추가적으로 사용된다.
!!! 재귀호출과 분할정복의 차이 !!!
- 재귀호출은 같은 함수코드를 재호출하는 것(같은 함수코드 사용)
- 분할정복은 비슷한 작업을 재진행하는 것(같은 함수코드는 아닐 수 있음)
''' 1부터 10까지의 합 구하기 '''
#재귀 함수 사용
def r_func(num):
if num < 1:
return 0
else:
return num + r_func(num-1)
print('재귀함수', r_func(10))
# 분할 정복으로 풀이
def dc_func(num):
if num == 1: # base case
return 1 # Conquer ==> result
if num % 2 == 1: # Divide
return dc_func(num - 1) + num # combine => conquer & merger
else: # Divide
return dc_func(num / 2) * 2 + (num / 2) * (num / 2) # combine => conquer & merger
print('분할 정복', dc_func(10))
'''
재귀함수 55
분할 정복 55.0
'''분할정복의 용어
- Base case: 문제를 분할할 수 없거나, 할 필요없는 경우에 대한 답을 구함(기본 케이스)
- Divide: 본 문제를 서브문제로 분할
- 본 문제를 서브 문제로 분할 할 수 있는가?
- Merge: 서브문제의 답을 구한 경우, 해당 답을 본 문제에 대한 답이 되도록 병합함
- 서브 문제의 답을 병합하여 본문제의 답을 구하는 것이 효율 적인가? (Conquer)
- 개별적으로 Conquer 후 Merge
퀵 정렬 (Quick Sort)
기준 데이터를 설정하고 그기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법.
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘.
퀵소트는 한정적인 범위에서 데이터를 정렬하기 때문에 캐시를 덜 활용하고, 하드웨어적으로 효율적이다
병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
일반적으로 퀵소트의 시간복잡도가 병합정렬보다 크다.(둘 다 nlogn 정도의 시간복잡도를 갖는다.
가장 기본적인 퀵 정렬은 첫번째 데이터를 기준데이터(Pivot)로 설정 함.
분할정복(divide and conquer)을 통해 정렬하고, 피벗이라는 별도의 노드를 지정해두고 재귀적으로 수행을 하기 때문에 더 빠르다.
단점: 악의 경우에 첫번째 노드를 피벗으로 설정하고 불균형하게 분할정복을 시도하여 성능이 안 좋아진다.
- 속도는 알고리즘을 처리하고 결과를 도출하는 속도(주로 소프트웨어에 영향을 주고 받음)
- 성능은 메모리에 영향을 주는 정도(주로 하드웨어에 영향을 주고 받음)
퀵정렬 순서 (수도코드방향)
- 파티션(영역)을 나눈다.
- 정해진 피벗을 중심으로 양옆으로 영역을 나눈다.
- 나눠진 영역을 중심으로 재귀호출을 진행하는 분할정복구조를 갖고 있다.
array = [7, 5, 9, 0, 3, 1, 6, 2, 8, 4]
'''퀵정렬 소스코드'''
def q_sort(array, start, end):
if start >= end: #원소가 1개인 경우 종료됨
return array
pivot = start #피벗은 1번째 원소
left = start + 1 # 2번째 원소가 가장 왼쪽이다 선언
right = end #가장 마지막 원소가 가장 오른쪽이다 선언
while(left <= right): # 왼쪽이 오른쪽보다 작거나 같은 경우 반복 = 피벗보다 큰 데이터를 찾을 때 까지 반복
# 왼쪽과 오른쪽의 진행방향이 교차되는 지점을 찾는 함수
while(left <= end and array[left] <= array[pivot]):
left += 1 # 오른쪽 끝의 수가 왼쪽 끝수보다 작거나 같고 왼쪽 1번째 수(pivot)보다 2번째(left)수가 작거나 같으면 오른쪽으로 하나씩 증가 시킨다.
while(right > start and array[left] >= array[pivot]):
left -= 1 # 가장 마지막 원소가 1번째 원소 보다 크고, 왼쪽 1번째 수(pivot)보다 2번째 수(left)가 크거나 같으면 왼쪽으로 한칸씩 이동
if(left>right): #진행방향이 교차되어 엇갈린다면 작은 데이터와 피벗을 스와핑
array[right], array[pivot] = array[pivot], array[right]
else: # 엇갈리지 않은경우 서로 데이터를 스와핑
array[left], array[right] = array[right], array[left]
#분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 재귀적으로 수행
q_sort(array, start, right-1) #왼쪽 부분
q_sort(array, right+1, end) #오른쪽 부분
q_sort(array, 0, len(array)-1)
''''퀵정렬을 리스트 슬라이싱과 컴프리핸션을 이용해서 만든 소스코드'''
def quick_sort(array):
#리스트가 하나 이하의 원소만을 담고 있다면 종료.
if len(array) <= 1:
return array
pivot = array[0] # pivot 은 array의 첫번째 원소
tail = array[1:] #pivot을 제외한 리스트 슬라이싱
left_side = [x for x in tail if x<=pivot] # 분할된 왼쪽 부분, x는 첫번재 이후 범위에 있는 인자로 피봇보다 작거나 같다
righ_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분, x는 첫번재 이후의 범위에 있는 피봇보다 큰인자
#분할된 왼쪽 부분과 오른쪽 부분에서 각 정렬이 수행되고 전체 리스트 반환 시키기
return quick_sort(left_side) + [pivot] + quick_sort(righ_side)
print(quick_sort(array))
퀵 정렬의 시간 복잡도
Avg O(NlogN)
Worst O(n^2)
- 평균의 경우 O(nlogn)
- 최악의 경우(한쪽 방향으로 편향된 정렬이 이루어질 경우) O(n^2)의 시간 복잡도를 가진다.
퀵정렬이 빠른이유
직관적이 이해
이상적인 경우 분할이 절반씩 일어난다면 전체 연산 횟수로 O(nlogn)을 기대할 수 있다.
너비x높이 = n x logn = nlogn
병합 정렬(Merge Sort)
병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘
병합정렬은 분할과 교체를 반복한다.
일단 시간을 들여서 1개의 서브리스트가 나올때까지 분할을 진행한다.
- 배열값을 반복문을 통해 비교->정렬->교환 후 합치는 과정을 연속적으로 진행한다.
''' 병합정렬 소스코드'''
def mergesort(arr):
if len(arr) > 1: # array가 유효한 경우 (1보다 큰경우)
mid = len(arr)//2 # 전체array 길이의 중간을 지정
left = arr[:mid] # 왼쪽은 처음부터 중간지점 인덱스전까지
right = arr[mid:] # 오른쪽은 중간지점 인덱스 부터 끝까지지
mergesort(left) # 왼쪽 부분을 재귀적으로 값을 분할정복 하여 함수 호출하여 병합 정렬
mergesort(right) # 오른쪽쪽 부분을 재귀적으로 값을 분할정복 하여 함수 호출하여 병합 정렬
i = j = k = 0 # 인덱스 인자 초기화
# Merge 정렬 - 배열의 인덱스를 참조하여 비교->정렬->교환
while i < len(left) and j < len(right): # 인덱스의 숫자가 왼쪽과 오른쪽의 길이보다 작은 경우 반복복
if left[i] < right[j]: # 오른쪽값 > 왼쪽값
arr[k] = left[i] # 왼쪽값을 결과값에 저장장
i+=1 # 왼쪽배열값의 인덱스를 +1 증가시키고, 결과를 위한 배열에 저장
else: # 오른쪽값 < 왼쪽값
arr[k] = right[j] # 오른쪽값을 결과 값에 저장장
j+=1 # 오른쪽 배열값값의 인덱스를 +1 증가시키고, 결과를 위한 배열에 저장
k+=1 # 다음으로 진행하기위해 배열의 인덱스 +1증가 시키고 저장
# 중간 확인 (필수 아님, 공부위함함)
print('배열의 오른쪽',right)
print('배열의 왼쪽', left)
'''
배열의 오른쪽 [3]
배열의 왼쪽 [7]
배열의 오른쪽 [16]
배열의 왼쪽 [2]
배열의 오른쪽 [2, 16]
배열의 왼쪽 [3, 3]
배열의 오른쪽 [2, 16]
배열의 왼쪽 [3, 3]
배열의 오른쪽 [2, 16]
배열의 왼쪽 [3, 3]
배열의 오른쪽 [4]
배열의 왼쪽 [24]
배열의 오른쪽 [9]
배열의 왼쪽 [11]
배열의 오른쪽 [9, 9]
배열의 왼쪽 [4, 4]
배열의 오른쪽 [9, 9]
배열의 왼쪽 [4, 4]
배열의 오른쪽 [4, 4, 11, 9]
배열의 왼쪽 [2, 3, 3, 16]
배열의 오른쪽 [4, 4, 11, 9]
배열의 왼쪽 [2, 3, 3, 16]
배열의 오른쪽 [4, 4, 11, 9]
배열의 왼쪽 [2, 3, 3, 16]
배열의 오른쪽 [4, 4, 11, 9]
배열의 왼쪽 [2, 3, 3, 16]
배열의 오른쪽 [4, 4, 11, 9]
배열의 왼쪽 [2, 3, 3, 16]
배열의 오른쪽 [4, 4, 11, 9]
배열의 왼쪽 [2, 3, 3, 16]
배열의 오른쪽 [4, 4, 11, 9]
배열의 왼쪽 [2, 3, 3, 16]
'''
# 왼쪽 확인
while i < len(left): # 왼쪽의 길이가 i보다 클경우 = 왼쪽 끝나지 않음음
arr[k] = left[i] # 정렬된 왼쪽 값을 array에 저장한다
i+=1 # 왼쪽 인덱스 +1 해준다음 저장
k+=1 # array 인덱스 +1 해준다음 저장
# 오른쪽 확인
while j < len(right): # 오른쪽 길이가 j보다 클경우 = 오른쪽 안끝남
arr[k]= right[j] # 정렬된 오른쪽 값을 array에 저장한다
j+=1 # 왼쪽 인덱스 +1 해준다음 저장
k+=1 # array 인덱스 +1 해준다음 저장
# 정렬된 결과 출력 함수
def printlist(arr):
for i in range(len(arr)): # array 길이의 범위안에 있는 i 인자를
print(arr[i], end=' ') # 구분은 ' ' 로 array의 각 인자들을 출력
print ()
# test
arr = [7,3,2,16,24,4,11,9]
print ("정렬되기 전 테스트 배열", end ="\n")
printlist(arr)
'''
정렬되기 전 테스트 배열
7 3 2 16 24 4 11 9
'''
# 병합정렬 알고리즘을 적용하기 위해 처음으로 병합정렬 함수를 호출한다.
mergesort(arr)
print("병합정렬로 정렬된 결과 배열: ", end ="\n")
printlist(arr)
'''
병합정렬로 정렬된 결과 배열:
2 3 7 16 4 24 9 11
'''병합정렬의 시간복잡도
O(nlogn)
- 병합정렬은 divide and conquer 로직으로 인해, 전체 데이터를 기준으로 처음과 끝을 계속해서 탐색하기 때문에 퀵소트에 비해 느리다.
- 병합정렬이 활용되는 이유는 퀵소트보다 빠르지는 않지만, 안정(stable) 정렬이기 때문에 데이터가 중복되었더라도 영향을 덜 받는다
