분할정복을 정복하자...
분할 정복
2.1 Binary search
이분 검색
- 분할 정복(Divide-and-Conquer)
- 으로 원소를 찾아보자
😎
- [Divide] 정가운데 원소를 기준으로 S를 두 개의 리스트로 분할
- [Conquer] x가 정가운데 원소보다 크면 오른쪽, 작으면 왼쪽을 재귀 호출
- [Obtain] 선택한 리스트에서 얻은 답을 리턴
Binary search
def location (S, low, high):
if (low > high):
return 0
else:
mid = (low + high) // 2
if (x == S[mid]):
return mid
elif (x < S[mid]):
return location(S, low, mid - 1)
else:
return location(S, mid + 1, high)
2.2 Merge sort
def location (S, low, high):
if (low > high):
return 0
else:
mid = (low + high) // 2
if (x == S[mid]):
return mid
elif (x < S[mid]):
return location(S, low, mid - 1)
else:
return location(S, mid + 1, high)
merge sort도 Divide and Conquer로 풀어보쟈 😎
- [Divide] 원소가 n개인 S를 n/2개의 원소를 가진 두 개의 리스트로 분할
- [Conquer] 왼쪽의 리스트와 오른쪽의 리스트를 각각 재귀적으로 합병 정렬
- [Combine] 각각 정렬된 두 개의 리스트를 정렬된 하나의 리스트로 합병하여 리턴
Merge sort
def mergesort (S):
n = len(S)
if (n <= 1):
return S
else:
mid = n // 2
U = mergesort(S[0 : mid])
V = mergesort(S[mid : n])
return merge(U, V)
Merge
def merge(U, V):
S = []
i = j = 0
while (i < len(U) and j < len(V)):
if (U[i] < V[j]):
S.append(U[i])
i += 1
else:
S.append(V[j])
j += 1
if (i < len(U)):
S += U[i : len(U)]
else:
S += V[j : len(V)]
return S
위 소스코드는 정렬은 됨 하지만 입력리스트인 S 외에 리스트 U 와 V 두개나 더 사용해야 한다.
- 추가적으로 만들어지는 리스트 원소의 총 수
- merge sort()호출할 때 마다 U랑 V를 새로 생성한다.
- 전체 재귀 호출 시 원소의 개수 = n + n/2 + n/4 … = 2n
따라서 메모리 사용에 비효율성이 있음,, 이거 어떻게 개선할까?
리스트 더 쓰지 말고 안에서 정렬해보자
Merge sort 2
def mergesort2 (S, low, high):
if (low < high):
mid = (low + high) // 2
mergesort2(S, low, mid)
mergesort2(S, mid + 1, high)
merge2(S, low, mid, high)
Merge 2
def merge2 (S, low, mid, high):
U = []
i = low
j = mid + 1
while (i <= mid and j <= high):
if (S[i] < S[j]):
U.append(S[i])
i += 1
else:
U.append(S[j])
j += 1
if (i <= mid):
U += S[i : mid + 1]
else:
U += S[j : high + 1]
for k in range(low, high + 1):
S[k] = U[k - low]
2.3 분할정복 설계 방법
분할정복 설계 전략
- 분할:문제의 입력사례를 둘 이상의 작은 입력사례로 분할
- 정복:작은 입력사례들을 각각 정복, 작은 입력사례들이 충분히 작지 않으면 재귀 호출
- 통합:필요하면, 작은 입력사례의 해답을 통합하여 원래 입력사례의 해답을 도출
분할정복 알고리즘
- 분할정복 vs 동적계획
Top-Down vs Bottom-Up - 분할정복 vs 탐욕법
탐욕법은 가장 비효율적인 분할정복 알고리즘?
ex. 교환정렬(greedy)->맨앞 원소와 나머지를 divide했다고 봐도 됨
2.4 퀵 정렬(분활 교환 정렬)
퀵 정렬:Divide-and-Conquer
- 내부(in-place)정렬:추가적인 리스트를 사용하지 않아도 됨
- Quick-Sort
- [Divide]기준 원소(pivot)를 정해서 기준원소를 기준으로 좌우로 분할
- [Conquer]왼쪽의 리스트와 오른쪽의 리스트를 각각 재귀적으로 퀵 정렬
- [Obtain]정렬된 리스트를 리턴
Quick sort
def quicksort (S, low, high):
if (high > low):
pivotpoint = partition(S, low, high)
quicksort(S, low, pivotpoint - 1)
quicksort(S, pivotpoint + 1, high)
여기서 문제, 어떻게 partition할 것인가??
pivot 정하기
- 편의상 일단 리스트의 첫 원소를 기준원소로 정하자
15를 기준으로 작으면 왼쪽, 크면 오른쪽으로 분할
계속 첫번째 원소를 기준으로 배열을 분할한다
기준 원소로 어떻게 리스트를 나눌까
- 두개의 인덱스 i, j를 이용하서 compare and swap
Partition (for Quick Sort)
def partition (S, low, high):
pivotitem = S[low]
j = low
for i in range(low + 1, high + 1):
if (S[i] < pivotitem):
j += 1;
S[i], S[j] = S[j], S[i] # swap
pivotpoint = j
S[low], S[pivotpoint] = S[pivotpoint], S[low] # swap
return pivotpoint
partition()함수를 다르게 구현해볼 수 없을까~~
partition()함수의 다른 구현 방법
S = [26, 5, 37, 1, 61, 11, 59, 15, 48, 19]
[26, 5, 37, 1, 61, 11, 59, 15, 48, 19]: 2, 9
[26, 5, 19, 1, 61, 11, 59, 15, 48, 37]: 4, 7
[26, 5, 19, 1, 15, 11, 59, 61, 48, 37]: 6, 5
[11, 5, 19, 1, 15, 26, 59, 61, 48, 37]
앞 뒤에서 맨 앞 원소인 pivotpoint보다 큰지/작은지 한꺼번에 비교하자
끝난 후 중간에 있는 원소를 pivotpoint로 바꿈
partition2
def partition2 (S, low, high):
pivotitem = S[low]
i = low + 1
j = high
while (i <= j):
while (S[i] < pivotitem):
i += 1
while (S[j] > pivotitem):
j -= 1
if (i < j):
S[i], S[j] = S[j], S[i] # swap
pivotpoint = j
S[low], S[pivotpoint] = S[pivotpoint], S[low] # swap
return pivotpoint
i로 왼쪽부터 pivot item보다 큰 원소가 나올 때 까지 전진
j로 오른쪽부터 pivot item보다 작은 원소가 나올 때 까지 전진
만약 j가 i보다 오른쪽에 있다면 둘을 swap
(왜냐하면 오른쪽에 작은값 왼쪽에 큰 값 둘거니까)
quicksort 2
def quicksort2 (S, low, high):
if (high > low):
pivotpoint = partition2(S, low, high)
quicksort2(S, low, pivotpoint - 1)
quicksort2(S, pivotpoint + 1, high)
Author And Source
이 문제에 관하여(분할정복을 정복하자...), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@yooniverseis/분할정복을-정복하자저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)