1. 분할과 정복

분할과 정복의 문제해결 과정
1) 문제를 작은 문제로 나눈다
2) 작은 문제들의 해를 재귀적으로 구한다
3) 작은 문제들의 해를 이용해 문제의 해를 구한다

1-1. 배열에서 최대값 찾기

def getMax(A, first, last):
    if first == last:
        return A[first]
    else:
        mid = (first + last) // 2
        lmax = getMax(A, first, mid)
        rmax = getMax(A, mid+1, last)
        return max(lmax, rmax)

시간복잡도 :

T(n) = 1           if n = 1
     = 2T(n/2) + 4 if n > 1
     
T(n) = 2T(n/2) + 4
     = 2[2T(n/2^2) + 4] + 4
     = 2^2[2T(n/2^3) + 4] + 8 + 4
     = 2^k(T(n/2^k) + (2^k - 1) * 4
     n/2^k = 1 일때
     = n(T(1)) + (n - 1) * 4
     = n + 4n -4
     : O(n)

1-2. 이진탐색 - 원소의 위치

def getIndex(A, left, right, item):
    if left > right:    # 원소 없음
        return -1
    
    else:
        mid = (left+right) // 2
        if A[mid] == item:
            return mid
        elif item > A[mid]:
            return getIndex(A, mid+1, right, item)
        else:
            return getIndex(A, left, mid-1, item)

시간복잡도 :

T(n) = 1            if n = 1
     <= T(n/2) + 1  if n > 1
     <= T(n/2^k) + k
     n/2^k = 1 일때
     = T(1) + log n
     : O(log n)

---

2. 점화식의 시간복잡도 계산

ex1)

f(n) = a            if n = 1
     = f(n-1) + bn  if n > 1
     
f(n) = f(n-1) + bn
     = [f(n-2) + b(n-1)] + bn = f(n-2) + b(n-1) + bn
     = [f(n-3) + b(n-2)] + b(n-1) + bn = f(n-3) + b(n-2) + b(n-1) + bn
     = f(n-k) + b[(n-(k-1)) + ... + (n-2) + (n-1) + n]
     = f(n-k) + b(n-k+1 + n)k/2
     n-k = 1일때
     = f(1) + b(1+1 + n)(n-1)/2
     = a + b(n+2)(n-1)/2
     : O(n^2)

ex2)

f(n) = a            if n = 1
     = 2f(n/2) + b  if n > 1
     
f(n) = 2f(n/2) + b
     = 2[2f(n/2^2) + b] + b = (2^2)f(n/2^2) + 2b + b
     = (2^k)f(n/2^k) + b(2^k - 1)
     n/2^k = 1일때
     = nf(1) + b(n-1)
     : O(n)

ex3)

f(n) = a               if n = 1
     <= 2f(n/2) + bn   if n > 1
     
f(n) <= 2f(n/2) + bn
     <= 2[2f(n/2^2) + b(n/2)] + bn = (2^2)f(n/2^2) + 2bn
     <= (2^k)f(n/2^k) + kbn
     n/2^k = 1일때
     <= nf(1) + logn * b * n
     : O(n log n)

⚠️ 수열의 합

---

3. 분할과 정복을 이용한 정렬

3-1. 병합 정렬

단계
1) n 크기 배열 A를 크기가 n/2인 두 배열로 나눈다
2) 크기가 n/2인 배열들을 재귀적으로 정렬한다
3) 정렬된 두 부분을 하나로 병합한다

def mergeSort(A):
    def sort(left, right):
        if (right - left < 2):
            return
        mid = (left+right) // 2
        sort(left, mid)
        sort(mid, right)
        merge(left, mid, right)
  
    def merge(left, mid, right):
        i = left
        j = mid
        tmp = []
    
        # 왼쪽 리스트와 오른쪽 리스트 원소 비교 후 복사
        while (i < mid and j < right):
            if A[i] <= A[j]:
                tmp.append(A[i])
                i += 1
            else:
                tmp.append(A[j])
                j += 1
    
        # 남은 원소 복사
        while (i < mid):
            tmp.append(A[i])
            i += 1
        
        while (j < right):
            tmp.append(A[j])
            j += 1
            
        for i in range(left, right):
            A[i] = tmp[i-left]
            
    return sort(0, len(A))

시간복잡도 :

T(n) = 0             if n = 1
     <= 2T(n/2) + n  if n > 1
     
T(n) <= 2T(n/2) + n
     <= 2[2T(n/2^2) + n/2] + n
     <= (2^k)T(n/2^k) + kn
     n/2^k = 1 일때
     <= nT(1) + log n * n 
     <= n + n log n
     : O(n log n)

• 병합정렬의 단점
  i) merge 시 O(n) 추가 메모리가 필요하다
  ii) 재귀 때문에 O(log n) 스택 메모리가 필요하다

3-2. 퀵 정렬

단계
1) 배열 A에서 pivot을 선택한다
2) 배열 A를 pivot보다 같거나 작은 원소의 배열, pivot보다 큰 원소의 배열로 나눈다
3) 분할된 두 리스트를 재귀적으로 정렬한다

def quickSort(A, left, right):
    if left < right:
        pivotPoint = partition(A, left, right)
        quickSort(A, left, pivotPoint-1)
        quickSort(A, pivotPoint+1, right)

• pivot 기준으로 배열을 나누는 partition()의 구현이 중요하다

1) 첫번째 원소를 pivot으로

def partition(A, left, right):
    pivot = A[left]
    i = left+1
    j = right
    while i <= j:
    
        # i는 오른쪽으로 이동하며 pivot보다 큰 수 탐색
        while i <= right and A[i] < pivot:
            i += 1
            
        # j는 왼쪽으로 이동하며 pivot보다 작은 수 탐색
        while j >= left+1 and A[j] >= pivot:
            j -= 1
            
        # i와 j 탐색 영역이 넘어가지 않았다면 교환 후 루프
        if i <= j:
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
            i += 1
            j -= 1
            
    # pivot을 위치에 맞게 바꾸고 pivotPoint인 j 반환
    A[left] = A[j]
    A[j] = pivot
    return j

2) 마지막 원소를 pivot으로

def partition(A, left, right):
    pivot = A[right]
    pivotPoint = left-1
    for i in range(left, right):
        if A[i] <= pivot:
            pivotPoint += 1
            exchange(pivotPoint, i)
            
    tmp = A[right]
    exchange(pivotPoint+1, right)

시간복잡도 :

W(n) = W(n-1) + bn
     = [W(n-2) + b(n-1)] + bn
     = W(n-k) + b(n-k+1 + n)k/2
     : O(n^2)