230831 분할 검색

생성 일시: 2023년 8월 30일 오후 3:34

• 분할 정복
• 이진 검색
• 병합 정렬
• 퀵 정렬

분할 정복

---

분할 정복 기법

유래

• 1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략
• 전력이 우세한 연합군을 공격하기 위해 나폴레옹은 연합군의 중앙부로 쳐들어가 연합군을 둘로 나눔
• 둘로 나뉜 연합군을 한 부분씩 격파함

설계 전략

• 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다
• 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다
• 통합 (Combine) : (필요하다면) 해결된 해답을 모은다

Top-down approach

반복 (Iterative) 알고리즘 $O(n)$

Interative_Power(x, n)
	result = 1

	FOR i in 1 -> n
	result = result * x

	RETURN result

분할 정복 기반의 알고리즘 $O(logn)$

• $C^n$을 구하기 위해서는?

  Recursive_Power(x, n)
  	IF n == 1 : RETURN x;
  	IF n is even
  		y = Recursive_Power(x, n/2)
  		RETURN y*y
  	ELSE
  		y = Recursive_Power(X, (n-1)/2)
  		RETURN y * y * x
  

병합 정렬

---

• 여러 개의 정렬된 자료의 집합을 병합하여 한 개의 정렬된 집합으로 만드는 방식
• 분할 정복 알고리즘 활용
  • 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 얻어냄
  • top-down 방식
  • 안정 정렬
• 시간 복잡도 $O(nlogn)$

병합 정렬 과정

• {69, 10, 30, 2, 16, 8, 31, 22} 를 병합 정렬하는 과정
• 분할 단계: 전체 자료 집합에 대하여, 최소 크기의 부분집합이 될 때까지 분할 작업을 계속한다

• 병합 단계: 2개의 부분 집합을 정렬하면서 하나의 집합으로 병합
• 8개의 부분집합이 1개로 병합될 때까지 반복함

알고리즘: 분할 과정

mergeSort(arr[], left, right) {
	IF left < right:
		mid = (left+right) / 2
		mergeSort(arr, left, mid)
		mergeSort(arr, mid+1, right)
		merge(arr, left, mid, right)

알고리즘: 병합 과정

merge(arr[], left, mid, right) {
	L = left
	R = mid+1
	idx = left
	while L <= mid && R <= right {
		if arr[L] <= arr[R]
			sortedArr[idx++] = arr[L++]
		else
			sortedArr[idx++] = arr[R++]
	}
	if L <= mid {
		for i in L to mid
			sortedArr[idx++] = arr[i]
	} else {
		for j in R to right
			sortedArr[idx++] = arr[j]
	}
	for i in left to right
		arr[i] = sortedArr[i]