CSE&MATH

Today's Topics

1. Dynamic programming
2. Example1 binomial coefficients
3. Example2 longest increasing subsequence

Dynamic Programming (DP)

정의 및 특징

• 문제를 부분 문제로 나눈 뒤, 반복되는 계산을 피하기 위해 결과를 저장하여 사용하는 최적화 기법
• Divide-and-Conquer와 차이점
  • Divide-and-Conquer는 재귀적으로 호출만
  • Dynamic Programming은 결과를 저장(Memoization or Tabulation)
• 핵심 구성:
  1. 점화식(Recursive property)
  2. 하향식(Memoization) 혹은 상향식(Tabulation)
  3. 저장된 값을 재사용 (Overlapping Subproblems)
• "Bottom-up approach"

Example 1: Binomial Coefficient (이항 계수)

구현

def binomial_recursive(n, k):
    if k == 0 or k == n:
        return 1
    return binomial_recursive(n - 1, k - 1) + binomial_recursive(n - 1, k)

# 예시 실행
print("C(5, 2) =", binomial_recursive(5, 2))

• 재귀적 방법: 매우 비효율적 (중복 계산 다수) ∴ Keep results of binomial(i,j) using a temporary 2D-array B where B[i,j] contains the value of (i j)

• DP (Bottom-up) 기반 code

def binomial_dp(n, k):
    B = [[0 for _ in range(k + 1)] for _ in range(n + 1)]
    
    for i in range(n + 1):
        for j in range(min(i, k) + 1):
            if j == 0 or j == i:
                B[i][j] = 1
            else:
                B[i][j] = B[i - 1][j - 1] + B[i - 1][j]
    
    return B[n][k]

# 예시 실행
print("C(5, 2) =", binomial_dp(5, 2))

• 시간복잡도: O(nk)
• 공간복잡도: O(nk) → 개선 가능 (공간 재사용)

  

Pascal's Triangle (파스칼 삼각형) 구현: 공간 효율적

def pascal_triangle(n):
    result = []
    for i in range(1, n + 1):  # i: 1부터 n까지
        B = 1  # 각 줄의 첫 번째 값은 항상 1
        line = []
        for j in range(1, i + 1):
            line.append(B)
            # 다음 항 계산 (DP적 재사용)
            B = B * (i - j) // j
        result.append(line)
    return result

# 예시 실행
n = 5
triangle = pascal_triangle(n)

# 출력
for row in triangle:
    print(row)

Example 2: Longest Increasing Subsequence (LIS)

문제 설명

• 주어진 수열에서 증가하는 부분 수열 중 가장 긴 길이 구하기
• 인접하지 않아도 되며, 왼쪽 → 오른쪽 순서만 유지

• 예제
  • S=(9,5,2,8,7,3,1,6,4): the longest increasing subsequence has length 3 and is either (2,3,4) or (2,3,6)

점화식

• hₖ 정의 및 설명
  • → hₖ는 원소 aₖ로 끝나는 가장 긴 증가 부분 수열의 길이라고 정의한다.
  • → i번째 원소를 포함하는 가장 긴 증가 부분 수열은, i보다 왼쪽에 위치한 원소들 중에서
    aᵢ보다 작은 원소로 끝나는 가장 긴 증가 부분 수열 뒤에 aᵢ를 덧붙여 만들어진다.

[ LIS(Longest Increasing Subsequence) 알고리즘이 동작하는 과정을 보여주는 핵심 예제]

• hᵢ: 원소 aᵢ로 끝나는 가장 긴 증가 부분 수열의 길이
• predecessor(i): aᵢ 바로 이전에 오는 LIS 원소의 인덱스

구현

def lis(arr):
    n = len(arr)
    h = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j] and h[i] < h[j] + 1:
                h[i] = h[j] + 1
    return max(h)

#test code
arr=[10,22,9,33,21,50,41,60]
print "Length of lis is", lis(arr)

복잡도

• Time Complexity: O(n²)
• Space-Complexity: O(n)

Example 5: Fractional Knapsack

문제 정의

: fractional knapsack problem이란?

• 물건마다 가치(value)와 무게(weight)가 있음
• 배낭의 최대 수용 무게 W가 주어짐
• 각 물건은 조각내어 일부만 넣을 수 있음 (fractional 가능)

• 배낭 용량 W 안에서, 물건을 쪼개서 최대 가치를 채워 넣는 문제

Greedy 해법

• 단위 무게당 가치 (value/weight) 기준으로 내림차순 정렬
• 배낭에 넣을 수 있을 만큼 넣고, 남으면 일부만 비례하여 넣음

코드 핵심

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight

def fractional_knapsack(W, items):
    # value/weight 비율로 정렬 (내림차순)
    items.sort(key=lambda x: x.value / x.weight, reverse=True)

    total_value = 0.0  # 총 가치
    remaining_capacity = W

    for item in items:
        if item.weight <= remaining_capacity:
            # 전체 항목을 넣을 수 있으면 전부 넣음
            total_value += item.value
            remaining_capacity -= item.weight
        else:
            # 일부만 넣고 종료
            fraction = remaining_capacity / item.weight
            total_value += item.value * fraction
            break

    return total_value

• 정렬 후 반복문으로 가득 찰 때까지 item 추가
• 시간복잡도: O(n log n)

The greedy approach always gives an optimal solution for the fractional knapsack problem. 

Example 6: Shortest Path – Dijkstra's Algorithm

문제 정의

• 단일 시작 정점에서 다른 정점까지의 최단 경로

핵심 아이디어

• dist[ ]: 시작점부터의 최단 거리
• sptSet[ ]: shortest path tree에 포함 여부
• 방문하지 않은 정점 중 가장 가까운 정점을 선택 → 인접 정점의 거리 갱신

코드 흐름

import sys  # 무한대를 표현하기 위한 용도 (sys.maxsize 사용)

V = 5  # 그래프의 정점 수

# 현재까지 확정되지 않은 정점 중에서 최단 거리(dist)가 가장 짧은 정점을 선택
def minDistance(dist, sptSet):
    min = sys.maxsize  # 초기값은 무한대
    for u in range(V):
        if not sptSet[u] and dist[u] < min:
            min = dist[u]
            min_index = u
    return min_index  # 최단 거리 정점의 인덱스 반환

# Dijkstra 알고리즘 구현
def dijkstra(graph, src):
    dist = [sys.maxsize] * V  # 시작점으로부터 각 정점까지의 거리. 초기값은 무한대
    dist[src] = 0             # 시작점은 거리 0
    sptSet = [False] * V      # 최단 경로가 확정된 정점 여부를 저장하는 배열

    for _ in range(V):
        u = minDistance(dist, sptSet)  # 아직 확정되지 않은 정점 중 최단 거리인 정점 선택
        sptSet[u] = True               # 선택된 정점은 최단 경로 확정

        # 선택된 정점 u에 인접한 모든 정점 v에 대해 거리 갱신
        for v in range(V):
            # 조건:
            # 1. u와 v 사이에 간선이 존재해야 하고 (graph[u][v] > 0)
            # 2. v는 아직 최단 경로가 확정되지 않았으며
            # 3. u를 거쳐 v로 가는 경로가 기존보다 짧을 경우
            if graph[u][v] > 0 and not sptSet[v] and \
               dist[u] + graph[u][v] < dist[v]:
                dist[v] = dist[u] + graph[u][v]  # 거리 갱신

    # 결과 출력: 시작점으로부터 각 정점까지의 최단 거리
    print("Vertex \tDistance from Source")
    for i in range(V):
        print(i, "\t", dist[i])

• 초기 dist는 ∞, 시작점은 0
• 인접 정점 탐색하며 조건에 따라 dist 업데이트

예시

• 5개 정점의 가중치 그래프
• 각 단계에서 dist[] 값이 갱신됨

Time Complexity

• O(V²)

가중치가 음수가 아닌 그래프에 대해 항상 최적해 보장

6. Huffman Coding

목적: 문자 인코딩 압축

• 어떤 문자열에서 문자마다 고정된 길이의 코드 대신, 빈도에 따라 가변 길이 코드를 부여하면 전체 파일 크기를 줄일 수 있음
• 특히 자주 등장하는 문자는 짧게, 드물게 등장하는 문자는 길게 코딩하면 효율적

기본 용어

• prefix-free code:
  어떤 코드도 다른 코드의 접두사(prefix)가 되어서는 안 됨
  (예: "0", "01" → 접두사 관계 → X)
• Huffman Code:
  문자들의 등장 빈도(frequency)를 기반으로 prefix-free한 최적의 이진 코드를 만들어주는 알고리즘
  → Greedy 알고리즘 기반

정의

• 각 문자를 고유한 Binary cid(이진 코드)로 표현
• 빈도에 따라 가변 길이 코드를 할당해 전체 길이 최소화

예시

• fixed-length binary code
  • a:00 b:01 c:11
  • ababcbbbc 000100011101010111 (18 bits)
• variable-length binary code
  • a:10 b:0 c:11
  • ababcbbbc 1001001100011 (13bits)
• 허프만 코드 (가변 길이): 150비트 (약 25% 절약 가능)

→ 각 줄의 의미는 다음과 같아:

• freq: 각 문자가 등장하는 횟수 (총 60 + 5 + 30 + 5 = 100회 등장)
• fixed: 고정 길이 binary code(2비트씩)
  • 4개의 문자니까 ⌈log⁡2 4⌉=2bit 필요
• prefix: 가변 길이 코드 (Huffman coding 기반)
  • 자주 등장하는 문자일수록 코드가 짧다 (예: a는 1비트)

(1) Fixed-length 코드의 경우:

• 문자 하나당 2bit 고정
• 문자 100개 전체 저장에 필요한 비트 수:100×2=200 bits

(2) Prefix code의 경우 (Huffman 기반):

• 각 문자의 비트 수 × 등장 횟수로 계산: 

얼마나 절약되었는가?

• Fixed-length: 200비트
• Prefix code: 150비트
• 절약된 비트 수: 200−150=50비트
• 절감률: 50200×100=25%

→ 25% 저장공간 절약

표 해석: Fixed-length vs Variable-length Huffman Codewords

고정 길이 코드

• 6개의 문자를 표현해야 하므로 최소 ⌈log⁡2 6⌉=3비트 필요
• 모든 문자가 3비트로 고정됨

Huffman 코드

• 빈도 기반 트리 구조에 따라 부여된 가변 길이 코드
• 자주 등장하는 a는 1비트, 드물게 등장하는 e, f는 4비트

아래 그림: 두 개의 Huffman Tree 구조

두 그림 모두 같은 문자 집합을 사용했지만,
Huffman Tree 구성 순서에 따라 구조가 달라질 수 있음을 보여줌.

하지만 중요한 건:

두 트리 모두 동일한 total bit 수 (224비트)를 만들어냄 
(왜냐하면, Huffman coding은 최적 prefix-free 코드를 항상 생성하기 때문)

Huffman 인코딩의 총 비트 수 계산

bit(T) = ∑ freq(v_i) × depth(v_i)

• freq(v_i): 문자 v_i의 등장 횟수
• depth(v_i): Huffman tree에서 해당 문자가 위치한 깊이 (루트에서의 거리)

적용 예제

→ 실제로 슬라이드 전체 Huffman 예제에서 나온 총 비트 수와 정확히 일치.

Example

1. 가장 작은 두 빈도 f:8, b:9 → 합쳐서 17
   (이게 그림의 오른쪽 하단 트리로 표시됨)
2. 그 다음 작은 두 빈도 c:12, d:14 → 합쳐서 26
   (왼쪽 하단 트리로 표시됨)
3. 다음 작은 두 빈도 a:15, 17 → 합쳐서 32
   (오른쪽 상단에서 32가 생김)
4. 마지막으로 26과 32를 합쳐서 58
   (중앙 루트 노드가 58인 트리 생성)

여기까지 병합한 결과:

• 왼쪽 서브트리 (26): c, d 포함
• 오른쪽 서브트리 (32): a, f, b 포함
• 루트는 58

아직 등장하지 않은 노드: e:42

• Step 4에서 생성된 트리의 루트가 58
• 남은 노드 e:42와 위에서 만든 노드 58을 합쳐서 루트 노드 100 생성

알고리즘 흐름

• 각 문자 빈도수로 우선순위 큐 생성 (min-heap)
• 빈도 낮은 두 노드를 병합
• 최종 트리에서 각 문자에 prefix-free codeword 부여

Time Complexity

• Heap 사용 시 O(n log n)

항상 최적의 prefix-free binary code를 생성함

Today’s Topics

• Graph Coloring
• Minimum Spanning Tree (MST)
• Prim’s Algorithm
• Kruskal’s Algorithm

Example 3: Graph Coloring

• 인접한 두 정점에 다른 색을 할당
• 그래프 G=(V,E) 가 주어졌을 때,
  색칠 함수 C:V→S (S는 색의 집합)을 찾는 것이 목표.
• 제약 조건:
  ∀(vi,vj) ∈ E, C(vi) ≠ C(vj).
• "The chromatic number"
  
  • 그래프를 조건에 맞게 색칠하는 데 필요한 최소 색 개수를 의미.
    즉, 가장 효율적으로 색칠했을 때 몇 가지 색만 있으면 되는지를 나타내는 수.
    • 예:
      • 이분 그래프 → 항상 chromatic number = 2
      • 완전 그래프 K_n → chromatic number = n

Greedy algorithm

• 각 정점 v_i에 대해:
  1. 가능한 가장 작은 색 c를 시도
  2. 인접한 정점들이 c를 쓰고 있으면 c+=1
  3. 가능한 색을 찾으면 그걸 할당

for i in range(n):
  c = 1
  while neighbor of v_i is colored with c:
    c += 1
  color[v_i] = c

Python Example

• graph.adj[u]: 정점 u에 인접한 노드 리스트
• adj_colors: 인접한 정점들이 쓰고 있는 색들의 집합
• result[u]: 정점 u에 할당된 최종 색

def colorGraph(graph, n):
    result = {}
    for u in range(n):
        adj_colors = set([result.get(i) for i in graph.adj[u] if i in result])
        color = 1
        while color in adj_colors:
            color += 1
        result[u] = color

• Time complexity: O(VE) 
  • where V: # of nodes, E: # of edges
  • 각 정점에 대해, 인접 정점들(V에 대해 E개 인접리스트 탐색)을 반복하기 때문.
• It doesn't always return an optimal solution.
• Two isomorphic graphs can have different X(G) if we number nodes somewhat differently
  • 서로 동형(isomorphic)인 두 그래프도, 정점에 번호를 다르게 붙이면 X(G)가 달라질 수 있음.
    • Isomorphic Graphs (동형 그래프):
      두 그래프가 구조적으로 동일함. 즉, 정점 간의 연결 방식(형태)은 같고, 정점 번호만 다름.
    • X(G):
      Greedy Coloring 알고리즘이 실제로 사용하는 색의 수를 의미.
      이건 chromatic number(진짜 최소 색 수)와는 다름!
  • 동일한 구조를 가진 그래프(즉, isomorphic)라고 하더라도,
    정점의 번호 매기기 순서가 다르면 Greedy 알고리즘의 선택 순서가 달라져서,
    실제로 사용하는 색의 수 X(G)X(G)X(G)가 달라질 수 있다는 뜻.

Graph Coloring applications: Scheduling

• 위원회 간 중복 인원을 고려하여 회의 시간을 배정
• 각 위원회를 정점으로, 겹치는 인원이 있으면 간선
• 최소 색칠 수 → 최소 시간 슬롯 수

Example 4: Minimum Spanning Tree (MST)

MST란,

• 주어진 무방향 연결 그래프 G=(V,E)에서
• 모든 정점을 포함하고
• 사이클이 없으며
• 간선 가중치의 총합이 최소인 트리를 말함.

MST algorithm 1: Prim’s Algorithm

• MST를 구성할 때, 정점 중심으로 트리를 확장해나가는 Greedy 알고리즘
• 항상 현재까지 만들어진 트리에 가장 가까운 정점을 하나씩 추가하는 방식

• 초기: 임의의 정점 하나 선택
• 항상 가장 가까운 정점을 추가 (locally optimal choice)
• 유사한 방식: Dijkstra’s algorithm

Pseudo-code:

F := ∅
Y := {v₁}
while Y ≠ V:
  선택: Y에 가장 가까운 V-Y 정점
  그 정점과 연결된 간선을 F에 추가

Python 구현 요약:

• 작동방식
  1. 임의의 정점 v_1을 시작점으로 선택해 집합 Y에 추가
  2. Y에 인접한 정점 중, 가장 적은 비용의 간선을 통해 연결된 정점 v를 선택
  3. 그 정점과 연결된 간선을 MST 집합 F에 추가
  4. v를 Y에 추가
  5. 위 과정을 Y=V가 될 때까지 반복
• key[ ]: 최소 연결 비용
• parent[ ]: 각 노드의 부모 저장
• mstSet[ ]: 방문 여부

def primMST(graph):
    key = [inf] * V       # 최소 연결비용
    parent = [None] * V   # MST 트리 내에서의 부모
    mstSet = [False] * V  # MST 포함 여부

    key[0] = 0             # 시작 정점 (0번)
    parent[0] = -1         # 루트 노드

    for _ in range(V):
        u = minKey(key, mstSet)  # MST에 포함되지 않은 정점 중 key가 최소인 u
        mstSet[u] = True         # u를 MST에 포함

        # u에 인접한 모든 정점 v에 대해
        for v in range(V):
            if graph[u][v] > 0 and not mstSet[v] and key[v] > graph[u][v]:
                key[v] = graph[u][v]
                parent[v] = u

• 시간복잡도: O(V²) (인접 행렬 기반)

🔴 초기 상태 (u = 0)

• 시작 정점: 0
• mstSet = [T, F, F, F, F] → 0번 노드만 포함
• key = [0, 2, ∞, 6, ∞]
  • 정점 0에서 직접 연결된 노드:
    • 1번: 가중치 2 → key[1] = 2
    • 3번: 가중치 6 → key[3] = 6
• parent = [-1, 0, None, 0, None]
  • 1번과 3번은 0번을 통해 연결될 가능성 있음

🔴 단계 2 (u = 1)

• 다음으로 key 값이 가장 작은 1번 정점 선택
• mstSet = [T, T, F, F, F]
• 1번에서 연결된 정점들 업데이트:
  • 2번: 3 → key[2] = 3, parent[2] = 1
  • 4번: 5 → key[4] = 5, parent[4] = 1
• key = [0, 2, 3, 6, 5], parent = [-1, 0, 1, 0, 1]

🔴 단계 3 (u = 2)

• 가장 작은 key = 3인 정점 2 선택
• mstSet = [T, T, T, F, F]
• 정점 2에서 4로 연결된 간선: 7 (→기존 key[4] = 5는 무시)
• key와 parent는 그대로 유지.

🔴 단계 4 (u = 4)

• 다음 최소 key = 5인 정점 4 선택
• mstSet = [T, T, T, F, T]
• 정점 4 → 3 간선: 9 (→ key[3] = 6은 무시)

🔴 단계 5 (u = 3)

• 마지막 남은 정점 3 선택
• mstSet = [T, T, T, T, T] → MST 완성

🟢 최종 결과: MST 간선 목록

• (0, 1): 2
• (1, 2): 3
• (1, 4): 5
• (0, 3): 6

이 간선들만 따서 보면, 사이클이 없고 모든 정점을 연결하며, 총 가중치도 최소임.
→ Minimum Spanning Tree 완성!

MST algorithm 2: Kruskal’s Algorithm

Kruskal's algorithm이란,

• Greedy 알고리즘 기반의 MST(최소 신장 트리) 구성 방법 중 하나.
• 정점 중심이 아니라 간선 중심으로 MST를 만들어가는 방식.

Pseudo-code:

F := ∅
각 정점을 독립 집합으로 초기화
모든 간선을 가중치 기준 오름차순 정렬
가장 작은 간선부터 선택
  - 사이클이 생기지 않으면 간선 추가
모든 정점이 연결되면 종료

• 핵심: Union-Find 자료구조
  • 각 정점이 어느 집합(트리)에 속하는지를 추적하는 구조
  • find(x): x의 루트(집합 대표)를 찾음
  • union(x, y): x, y의 루트를 비교해서 서로 다른 집합이면 합침
  • 사이클 여부 판단:
    find(x) == find(y) 이면 → 이미 같은 집합 → 이 간선은 사이클 유발함 → ❌

• 모든 간선을 가중치 기준으로 정렬
• 하나씩 간선을 선택하며, 사이클이 생기지 않는 경우에만 MST에 포함
• 정점 수가 n개일 때, (n−1)개의 간선이 선택되면 MST 완성

Python 구현:

• find(): root 찾기

def find(parent, i):
    if parent[i] != i:
        parent[i] = find(parent, parent[i])  # 경로 압축 (path compression)
    return parent[i]

• union(): 랭크(rank)를 이용한 집합 합치기

def union(parent, rank, x, y):
    xroot = find(parent, x)
    yroot = find(parent, y)
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

(이미지 설명)

1️⃣ 서로 다른 높이(ranks)의 트리 병합

• 왼쪽:
  • 파란 트리의 루트는 D, rank = 1
  • 빨간 트리의 루트는 G, rank = 2
    → 높이가 낮은 트리를, 높이가 더 높은 트리에 붙임

📌 결과:

• 파란 트리 전체가 빨간 트리의 일부가 됨.
• D는 이제 G 아래에 연결됨.
• 전체 트리의 루트는 여전히 G, rank = 2 (변화 없음)

🧠 이유:

• 큰 트리 쪽으로 합치면 전체 트리의 깊이가 늘어나지 않음 → 효율적!

2️⃣ 동일한 높이(ranks)의 트리 병합

• 두 트리 모두 루트(D, E)의 rank = 1
• → 아무 쪽이나 루트가 될 수 있지만,
  → 한 쪽을 다른 쪽에 붙이고 rank를 1 증가시킴

📌 결과:

• 예시에서는 D 트리를 E 트리에 붙임 → E가 새 루트
• E의 rank는 1 → 2로 증가

🧠 이유:

• 두 트리 높이가 같아서 붙이면 루트의 높이가 1 증가함 (정확히 1만 증가!)
• rank 업데이트는 최소화됨

• 시간복잡도: O(E log E) (정렬 포함)

def KruskalMST(graph):
    result = []
    i, e = 0, 0  # i = index for sorted edges, e = edges in MST

    graph.edges.sort(key=lambda x: x[2])  # 간선 가중치로 정렬
    parent = [i for i in range(V)]
    rank = [0] * V

    while e < V - 1:
        u, v, w = graph.edges[i]
        i += 1
        x = find(parent, u)
        y = find(parent, v)

        if x != y:
            e += 1
            result.append((u, v, w))
            union(parent, rank, x, y)

MST Applications

• 전화선/고속도로/파이프라인 설계
• 최소 거리로 모든 지역 연결
• 핵심 목표: 최소 비용으로 전체 연결

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)으로 해결 가능

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란, 추가 배열 없이 인덱스 이동으로 구현하는 정렬 알고리즘

알고리즘 분석 (Part 2)

Practice 1 – Big-O Notation

• 5n2=O(n2)5n^2 = O(n^2): 참, c=6,n0=1c = 6, n_0 = 1
• 5n2+3=O(n2)5n^2 + 3 = O(n^2): 참, c=6,n0=2c = 6, n_0 = 2
• n3=O(n2)n^3 = O(n^2)?: 거짓. n≤cn \le c 가 항상 성립할 수 없기 때문

Practice 2 – Big-Omega Notation

• 5n2=Ω(n2)5n^2 = \Omega(n^2): 참, c=4,n0=1c = 4, n_0 = 1
• 5n2+3=Ω(n2)5n^2 + 3 = \Omega(n^2): 참, c=1,n0=1c = 1, n_0 = 1
• n=Ω(n2)n = \Omega(n^2)?: 거짓. n≥cn2n \ge c n^2 를 만족하는 c는 없음

Big-O 복습

• 점근적 상한 (asymptotic upper bound)
• 예: n^2 + n, 2nlog⁡n+3n ∈ O(n^2)

Big-Omega 복습

• 점근적 하한 (asymptotic lower bound)
• 예: n^2 + n, 5n^2 + 15 ∈ Ω(n^2)

Big-Theta 복습

• 정확한 점근적 경계 (exact bound)
• Θ(f(n))=O(f(n))∩Ω(f(n))
• 예: 5n^2 + 15 ∈ Θ(n^2)

시간복잡도 예시 – 선형 탐색 복습

def search(arr, x):
    for index, value in enumerate(arr):
        if value == x:
            return index
    return -1
    
if __name__ == '__main__':
    arr = [1, 10, 30, 15]
    x = 30

    # Function call
    print(x, "is present at index", search(arr, x))

• Worst-case (W(n)): 타겟이 없거나 마지막 → O(n)
• Average-case (A(n)):
  • 총 비교횟수: (1+2+...+n) + n = n(n+1) / 2+n
  • 평균: A(n) = (n(n+1)/2+n) / (n+1)=n/2 = O(n)

Amortized Analysis – Accounting Method 복습

• push: $2 지불 → $1은 실제 비용, $1은 계좌에 저장
• pop: $0 지불 → 계좌에서 $1 차감
• multipop: pop과 동일
• 모든 연산의 평균 비용: O(1)

n회 수행 시 Amortized Time 복습

연산 Amortized 시간복잡도

→ 전체 비용은 O(n) → 개별 연산 평균 O(1)

Amortized Analysis – Potential Method

• 잠재 에너지(Φ)는 자료구조에 저장된 에너지
• 연산이 D₀ → D₁로 구조를 바꿀 때: Amortized Cost=real cost + Φ(D1) − Φ(D0)
• 스택에서 Φ(D) = 항목 수로 정의

예시:

• push: 실제 비용 1, Φ증가 1 → 총 2 = O(1)
• pop: 실제 비용 1, Φ감소 -1 → 총 0 = O(1)
• multipop(k): 실제 비용 min(k, s), Φ감소 동일 → 총 0 = O(1)

→ 평균적으로 모든 연산이 O(1)

공간복잡도 (Space Complexity)

• 저장 공간은 다음으로 구성:
  • 명령어, 상수, 변수
  • 입력 데이터
  • 추가 작업 공간 (자료구조 등)
• 입력이 배열로 주어지면 추가 공간만 분석
• 그래프처럼 표현 방식이 다양할 경우, 입력 + 추가 공간 모두 분석
• Worst-case, Average-case 공간복잡도 분석 가능

Divide and Conquer (분할 정복)

• 큰 문제를 작게 나누고, 각 문제를 해결 후 결과를 병합
• Top-down 방식
• 단계: Divide → Conquer → Combine

재귀관계 표현

예제 1: Binary Search

• 정렬된 배열에서 이진 탐색
• T(n) = T(n/2) + 1
• 풀이는 다음과 같이 전개됨

• 결정 트리의 깊이로 나타낼 수 있음
• 최악 비교 횟수는 ≥ log⁡2(n+1)

예제 2: 최대값 찾기 Find the maximum (findMax)

def findMax(arr, start, end):
    if start == end:
        return arr[start]
    mid = (start + end) // 2
    lmax = findMax(arr, start, mid)
    rmax = findMax(arr, mid+1, end)
    return max(lmax, rmax)

• 재귀 관계

예제 3: 곱셈 알고리즘

3-1. 반복적 곱셈

def multiply(x, y):
    if y == 0:
        return 0
    z = multiply(x, int(y/2))
    if y%2 == 0 #even number
    	return 2*z
    else #odd number 
    	return 2*z + x

• n = y의 비트 수
• 시간복잡도: O(n)

3-2. Divide & Conquer 곱셈

• 곱셈 4번 필요
• 재귀 관계:

3-3. Karatsuba multiplication

• 곱셈을 3번으로 줄임: T(n) = 3T(n/2)+O(n) ⇒ Θ(n log⁡2 3) ≈ Θ(n^1.585)

재귀 관계 예제 풀이

예제 1

+) 예제 2, 예제 3 > kr 파일에 문제 및 해설 존재