동적 계획 알고리즘, 동적 프로그래밍

동적 계획(Dynamic Programming)알고리즘은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.

동적 계획 알고리즘은 먼저 입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘이다.

동적 계획 알고리즘에는 부분문제들 사이에 의존적 관계가 존재한다.

이러한 관계는 문제 또는 입력에 따라 다르고, 대부분의 경우 뚜렷이 보이지 않아서 '함축적인 순서'라고 한다.

 

동적 프로그래밍은 문자열과 같이 왼쪽에서 오른쪽으로 순서가 정해진 항목과 관련된 문제에서 최적의 풀이를 구하기 위한 것으로, 매우 강력하면서도 다양한 분야에서 쓰일 수 있다.

동적 프로그래밍을 이용해서 똑같은 계산을 반복하는 것을 방지하기 위해 계산 결과를 저장하면서(효율을 높일 수 있다) 모든 가능성을 체계적으로 검색(이렇게 하면 올바른 해가 나오게 되어 있다)하는 알고리즘을 직접 만들 수 있다.

동적 프로그래밍 알고리즘은 더 작은 문제에 대한 풀이를 바탕으로 전체 문제에 대한 풀이를 기술하는 재귀적인 알고리즘/함수에 의해 정의된다.

지금까지 우리가 배운 것 중에는 백트래킹과 그래프에서의 깊이 우선 검색이 재귀적이라고 할 수 있다.이렇게 재귀적인 알고리즘을 만들 때는 효율을 위해 이미 계산한 것을 다시 계산하는 것을 피해야 하는데, 그러기 위해서는 계산한 정보를 저장해야 한다. 그래프에서 사용하는 깊이 우선 검색이 효율적일 수 있었던 이유는 무엇일까? 이미 한 번 방문했던 정점은 따로 표시를 해서 다시 방문하지 않아도 되도록 했기 때문이다.

백트래킹을 하려면 왜 계산ㅇ르 많이 해야 하는 것일까? 전에 검색하지 않은 것 뿐 아니라 모든 가능한 경로/풀이를 검색하기 때문이다.동적 프로그래밍은 부분적인 결과를 저장함으로써 재귀적인 알고리즘을 효율적으로 구현하는 기법이다. 가장 중요한 포인트는, 일반적인 재귀 알고리즘에서 이미 풀었던 부분 문제를 반복해서 푼다는 사실을 찾아내는 것이다.

만약 알고리즘이 그런식으로 작동하다면, 매번 다시 계산하는 대신 표 같은 데 결과를 저장해두면 알고리즘의 효율을 향상시킬 수 있다.동적 프로그래밍 알고리즘은 재귀 알고리즘을 바탕으로 한다.

효율적인 동적 프로그램이 알고리즘에서는 정렬된 값을 입력 받아야 되는 경향이 있다.보통 동적 프로그래밍 테이블을 저장하기 위한 전역 배열을 설정한다.