분할정복

알고리즘 설계 기법의 종류

1. 전체를 그냥 다 보자. (Brute Force - 완전 탐색)
   • 배열 : for 문, while 문
   • 그래프 ( 관계가 있는 데이터)
     • DFS, BFS
2. 상황마다 좋은 것을 고르자 : Greedy
   • 규칙 + 증명 → 구현
3. 큰 문제를 작은 문제로 나누어 부분적으로 해결하자(Dynamic Programming)
   • 분할 정복과 다르게 작은 문제가 중복
   • 중복된 문제의 해답을 저장해놓고 활용하자 (Memoization)
4. 큰 문제를 작은 문제로 나누어 부분적으로 해결하자 (분할 정복)
5. 정체 중 가능성 없는 것을 빼자 (Backtracking - 백트래킹)

→ 이 기본들을 기반으로 더 고급 알고리즘들이 개발됨

 

분할 정복

대표적으로 병합 정렬, 퀵 정렬 + 이진 검색

만약 n개의 동전 중에 1개의 가짜 동전 있고, 진짜 동전에 비교해 아주 조금 가볍다. 양팔저울을 최소로 사용해서 찾는 방법은?

유래는 나폴레옹의 전략, 중앙에 들어가서 양 끝으로 격파해나감

전략

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

하나라도 틀리면 전체 결과가 잘못 나옴

재귀함수로 많이 구현한다.

Top-down approach

 

예시) $C^n$을 구하는 방법

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

iterative_power(x,n)
		result <- 1 
	
		for i in 1 ->n
				result <- result * x
		return result
	

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

짝수와 홀수로 나누어서 계산해 나감

$C^8 = ((C^2)^2)^2$

짝수 일 때 $C^n = C^{n/2} * C^{n/2}$ = $C^n$

홀수 일 때 $C^n = C^{(n-1)/2} * C^{(n-1)/2} * C$ = $C^n$

Recursive_Power(x,n)
	if n == 1: return x
	if n is even
		y <- recursive_poser(x,n/2)
			return y * y
	else:
		y <- recursive_power(x,(n-1)/2)
			return y * y * x

병합 정렬 Merge Sort

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

알고리즘

분할 과정

merge_sort(list m)
	if length(m) == 1: return m
	
	list left, right
	middle <- length(m) /2
	for x in m before middle
		add x to left
	for x in m after or equal middle
		add x to right
	
	left <- merge_sort(left)
	right <- merge_sort(right)
	
	return merge(left, right)

병합 과정

merge(List left, List right)
	List result
	
	while length(left) > 0  OR length(right) > 0
		if length(left) > 0 AND length(right) > 0
			if first(left) <= first(right)
				append popfirst(left) to result
			else
				append popfirst(right) to result 
		elif length(left) > 0
			append popfirst(left) to result
		elif length(right) > 0
			append popfirst(right) to result
	return result

• 파이썬 코드

def merge_sort(a):
    # 문제를 절반으로 나누어서 각각을 해결
    if len(a) == 1: # 길이가 1일때 리턴
        return a
    else: # 길이가 1 보다 클 때재귀호출하는 부분
        mid = len(a) // 2
        left = a[:mid]
        right = a[mid:]

        left = merge_sort(left)
        right = merge_sort(right)

        return merge(left, right)

def merge(left,right):
    # 두 개의 정렬된 부분집합을 정렬하여 하나의 집합으로 리턴
    result = []

    # 병합과정
    # 각각의 최소값들(가장 앞쪽값)을 비교해서 더 작은 요소를 결과에 추가
    # 두 부분집합에 요소가 없어질 때까지 반복
    while left or right:
        if left and right: # 양 쪽이 둘 다 남아 있을 때
            if left[0] <= right[0]:
                result.append(left.pop(0))
            else:
                result.append(right.pop(0))
        elif left: # 왼쪽만 남아 있으면
            result.append(left.pop(0))
        elif right:
            result.append(right.pop(0))
    return result

퀵 정렬

주어진 배열을 두 개로 분할하고, 각각을 정렬한다.

병합 정렬과 동일? X

• 다른 점 1 : 병합 정렬은 그냥 두 부분으로 나누는 반면에, 퀵 정렬은 분할할 때, 기존 아이템(pivot item) 중심으로 분할한다.
• 기준보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다.
• 다른 점 2 : 각 부분 정렬이 끝난 후, 병합정렬은 ‘병합’이란 후처리 작업이 필요하나, 퀵 정렬은 필요로 하지 않는다.

퀵 정렬의 가장 최악의 배열상태 : $O(n^2)$, (=기존 리스트가 역순으로 정렬되있는 경우)

Hoare-Partition (호어 파티션) 알고리즘

partition(A[], L , r)
    p <- A[L] // p : 피봇 값
    i <- L, j <- r
    while i <= j
            while i <= j and A[i] <= p : i ++ # 피봇보다 큰 값이 나올때까지 i를 더해감
            while i <= j and A[j] >= p : j -- # 피봇보다 작은 값이 나올때까지 j를 뺴감
            if i < j : swap(A[i], A[j])

    swap(A[L], A[j]) # 피봇과 i ==j 인 부분을 교환
    return j

 

파이썬 코드

'''
3 2 4 6 9 1 8 7 5
'''
def partition(a,l,r):
    p = a[l]
    i,j = l, r
    while i <= j:
        while i <= j and a[i] <= p: i += 1
        while i <= j and a[j] >= p: j -= 1
        if i < j:
            a[i],a[j] = a[j],a[i]
    a[l], a[j] = a[j], a[l]
    return j

def quick_sort(a,l,r):
    if l < r:
        pivot = partition(a,l,r)
        quick_sort(a,l,pivot-1)
        quick_sort(a,pivot+1,r)

arr = list(map(int,input().split()))
quick_sort(arr,0,len(arr)-1)
print(arr)

Lomuto partition (로무토 파티션) 알고리즘 : 호어 파티션보다 안좋다.

partition(A[], p, r)
		x <- A[r] # 피봇 고르기
		i <- p -1 
		for j in p -> r-1 
				if A[j] <= x
						i ++, swap(A[i], A[j]) # 값이 피봇보다 작다면? i,j 둘다 증가, 
 																	 #		           크다면? j 만 증가됨
		swap(A[i+1], A[r])
		return i + 1

풀이

arr = [3 2 4 6 9 1 8 7 5] 피벗 : 5 고 i = 0 j = 1 일 때 arr [1] ==> 2 2 < 5 ==> 조건 만족하면서 i ++ 되서 i,j 둘 다 1이 되서 스왑에 의미가 없음 하지만 i = 2 일 때

j는 3,4,5번째 항까지 올라가서 if를 만족하게 됨

⇒ i = 3 과 j =5의 값을 교환하게 됨

이진 검색

• 정렬된 데이터를 기준으로 특정 값이나 범위를 검색하는데 사용 $O(logn)$
• 이진 검색을 활용한 심화 학습 키워드 : Lower Bound, Upper Bound
  • 정렬된 배열에서 특정 값 이상 또는 이하가 처음으로 나타나는 위치를 찾는 알고리즘
  • 특정 데이터의 범위 검색 등에서 활용

# 이진 탐색
arr = [324,32,22134,16,48,93,922,316]

# 1. 정렬된 상태의 데이터
arr.sort()

# 2. 이진 검색 - 반복문 버젼
def binarySearch(target):
    # 제일 왼쪽, 오른쪽 인덱스 구하기
    low = 0
    high = len(arr) -1

    # 탐색 횟수
    cnt = 0
    # 해당 숫자를 찾으면 종료
    # 더이상 쪼갤 수 없을 때까지 반복
    while low <= high:
        mid = (low + high) //2
        cnt += 1
        # 가운데 숫자가 정답이면 종료
        if arr[mid] == target:
            return mid, cnt
        elif arr[mid] > target:
            high = mid - 1
        elif arr[mid] < target:
            low = mid + 1
    # 못 찾으면 -1 반환
    return -1, cnt

# 3. 이진 검색 - 재귀 함수 버젼
def binarySearch2(low,high, target):
    # 기저 조건
    if low > high:
        return -1
    # 다음 재귀전에 뭘 해야되는가
    # 정답 판별
    mid = (low + high) // 2
    if target == arr[mid]:
        return mid

    # 다음 재귀 함수 호출(파라미터로 뭘 넘길것인가)
    if target < arr[mid]:
        return binarySearch2(low, mid-1, target)
    else:
        return binarySearch2(mid + 1, high, target)
    # 재귀함수에서 돌아왔을 때 어떤 작업을 해야될까
        # 이진 검색에서는 없음

정리

병합 정렬

• 외부 정렬의 기본이 되는 정렬 알고리즘이다.
• 멀티코어(Multi-Core) CPU 나 다수의 프로세서에서 정렬 알고리즘을 병렬화하기 위해 병합 정렬 알고리즘이 활용된다.

퀵 정렬

• 매우 큰 입력 데이터에 대해서 좋은 성능을 보이는 알고리즘이다.