다이나믹 프로그래밍 (Dynamic Programming)

한창 백준 문제 풀 때 DP의 개념에 대해 정리한 글이다. 이번 글에서는 추가적으로 알게 된 것들만 정리해보자.

https://aodtns.tistory.com/16?category=993972

백준 1003번 - 피보나치 함수

 

DP를 사용하기 위한 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 

 

분할 정복(Divide and Conquer)과의 차이점

분할 정복과 비슷한 느낌이지만 DP는 문제들이 서로 영향을 미치고 있다는 점이다.

예를 들어 퀵 정렬에서 Pivot이 자리를 변경해서 자리를 잡으면 그 Pivot의 위치는 바뀌지 않고 그 Pivot을 다시 처리하는 부분 문제는 존재하지 않는다. 합병 정렬에서도 마찬가지로 부분 문제를 쪼갠 뒤 정렬을 하면 그 부분 문제에 대해서 다시 처리하지 않는다.

 

메모이제이션과 DP

DP의 전형적인 형태는 Bottom Up 방식이다. 이 방식에서 사용되는 결과 저장용 리스트는 DP 테이블이라고 하며, 메모이제이션은 Top down 방식에 국한되어 사용되는 표현이다. 

DP와 메모이제이션의 개념을 혼용해서 사용하는 경우도 있는데, 엄밀히 말하면 메모이제이션은 그저 이전 결과를 기록해 놓는다는 넓은 개념이므로 DP와는 별도의 개념이다. 

 

 

문제를 접근하는 방식

특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸린다면 DP를 사용하기 위한 조건을 생각해보고 부분 문제들의 중복 여부를 확인해보자.

일단 Top Down 형태로 코드를 작성한 뒤에 부분 문제에서 구한 답이 큰 문제에서도 적용될 수 있다면, 즉 메모이제이션을 적용할 수 있으면 코드를 개선하는 방법도 좋은 방법이다.