algo_lec4

 

Divide and Conquer (Part 2)

---

Today’s topics

• Modular exponentiation (모듈러 지수 연산)
• Matrix multiplication (행렬 곱셈)
• Merge sort (병합 정렬)

---

1. Modular Exponentiation 지수승

개념

• RSA 암호 시스템에서 자주 등장
• 수백 비트 크기의 수 x, y, N에 대해 x^y (mod  N)을 효율적으로 계산해야 함

---

모듈러 연산 성질

• 덧셈: (x+y)+z ≡ x+(y+z)
• 곱셈: xy ≡ yx (mod N)
• 분배법칙: x(y+z) ≡ xy+xz (mod N)
• Equivalence class mod N: 정수 전체를 N개의 클래스 {i + kN}로 나눌 수 있음
  • 예: N = 3
    • {…, -3, 0, 3, 6, …}, {…, -2, 1, 4, 7, …}, {…, -1, 2, 5, 8, …}

---

모듈러 계산의 Rule

• x ≡ x′ mod  N, y ≡ y′ mod N 이면, x+y ≡ x′+y′ (mod N), xy ≡ x′y′ (mod N).
• 중간 계산에서 언제든지 모듈러 연산 가능 (계산 효율성 증가)

---

예시: 

2^10 mod  31 = 1024 mod  31 = 1

---

효율적 계산 방법

• x^y mod  N → 지수를 절반씩 나눔

---

Examples: 11^7 mod 13

---

구현 (Python)

def mod_exponent(x, y, n):
    if y == 0:
        return 1
    elif y % 2 == 0:
        s = mod_exponent(x, y // 2, n)
        return (s * s) % n
    else:
        s = mod_exponent(x, y - 1, n)
        return (x * s) % n

---

Modular exponentiation - time complexity

• x, y, N: n비트 수
• 총 재귀 호출: O(n)회
• 각 호출당 곱셈 연산: O(n²)
  → 전체 시간복잡도: O(n³) 비트 연산

---

2. Matrix Multiplication (행렬 곱셈)

---

Divide and Conquer 방식

• n×n 행렬을 2^k×2^k 로 가정
• 행렬을 4개의 n/2×n/2 서브행렬로 나눔

---

Strassen’s Algorithm

• 곱셈을 8 → 7회로 줄임, 대신 덧셈/뺄셈 증가
• 시간복잡도

---

3. Merge Sort (병합 정렬)

---

개요

1. 배열을 반으로 나눔
2. 각 부분을 재귀적으로 정렬
3. 정렬된 두 배열을 병합

→ 분할 정복 방식

---

Merge Sort Examples

---

구현 코드 (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

• What about the # of while loops in the worst case?
  • len(left_arr)+len)right_arr)-1 = h+m-1

---

시간복잡도 분석

• 병합 연산: O(n)
• 재귀 깊이: log⁡2n
• 전체 시간복잡도: T(n) = 2T(n/2)+n-1 ⇒ T(n)=nT(1)+log2 n(n-1) ∈ Θ(nlog⁡n).

---

단점 Downside

• 정렬 과정에서 Temporary arrays(복사 배열)이 필요함 (e.g., left_arr, right_arr, final_arr)
• → in-place 정렬 아님

---

In-place Merge Sort

• Only requires moving indices of arr.

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

def mergeSort(arr, l, r):
    if l < r:
        m = l + (r - l) // 2
        mergeSort(arr, l, m)
        mergeSort(arr, m + 1, r)
        merge(arr, l, m, r)

• in-place sort란, 추가 배열 없이 인덱스 이동으로 구현하는 정렬 알고리즘