[이것이 취업을 위한 코딩테스트다] chap08 - 다이나믹 프로그래밍

다이나믹 프로그래밍

 

다이나믹 프로그래밍은 최적의 해를 구하기에 연산 속오데 한계가 있고, 메모리 공간을 사용할 수 있는 데이터 개수도 한정적일 때 중복되는 연산을 줄이면서 공간을 최대한으로 활용하기 위해 탄생되었다. 동적 계획법이라고도 하며, 2가지 방식(탑다운과 보텀업)이 있으며 메모이제이션 기법이 주료 사용된다.

 

위와 같이 피보나치 수열이 있을 때 아래와 같이 점화식을 나타날 수 있다.

반복되는 값이 있을 때, 점화식을 통해 나타내고 이 점화식을 코드로 구현하면 다이나믹 프로그래밍 유형을 풀 수 있다.

피보나치 수열을 이진 탐색 트리로 구현했을 때, 위와 같이 동일한 함수가 반복적으로 호출되는 것을 알 수 있다. 불필요한 연산을 수행함으로써 연산 속도가 느려지고 메모리 공간을 많이 차지하는 단점이 있다.

 

다만 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.

- 큰 문제를 작은 문제로 나눌 수 있다.

- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

이 문제를 메모이제이션 기법을 통해 구현할 수 있는데 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. caching이라고도 하며, 리스트에 정보를 저장하여 다이나믹 프로그래밍을 재귀적으로 수행하다가 같은 정보가 필요할 때 리스트에서 꺼내 가져오는 형식이다.

 

 

 

vs 분할 정복

 

분할 정복과 다이나믹 프로그래밍은 비슷한 점이 많으나 문제들이 서로 영향을 미치고 있다는 점이 다르다. 퀵 정렬을 예로 들면, 한 번 기준 원소(pivot)가 자리를 변경해서 자리를 잡게 되면, 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다. 반면 다이나믹 프로그래밍은 한 번 해결했던 문제를 다시금 해결한다는 점이 특징이다. 그렇기 때문에 이미 해결된 부분 문제에 대한 답을 저장해 놓고, 이 문제는 이미 해결이 됐던 것이니 다시 해결 필요가 없다고 반환하는 것이다.

 

 

탑다운 vs 보텀업

 

탑다운 방식은 재귀 함수를 이용하여 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이고, 단순히 반복문을 이용하여 작은 문제부터 차근차근 답을 도출하는 방식을 보텀업 방식이라고 말한다. 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이며, 메모이제이션과 결합해 리스트 형식으로 값을 저장한다.