[이코테] 7. 다이나믹 프로그래밍
관련 코드 구현
[BOJ] 11057 오르막 수
[이코테] 실전 문제(예제)
다이나믹 프로그래밍(Dynamic Programming)
다이나믹 프로그래밍은 메모리 공간을 약간 더 사용하여 연산 속도를 비약적으로 증가시키는 방법이다.
예를 들어 피보나치 함수를 재귀적으로 구현할 때 f(6) = f(5) + f(4) → f(5) = f(4) + f(3) 과 같이 구하게 되는데, f(4)의 호출이 반복적으로 일어난다. 이와 같은 중복 호출을 피하도록 하여 메모리 공간을 조금 더 할당하여 속도를 증가시키는 방법이다.
다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
메모이제이션 기법(Memoization)은 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 캐싱(Caching)이라고도 한다.
다이나믹 프로그래밍은 크게 2가지 방법으로 구현할 수 있다.
- 탑-다운(Top-down approach): 재귀함수와 메모이제이션을 이용하여 구현하는 방식
- 바텀-업(Bottom-up approach): 아래서부터 반복문을 이용하여 구현하는 방식, DP 테이블 사용
바텀-업 방식에서 사용하는 결과 저장용 리스트는 DP 테이블이라고 부른다. 메모이제이션은 탑-다운 방식에 국한된 표현이다.
다이나믹 프로그래밍이란, 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 효율적으로 해결하는 알고리즘이다. 이렇게 보면 분할 정복과의 차이를 못느낄 수 있는데, 둘의 큰 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있다는 점이다. 즉, 한번 해결했던 문제를 다시 해결해야 하므로, DP테이블, 메모이제이션과 같이 저장하여 꺼내쓰는 방식이 차이점이다.
코딩 테스트에서의 다이나믹 프로그래밍
코딩 테스트에서 가장 중요한 것은, 주어진 문제가 다이나믹 프로그래밍 유형인지 파악하는 것이다. 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면, 다이나믹 프로그래밍을 적용하여 부분 문제들의 중복은 없었는지 확인해보자.
이 부분이 어렵기 때문에 우선 재귀함수(탑-다운)로 비효율적인 프로그램을 작성한 후, 메모이제이션을 적용할 수 있는지 보는 것도 좋은 아이디어이다.
하지만 탑-다운 방식은 재귀를 사용하므로 시스템 상의 스택 크기를 초과하여 recursion depth관련 오류가 발생할 수 있다. setrecursionlimit() 메서드를 통해 해결할 수 있지만 가능하면 바텀-업 방식으로 구현하는 것이 좋긴 하다.