[파이썬] 알고리즘 패러다임 : Dynamic Programming

2023.02.27 코드잇 학습내용

 

🔎 Dynamic Programming

복잡한 문제를 더 작고 간단한 하위 문제로 분해하여 각각의 하위 문제를 한 번만 풀고, 각 하위 문제의 해결책을 표에 저장한 후 필요에 따라 재사용하는 알고리즘 패러다임.

 

Dynamic Programming의 조건

 

1. 최적 부분 구조 (Optimal Substructure)

최적 부분 구조가 있다는 것은 부분 문제들의 최적의 답을 이용하여 기존 문제의 최적의 답을 구할 수 있다는 것을 의미함.

즉, 기존 문제를 부분 문제로 나누어 풀 수 있어야 함. (ex. 피보나치 수열)

 

2. 중복되는 부분 문제 (Overlapping Subproblems)

피보나치 수열과 같이 최적 부분 구조가 있는 문제를 풀 때에는 중복 되는 부분 문제들이 있을 수 있음.

예를 들면, 피보나치 수 함수 fib(5)를 구하기 위해서는 아래와 같은 과정을 거침

fib(5) = fib(4)                          + fib(3)
          = fib(3)              + fib(2) + fib(3)
          = fib(2) + fib(1) + fib(2) + fib(2) + fib(1)

 

위와 같이 fib(5)를 푸는데 fib(3) 을 여러번 계산해야 함. 이렇게 같은 문제를 여러번 푸는 것은 비효율적.

이러한 비효율을 해결하는 알고리즘 패러다임이 다이나믹 프로그래밍

 

다이나믹 프로그래밍은 위와 같이 한 번 계산한 결과를 표에 저장해두었다 필요할 때 꺼내 쓰는 방식을 사용

→ 한 번 계산한 결과를 재활용하는 방식

 

다이나믹 프로그래밍을 구현하는 방법에는 Memoization과 Tabulation 두 가지 방법이 있음. 

 

📖 Memoization

중복되는 계산은 한 번만 계산 후 메모하고 그 이후에는 메모를 참고하는 방식으로, 재귀를 기반으로 코드를 작성.

메모를 저장하는 공간 즉, 다시 쓸 값을 저장해 두는 공간을 캐시(cache)라 함. 중복되는 계산은 캐시에 저장해 두고 다시 계산해야 할 때 꺼내 씀.

 

▼▼▼ Memoization으로 피보나치 함수 작성 ▼▼▼

① base case와 recursive 케이스 찾기

    - base case : n이 1 혹인 2일 때 1을 리턴함

    - recursive case → 2가지 경우로 나눌 수 있음

      1) 이미 cache에 키 n에 대한 값이 저장 되어 있을 때 → cache[n] 리턴

      2) cache에 키 n에 대한 값이 없을 때 → 재귀 활용하여 키 n에 대한 값을 구한 후 cache[n] 리턴

 

 

위와 같이 memoization은 맨 위에서부터 시작해 하나씩 내려가는 사고방식(하향식 접근, Top down approach).

memoization과 반대로 f(1)부터 차례대로 계산하여 구동하는 Bottom-up approach 방식이 있음. 이 방식 또한 한 번만 계산하므로 dynamic programming 중 하나. 이러한 방식을 Tabulation이라 함. 

 

📖 Tabulation

Table 방식으로 정리한다는 뜻으로 반복문을 사용해서 리스트를 채워나가게 됨

 

▼▼▼ Tabulation으로 피보나치 함수 작성 ▼▼▼

① 피보나치 수를 저장할 리스트 생성 (tab) 하고 0 ~ 2번째 값 넣기

     → 리스트는 인덱스 0부터 시작하므로 n번째의 피보나치 수를 찾기 위해서 인덱스 0에 0 입력

② 반복문 사용하여 tab에 피보나치 수 추가

 

 

▼▼▼ Tabulation으로 피보나치 수 찾기 (내가 작성한 코드) ▼▼▼

차이점 : 리스트 대신 딕셔너리, for문 대신 while문 활용하여 작성

 

📖 Memoization vs Tabulation

공통점 : 중복되는 부분 문제의 비효율을 해결

차이점 : Memoization은 재귀함수, Tabulation은 반복문을 사용

memoization의 경우 재귀 함수를 기반으로 작성하기 때문에 재귀 호출이 너무 많이 일어나면 스택이 쌓여 과부하가 되어 오류 발생. 반면, Tabulation은 처음부터 n번째까지 모두 계산하기 때문에 중간에 필요없는 부분까지 계산하는 경우도 있을 수 있음. memoization은 뒤에서부터 필요한 계산을 요구하는 형태이므로 불필요한 계산은 하지 않는다는 장점이 있음.

 

Tabulation으로 피보나치 함수 풀 경우

시간 복잡도 : O(n)

공간 복잡도 : O(n)

tabulation은 리스트에 모든 계산 값을 저장함 → 공간 복잡도를 줄이기 위해 가장 최근 값 2개만 변수를 사용하여 저장하면 공간 복잡도를 줄일 수 있음(current, previous) → 이렇게 하면 사용하는 메모리는 고정되어 있기 때문에 공간복잡도는 O(1)이 됨

 

▼▼▼ 공간 복잡도 O(1)인 피보나치 수 함수 작성 ▼▼▼

임시 저장 변수 사용한 경우 코드 :
for i in range(1, n)
    temp = current
    current = current + previous
    previous = temp

임시 저장 변수 생략한 경우 코드 :
for i in range(1, n)
    current, previos = current + previous, current

 

▼▼▼ 공간 복잡도 O(1)인 피보나치 수 함수 작성(내가 작성) ▼▼▼

임시 변수를 사용하여 작성하였고, temp에 previous 값을 저장

 

임시 저장 변수를 사용하지 않고 한줄로 작성한 코드