algo_lec8

 

 

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)

(2,3,1) 이 아니라 (2,3,4) 와 (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)