[다이나믹프로그래밍] DP - JS, Python

다이나믹 프로그래밍 

큰 문제를 작게 나누고 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하려는 알고리즘 기법

다이나믹 프로그래밍을 사용할 수 있는 경우

1. 최적 부분 구조(큰 문제를 작은 문제로 나눌 수 있다)

2. 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결 (최적화))

 

위의 두 조건이 모두 충족할 경우 다미나믹 프로그래밍을 사용할 수 있다 (점화식 사용)

 

다이나믹 프로그래밍 최적화의 핵심

• 각 작은 문제는 한 번만 풀어야 한다
• Optimal Substructure를 만족하기 때문에 같은 문제는 구현 때마다 정답이 같다
• 정답을 한 번 구했으면 어딘가에 메모해 놓는다
• 메모하는 것을 코드에서는 배열로 구현할 수 있다
• 메모한다고 해서 memoization 용어를 쓴다

 

다이나믹 프로그래밍의 특징

1. 다이나믹 프로그래밍은 보텀업 방식과 탑타운 방식이 있다. (보텀업 방식이 일반적)

• 보텀업 방식 : 반복문을 이용하여 소스코드를 작성해 작은 문제부터 차근차근 답을 도출(DP테이블 사용)
  •  
• 탑다운 방식 : 큰 문제를 해결하기 위해 작은 문제를 호출(재귀 이용(메모이제이션 방법))
  • 메모이제이션 : 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 => 값을 저장하는 방법이므로 캐싱이라고도 한다.
  • 재귀함수를 이용하는 방법, 한번 푼 문제는 그 결과를 저장해 놓았다가 나중에 동일한 문제를 풀어야 할 때 이미 저장한 값을 반환한다.

2. 큰 문제를 작은 문제로 나누는 방법이라는 점에서 분할 정복과 같아보이지만 차이점이 있다. 

• 분할정복 : 퀵 정렬에서 사용됐는데, 리스트를 분할하면 전체적으로 정렬될 수 있도록 하는 기법
  • 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 끼친다는 것, 한 번 얘기했던 문제를 다시금 해결해야한다
  • 분할정복을 퀵정렬을 예로 들면 한 번 기준 원소가 자리를 변경해서 자리를 잡게 되면 그 기준 원소의 위치는 더 이상 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않음

3. 재귀함수만을 사용했을 때 시간복잡도는 O(2^n), DP를 사용하는 경우 시간 복잡도 O(N)

좌 : 피보나치 재귀 호출,  우 : DP방식(보텀업, 탑다운)  

• 재귀 사용 시 동일한 함수가 반복적으로 호출됨. 이미 계산했지만 호출할 때마다 계속 계산됨
• 탑 다운 방식에서는 한 번 돌았던 함수는 리스트에 저장. 그 함수를 돌 때마다 저장된 값을 불러옴 
  하지만 재귀를 사용하면 컴퓨터 시스템에서는 함수를 다시 호출했을 때 메모리 상에 적재되는 일련의 과정을 따라야 하므로 오버헤드 발생할 수 있음 => 재귀대신 반복문으로 사용하여 오버헤드 줄일 수 있음(보텀업)
• 보텀업 방식을 사용하는 것을 추천. 보텀업 방식 사용시 반복문을 돌면서 작은 문제부터 차근차근 답을 도출하여 DP테이블에 저장한다. DP테이블에서 계산한 값을 불러와 큰 문제의 답을 도출해낸다

피보나치 수열 구현

기본 구현

피보나치 점화식 An = An-1 + An-2, A1=1, A2=2

Python

# 재귀 => O(2^n)으로 매우 비효율적
# f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(2) f(1) f(4) f(3) f(2) f(1) f(2) 8
def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)


print(fibo(6))

JS

const fibo = function(x) {
    console.log(`f(${x}) `)
    if (x === 1 || x === 2) {
        return 1
    }
    return fibo(x - 1) + fibo(x - 2)
}

console.log(fibo(6))

 

탑다운(메모이제이션)

1. 메모할 리스트를 만든다(d)

2. 원하는 위치의 값(x)을 인덱스로 사용하여, d[x]이 0인지 아닌지 판별(원하는 위치x의 값을 구했는지 아닌지)

3. d[x]값이 0인 경우 x-1과 x-2의 값을 호출 

4. d[x]값이 0이 아닌 경우 결과값 return 

Python

# 피보나치 수열을 재귀함수로 구현(탑다운 다이나믹 프로그래밍)
# f(6) f(5) f(4) f(3) f(2) f(1) f(2) f(3) f(4) 8
# 시간복잡도 O(2^N) => O(N)
def fibo(x):
    print('f(' + str(x) + ')', end=' ')
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제면 그대로 반환
    if d[x] != 0:
        return d[x]
    # 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]


print(fibo(6))

JS

let d = Array(100).fill(0)

const fibo = function(x) {
    if (x === 1 || x === 2) {
        return 1
    }
    if (d[x] !== 0) {
        return d[x]
    }
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

}   

const result = fibo(99)
console.log(result)

 

보텀업(DP테이블)

1. DP테이블을 생성한다(d)

2. 고정값 정의 (A1=1, A2=1)

3. 3에서 n+1만큼 돌면서 An = An-1 + An-2 반복

Python

# 앞서 계산된 결과를 저장하기 위한 dp테이블 초기화
d = [0] * 100

# 첫번째 피보나치 수와 두번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

print(d[n])

JS

let d = Array(100).fill(0)
// console.log(d)

d[1] = 1
d[2] = 1
const n = 99

for (let i = 3; i < n+1; i++) {
    d[i] = d[i-1] + d[i-2]
}

console.log(d[n]) // 218922995834555200000