[알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법

동적 프로그래밍(Dynamic programming) 란? 

동적 프로그래밍은 "큰 문제"를 "부분 문제"로 나누고, "부분 문제"의 정답으로 "큰 문제"의 답을 찾는 알고리즘 설계 기법입니다.

동적 프로그래밍의 대표적인 예로 피보나치 수열을 예로 들 수 있는데요,

이 점화식을 코드로 표현하면 다음과 같습니다.

F[1] = 1
F[2] = 1
F[1] = F[2]
F[i] = F[i-1] + F[i-2]

점화식은 재귀식이라고도 하며 위 코드를 보면 피보나치 수열은 재귀적인 관계를 가지고 있다는 것을 알 수 있습니다.

---

DP를 적용하기 위한 2가지 조건

동적 프로그래밍을 적용시키기 위해선 다음 고같은 두 가지가 만족되어야 합니다.

• 부분 반복 문제(Overlapping Subproblem)
• 최적 부분 구조(Optimal Substructure)

이 두가지 특징이 대체 어떤 것인지 순서대로 알아봅시다.

 

DP의 조건 1 - 부분 반복 문제(Overlapping Subproblem)

피보나치 수열이 해를 찾는 과정을 보면 "큰 문제"를 찾기 위해 "부분 문제"가 필요하고 "부분 문제"는 중복됩니다.

 

피보나치 수열

만약 위 점화식을 이용해 fib[4]를 찾기 위해선 "부분 문제" fib[3]과 fib[2]를 찾아야하고, fib[3]은 또 쪼개져 fib[2]와 fib[1]의 해를 찾아야 합니다.

fib[4] = fib[3] + fib[2]
fib[4] = (fib[2] + fib[1]) + fib[2]

 이런식으로 fib[2] 의 해를 이미 했던 연산임에도 한번 더 총 2번을 구해야하는 "중복"이 나타나는데

이러한 반복적인 연산을 부분 반목 문제(Overlapping Subproblem) 라고 합니다.

이때, 부분 문제는 항상 새로운 부분 문제를 생성해내기 보다는 계속해서 같은 부분 문제가 여러번 재사용되거나 재귀 알고리즘을 통해 해결되는 문제를 가리킵니다.

 

fib(4)의 해를 구한다고 가정했을 때, 점화식을 통해 다음과 같이 나눌 수 있습니다.

문제	fib(4)의 해 구하기
부분 문제	fib(4-1)의 해 구하기 + fib(4-2)의 해 구하기.

 

 

DP의 조건 1 - 최적 부분 구조(Optimal Substructure)

"큰 문제"의 해는 "부분 문제"의 조합으로 찾을 수 있으며 문제의 해는 동일한 연산으로 수행되어야 한다.

 

fib(n) = fib(n-1) + fib(n-2);

위 피보나치 점화식에서 큰 문제의 답인 fib(n)이 최적의 답이 되기 위해선, 작은 부분 문제인 fib(n-1)과 fib(n-2)가 최적의 답이 되어야 합니다.

 

최적 부분 구조를 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 답은 일정한데 이를 피보나치 수열 그림을 참고해 간단히 설명하면,

• fib(5) 에서 구한 fib(3)
• fib(4) 에서 구한 fib(3)
• fib(3) 에서 구한 fib(3)

이 fib(3) 의 값들이 항상 같은 값인 것입니다.

하지만, fib(3) 은 같은 값이기 때문에 여러 번 반복되어 연산하는 것은 비효율적입니다.

그렇기 때문에 메모이제이션(Memoization) 이라는 개념이 도입되게 됩니다.

---

메모이제이션(Memoization)

동일한 문제를 반복해야 할 경우, 한 번 계산된 결과를 저장해 두었다가 활용하는 방식으로 중복 계산을 줄이는 것

메모이제이션을 통해, 이전에 계산한 값을 메모리에 저장함으로 써, 동일한 계산의 반복 수행이 제거 되어 프로그래밍 실행 속도를 빠르게 할 수 있습니다.

 

메모이제이션을 통해 위 피보나치 수열에서 fib(5)를 구할 시 중복되는 연산을 다음 메모이제이션을 통해 해결할 수 있습니다.

=> 저장해 두는 메모리(배열)을 캐시(Cache)라고 부르기도 합니다.

function fibonacci(n,memo) {
	// memo 오브젝트를 캐시로 사용
    memo = memo || {}
    
    // 함수를 호출할 때, memo 가 인수로 수신되었는지 확인.
    if (memo[n]) {
        return memo[n]
    }
    
    // 입력받은 n에 대한 캐시된 값이 있는지 확인하고 캐시된 값이 있으면 값을 반환. 
    // n 이 1보다 작거나 같은 경우 if문 종료
    if (n <= 1) {
        return 1
    }
    
    // 캐시된 값 ( memo ) 를 각 함수에 전달 하면서 n 보다 작은 값을 가진 함수를 재귀적으로 호출.
    return memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
}

 

출력결과는 다음과 같습니다.

console.log(fibonacci(3)) // --> 3
console.log(fibonacci(4)) // --> 5
console.log(fibonacci(5)) // --> 8

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

 

 

 

참고자료
https://kangworld.tistory.com/48
https://velog.io/@gillog/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming