algo_lec5

 

 

Divide and Conquer (Part 3)

---

 

Review: Merge Sort

• 병합 정렬은 Divide → Conquer → Combine 단계로 구성
• 병합 단계에서 매 레벨마다 O(n) 시간 소요, 총 log n 단계 → O(n log n)
• Worst-case 비교 횟수: n - 1

예시:
[1, 3, 4, 7], [2, 5, 9] → [1, 2, 3, 4, 5, 7, 9]

---

merge_sort 코드 (copy 기반)

def merge_sort(arr):
    if len(arr) < 2:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    
    final_arr = []
    l = r = 0
    while l < len(left_arr) and r < len(right_arr):
        if left_arr[l] < right_arr[r]:
            final_arr.append(left_arr[l])
            l += 1
        else:
            final_arr.append(right_arr[r])
            r += 1
    final_arr += left_arr[l:]
    final_arr += right_arr[r:]
    return final_arr

• 비교 연산 수: h+m−1 = n - 1
• 시간복잡도: T(n) = 2T(n/2) + n−1 ∈ Θ(nlog⁡n)

---

병합 정렬의 Downside

• Temporary array 필요 (left_arr, right_arr, final_arr)
• In-place 정렬 아님

---

Better Approach: In-place Merge Sort

def merge(arr, start, mid, end):
    start2 = mid + 1
    if arr[mid] <= arr[start2]:
        return
    while start <= mid and start2 <= end:
        if arr[start] <= arr[start2]:
            start += 1
        else:
            value = arr[start2]
            index = start2
            while index != start:
                arr[index] = arr[index - 1]
                index -= 1
            arr[start] = value
            start += 1
            mid += 1
            start2 += 1

• 추가 배열 없이 index 이동으로만 병합
• 시간복잡도: Θ(n2log⁡n)\Theta(n^2 \log n)

---

Quick Sort

• Hoare (1962) 개발
• pivot 기준으로 작은/큰 두 파티션 생성 → 각 파티션에 재귀 적용

---

partition 함수

• Input
  • unsorted array
  • low (i.e., 0)
  • high (i.e., len(arr)-1)
• Output
  • sorted array in terms of pivot 
  • pivot

def partition(array, low, high):
    pivot = array[high]
    i = low - 1
    for j in range(low, high):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i + 1], array[high] = array[high], array[i + 1]
    return i + 1

• pivot보다 작은 값은 왼쪽으로 swap
• pivot은 정렬된 위치로 이동

---

partition Example

• 초기 배열: [21, 3, 12, 15, 7, 32, 4, 25, 9, 18]
• pivot = 18
• 결과: pivot 왼쪽엔 <18, 오른쪽엔 ≥18

---

quickSort 함수

• Input
  • sorted array in terms of pivot
• Output
  • sorted array

def quickSort(array, low, high):
    if low < high:
        c_pivot = partition(array, low, high)
        quickSort(array, low, c_pivot - 1)
        quickSort(array, c_pivot + 1, high)

---

시간복잡도

• Average case: Θ(nlog⁡n)
  • T(n) = 2T(n/2) + O(n) 

• Worst case (pivot이 항상 최대/최소일 때): Θ(n^2)
  • T(n) = T(n−1) + T(0) + O(n) ∈ Θ(n^2)

---

When not to use Divide and Conquer

: Divide and Conquer를 쓰면 안 되는 경우

• 분할 후 문제 크기가 거의 줄지 않는 경우 ( ex: T(n)=T(n−1)+O(n) )
• 분할된 문제 수가 n에 가까운 경우 (a ≈ n)
• 서브 문제의 크기가 거의 원래와 같은 경우 (b ≈ 1)

---

Greedy Algorithm (Part 1)

• 최적화 문제 해결에 자주 사용됨
• 현재 단계에서 가장 좋아 보이는 선택 반복 (locally optimal)
• 항상 전역 최적(global optimal)을 보장하진 않음 → 증명 필요

---

Pseudo-code of greedy algorithm

procedure GREEDY(A, n)
  solution := ∅ #start with empty set
  for i := 1 to n:
    x := SELECT(A) #Select current optimal one
    if FEASIBLE(solution, x):
      solution := UNION(solution, x) #Check this addition is feasible
  return solution

• 핵심 단계:
  1. 선택 (locally optimal)
  2. 가능성 검증
  3. 해에 포함

---

Example 1: Find minimum num. of coins for change

• 문제: y원을 가장 적은 동전 수로 만드는 방법
• 한국: [500, 100, 50, 10, 5, 1]
• 예: 1237원 → 최적해: [2, 2, 0, 3, 1, 2]

단점:

• Greedy는 항상 최적해를 보장하지 않음
• DP 방식은 항상 최적해 가능

---

Example 2: Matrix-chain product

• A = A_1 ⋅ A_2 ⋯ A_n
• 곱셈 순서에 따라 총 연산 수 달라짐

예시 1 (그리디 성공):

• A: 30×1, B: 1×40, C: 40×10, D: 10×25
• AxB=30x1x40=1200, BC=1x40x10=400, CD=40x1x25
• Choose BC. Let K (=1x10).
• AK=30x1x10, KD=1x10x25
• Choose KD. Let G (=1x25)
• Choose AG = (30x1)(1x25) = 30x1x25.
• BC → KD → AG → 총 곱셈 수: 1x40x10 + 1x10x25 + 30x1x25 = 1400

예시 2 (그리디 실패):

• A: 101×11, B: 11×9, C: 9×100, D: 100×99
• AB=101x11x9=9999, BC=11x9x100=9900, CD=9x100x99=89100
• Choose BC. Let K=11x100.
• AK=101x11x100, KD=11x100x99
• Choose KD. Let J=11x99.
• AJ=101x11x99
• Greedy: BC+KD+AJ = 228,789
• Optimal solution
  • AxB=101x11x9. Let K.
  • CxD=9x100x99. Let G.
  • KxG=101x9x99 
  • AB+CD+KG = 189,090

→ Greedy는 항상 최적 보장 X
→ Dynamic Programming(DP)으로 해결 가능