[Day+17] DP(Dynamic Programing)

동적 프로그래밍 (DP)

복잡한 문제를 여러개의 작은 하위 문제로 쪼개서 푸는것

 -> 하위 문제를 먼저 풀어서 그 결과를 쌓아 올리는것

 

DP의 정의이다.. 위의 말을 보면 동적프로그래밍이 뭐인지 정확한 감이 오지 않는다.

오히려 재귀에 가까운 설명이라고 생각이 드는데 이런 생각이 들면 정답이다. 결국 DP는 재귀적 문제를 효율적으로 처리하기 위한 방식이다.

 

DP의 핵심은 하위 문제를 풀어서 '저장' 해놓고 그 결과를 쌓아 올리는것이다.

---

DP 풀이의 종류

1. 메모제이션(탑다운)

 재귀를 사용하면서 계산된 결과를 저장하는것

2. 테이블(바텀업)

작은 문제부터 해결해 가는 방식. 가장 바닥의 값을 미리 계산해놔야함

---

DP의 풀이과정

1. 문제 이해

2. 테이블 정의

3. 점화식 정의

4. 초기값 설정

 

DP를 이해하기 위해 Fibonacci 수열을 코드로 풀이를 해 보겠다. 

 

먼저 기본적인 재귀 방식

def fibonacci_recursive(n):
    if n <= 1: # 기저조건
        return n
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2) #점화식
 
print(fibonacci_recursive(10))  # 55

 

---

메모제이션 방식

def fibonacci_memoization(n, memo=None):
    # 메모 딕셔너리를 초기화합니다.
    if memo is None:
        memo = {}
    # 이미 계산된 값이 있는지 확인합니다.
    if n in memo:
        return memo[n]
    # 기저 조건: n이 0 또는 1일 때, n을 반환합니다.
    if n <= 1:
        return n
    # F(n-1)과 F(n-2)를 재귀적으로 계산하고 그 합을 메모에 저장합니다.
    memo[n] = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo)
    # 계산된 값을 반환합니다.
    return memo[n]

print(fibonacci_memoization(10))  # 55

메모제이션 방식은 재귀적으로 호출을 하고 해당 값을 딕셔너리에 저장을 해서 같은 값을 두번 계산 안하도록 하는 것이다.

---

테이블 방식

def fibonacci_tabulation(n):
    if n <= 1:
        return n
    # dp 테이블 초기화
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    # 점화식을 이용하여 dp 테이블을 채웁니다.
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fibonacci_tabulation(10))  # 55

테이블 방식은 최초 가장 기본 값을 미리 계산 한 후 dp 테이블을 최신화하면서 값을 계산하는 방식이다.

 

이처럼 DP를 사용하면 재귀에서 같은 값을 계속 다시 계산하는 불필요한 행위를 없앨 수 있음으로 매우 효율적인 방식이다.

이제 DP를 사용하기 위해 점화식과 테이블을 어떻게 초기화 해야할지 연습을 많이 해야할 것 같다.

 

---

오늘의 회고

이제 알고리즘을 어떤식으로 공부해야할지 알 것 같다. 저번주차 문제를 최대한 풀기 위해서 밤새가면서 문제를 풀었는데 오늘부터 1시간에서 1시간30분까지 문제를 풀어보고 시간이 지나면 무조건 풀이를 보고 30분동안 푸는 시간을 가질것이다. 오늘 알고리즘 테스트를 진행했는데 아직 부족하지만 그래도 내가 조금은 알고리즘에 대해서 알아 가는구나라는 느낌을 가졌다. 좀더 효율적으로 그리고 부지런히 공부를 해야할 것같다. 이제 슬슬 허리가 아파온다 바른자세에도 신경을 쓰자!