[알고리즘] Week 8: 동적 프로그래밍 - 개념과 예제

Day 1: 동적 프로그래밍의 개념

• 강의 내용:
  • 동적 프로그래밍의 정의와 중요성
    • 동적 프로그래밍(DP)이란 무엇인가?
    • 동적 프로그래밍의 기본 원리 (중복 부분 문제, 최적 부분 구조)
    • 동적 프로그래밍의 장점 및 활용 사례
  • 동적 프로그래밍과 분할 정복의 차이
    • 메모이제이션 (Top-down) vs. 테이블화 (Bottom-up)
• 실습:
  • 간단한 동적 프로그래밍 문제 예제 설명

# 피보나치 수열의 메모이제이션을 사용한 동적 프로그래밍 예제
def fibonacci_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
    return memo[n]

# 예제 실행
print("피보나치 수열의 10번째 항:", fibonacci_memo(10))  # 55

 

Day 2: 피보나치 수열 (Bottom-up 방식)

• 강의 내용:
  • Bottom-up 방식의 개념
    • 테이블화 방법 (Bottom-up) 소개
    • 피보나치 수열의 Bottom-up 방식 구현
  • Bottom-up 방식의 장단점
    • 메모리 사용 최적화
    • 코드 간결성
• 실습:
  • 피보나치 수열의 Bottom-up 방식 구현 및 예제

# 피보나치 수열의 Bottom-up 방식 구현
def fibonacci_bottom_up(n):
    if n <= 1:
        return n
    fib = [0] * (n + 1)
    fib[1] = 1
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    return fib[n]

# 예제 실행
print("피보나치 수열의 10번째 항 (Bottom-up):", fibonacci_bottom_up(10))  # 55

 

Day 3: 최장 공통 부분 수열 (Longest Common Subsequence, LCS)

• 강의 내용:
  • LCS의 개념과 정의
    • 두 문자열 간의 최장 공통 부분 수열 찾기
    • LCS 문제의 동적 프로그래밍 접근법
  • LCS의 구현
    • 테이블화 방법 (Bottom-up) 사용
• 실습:
  • LCS 알고리즘 구현 및 예제

# 최장 공통 부분 수열 알고리즘 구현
def lcs(X, Y):
    m = len(X)
    n = len(Y)
    L = [[0] * (n + 1) for i in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif X[i - 1] == Y[j - 1]:
                L[i][j] = L[i - 1][j - 1] + 1
            else:
                L[i][j] = max(L[i - 1][j], L[i][j - 1])

    return L[m][n]

# 예제 실행
X = "AGGTAB"
Y = "GXTXAYB"
print("최장 공통 부분 수열의 길이:", lcs(X, Y))  # 4 (GTAB)

 

Day 4: 배낭 문제 (Knapsack Problem)

• 강의 내용:
  • 배낭 문제의 개념과 정의
    • 0/1 배낭 문제 소개
    • 배낭 문제의 동적 프로그래밍 접근법
  • 배낭 문제의 구현
    • 테이블화 방법 (Bottom-up) 사용
• 실습:
  • 배낭 문제 알고리즘 구현 및 예제

# 0/1 배낭 문제 알고리즘 구현
def knapsack(W, wt, val, n):
    K = [[0 for x in range(W + 1)] for x in range(n + 1)]

    for i in range(n + 1):
        for w in range(W + 1):
            if i == 0 or w == 0:
                K[i][w] = 0
            elif wt[i - 1] <= w:
                K[i][w] = max(val[i - 1] + K[i - 1][w - wt[i - 1]], K[i - 1][w])
            else:
                K[i][w] = K[i - 1][w]

    return K[n][W]

# 예제 실행
val = [60, 100, 120]
wt = [10, 20, 30]
W = 50
n = len(val)
print("최대 가치:", knapsack(W, wt, val, n))  # 220

 

Day 5: 동적 프로그래밍을 이용한 기타 문제

• 강의 내용:
  • 동적 프로그래밍을 이용한 다양한 문제 소개
    • 최소 편집 거리 (Edit Distance)
    • 동전 교환 문제 (Coin Change)
  • 동적 프로그래밍의 적용 범위
    • 최적화 문제에서의 활용
    • 조합 문제에서의 활용
• 실습:
  • 최소 편집 거리 및 동전 교환 문제 구현

# 최소 편집 거리 알고리즘 구현
def edit_distance(str1, str2, m, n):
    dp = [[0 for x in range(n + 1)] for x in range(m + 1)]

    for i in range(m + 1):
        for j in range(n + 1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif str1[i - 1] == str2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])

    return dp[m][n]

# 예제 실행
str1 = "sunday"
str2 = "saturday"
print("최소 편집 거리:", edit_distance(str1, str2, len(str1), len(str2)))  # 3

# 동전 교환 문제 알고리즘 구현
def coin_change(coins, m, V):
    dp = [0] + [float('inf')] * V

    for i in range(1, V + 1):
        for j in range(m):
            if coins[j] <= i:
                dp[i] = min(dp[i], dp[i - coins[j]] + 1)

    return dp[V]

# 예제 실행
coins = [1, 2, 5]
V = 11
print("최소 동전 개수:", coin_change(coins, len(coins), V))  # 3

 

Day 6: 동적 프로그래밍의 성능 분석

• 강의 내용:
  • 동적 프로그래밍 알고리즘의 성능 분석
    • 동적 프로그래밍 알고리즘의 시간 복잡도 및 공간 복잡도 분석
    • 메모이제이션과 테이블화의 차이점
  • 동적 프로그래밍과 다른 접근 방식의 비교
    • 재귀와 반복의 비교
    • 분할 정복과 동적 프로그래밍의 비교
• 실습:
  • 다양한 동적 프로그래밍 알고리즘의 성능 비교 예제

# 성능 비교 예제: 피보나치 수열 (재귀 vs 동적 프로그래밍)
import time

def measure_time(func, *args):
    start_time = time.time()
    result = func(*args)
    end_time = time.time()
    return end_time - start_time, result

n = 30

# 재귀적 피보나치 수열 시간 측정
start_time = time.time()
fibonacci_time, _ = measure_time(fibonacci, n)
end_time = time.time()
print("재귀적 피보나치 계산 시간:", fibonacci_time)

# 동적 프로그래밍 피보나치 수열 시간 측정
fibonacci_memo_time, _ = measure_time(fibonacci_memo, n)
print("동적 프로그래밍 피보나치 계산 시간:", fibonacci_memo_time)

 

Day 7: 종합 연습 및 프로젝트 준비

• 강의 내용:
  • 동적 프로그래밍 종합 연습
    • 다양한 동적 프로그래밍 문제 풀이
    • 알고리즘 성능 분석 및 최적화
  • 프로젝트 준비
    • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 구현 계획 수립
• 실습:
  • 동적 프로그래밍 종합 연습 문제 풀기
  • 프로젝트 주제 및 계획 수립

### 종합 연습 문제 예시
1. 주어진 배열에서 최대 부분 배열의 합을 동적 프로그래밍을 사용하여 찾기
2. 주어진 두 문자열의 최소 편집 거리를 계산
3. 주어진 동전 종류로 특정 금액을 만들기 위한 최소 동전 개수 구하기

### 프로젝트 주제 예시
1. 동적 프로그래밍을 활용한 경로 최적화 시스템
2. 동적 프로그래밍을 이용한 데이터 압축 도구
3. 동적 프로그래밍을 사용한 재무 최적화 모델

### 프로젝트 요구사항 예시
1. 동적 프로그래밍을 활용한 경로 최적화 시스템:
   - 경로 입력 및 저장
   - 동적 프로그래밍 알고리즘을 통한 최적 경로 계산
   - 최적 경로 출력 및 분석

### 프로젝트 계획 예시
1. 데이터 입력 모듈 구현
2. 동적 프로그래밍 알고리즘 구현 (예: 최단 경로 알고리즘, 최대 이익 경로 등)
3. 데이터 출력 및 분석 모듈 구현

 

이 강의는 파이썬의 동적 프로그래밍 알고리즘, 특히 피보나치 수열, 최장 공통 부분 수열, 배낭 문제, 최소 편집 거리, 동전 교환 문제의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!