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

동적계획법 (Dynamic Programming) 이란?

최적화 문제를 위해 고안된 기법으로 복잡한 문제보다 간단한 여러 개의 부분 문제로 나누어 해결합니다.

중요한 점은 한 번 계산된 부분 문제의 답을 저장해 두어 나중에 같은 부분 문제의 답을 원할 시, 반복되는 연산 없이 바로 저장해 둔 걸 꺼내 쓸 수 있도록 하는 것이 핵심입니다.

주로 중복되는 부분 문제(Overlapping Subproblem)와 최적 부분 구조 (Optimal Substructure)를 가지고 문제들을 풀 때 사용됩니다.

또한,

동적 계획법을 설계할 때는 가장 중요한 것이 현재 문제의 상태와 문제와 부분 문제 간의 관계 또는 전이를 파악하는 것입니다.

문제들 간의 관계 또는 전이를 정확하게 파악한다면 알고리즘의 정당성을 얻을 수 있고,

시간 복잡도는 상태의 수와 한 상태의 답을 결정하기 위한 시간에 비례하므로

이를 잘 고려하여 문제 간의 상태와 관계를 잘 파악하는 것이 중요합니다.

 

 

동적 계획법의 조건 ?

동적 계획법을 적용하려면 2가지 속성을 만족시켜야 합니다.

1. 부분 반복 문제 (Overlapping Subproblem)

2. 최적 부분 구조 (Optimal Substructure)

 

중복되는 부분 문제

주어진 무제를 여러 개의 부분 문제로 나누어 풀 때, 같은 부분 문제의 답을 여러 번 계산을 하는 경우가 있습니다.

이런 부분 문제들은 중복이되는데, 그 중복되는 부분을 Overlapping Subproblems라고 합니다. 

중복 되는 부분 문제를 단 한 번만 계산하여 알고리즘의 속도를 최적화하는 방식입니다.

 

최적 부분 구조

최적화 문제에 적용하려면 동적 계획법에서 Overlapping Subproblems 말고,  Optimal Substructure 이라는 특성이 필요합니다.

어떤 문제가 최적 부분 구조를 가진다는 것은?

주어진 문제의 최적해를 그 문제의 부분 문제들의 최적해를 통해 얻을 수 있다는 것을 말합니다.

 

동적 계획법의 구현은 ?

동적 계획법은 문제의 상태와 문제들 간의 관계 파악이 끝났따면, 이를 코드로 구현해야합니다.

두 가지 방법이 있습니다.

하나는 재귀 함수를 이용하는 Top-down 방식이고

다른 하나는 반복문을 통해 DP 테이블을 채워 나가는 Bottom-up 방식이 있습니다.

두 방식은 각기 다른 장단점이 존재하니, 잘 알아두고 문제의 특성에 맞게 사용하면 됩니다.

Top-Down

위 코드는 재귀함수를 이용하여 피보나치수열을 구현하는 문제입니다. 

이 코드에서 메모이제이션 기법(캐싱)을 사용하였습니다.

메모이제이션이란? 동적계획법에서 구현하는 방법 중 한 가지로 한 번 구현한 결과를 메모리 공간에 메모리해두고, 같은 식을 다시 호출하면 메모리한 결과를 그대로 가져오는 기법입니다.

이 메모이제이션 부분이 없다면 너무 많이 중복해서 계산하게 되어 복잡도 효율이 떨어집니다..

중복 계산 방지를 위해서 사용했습니다.

 

Bottom-Up

위 코드는 부분 문제들 간의 의존성을 파악하여 먼저 해결되어야 할 부분 문제부터 풀어나갑니다.

피보나치수를 반복문으로 DP 배열을 채워나가는 방식입니다.

이 방식은 표를 채워나가는 것처럼 보여 Tabulation 이라고도 합니다.

 

Top-down / Bottom-up 방식 비교를 통한 장단점은?

Top-down 

장점 : 대체로 코드를 직관적으로 이해할 수 있으며 필요한 부분 문제만을 계산하기 때문에 원래 Bottm-up 방식이 빠르지만, 때론 Top-down 방식이 빠를 때가 있습니다.

단점: 함수 호출, 반환 방식으로 인하여 오버헤드가 있기 때문에 Bottom-up 이 더 빠르고, 가끔 메모리 제한이 엄격할 땐 문제를 해결 못합니다.

Bottom-up

장점 : Top-down 방식보다는 빠르고, 슬라이딩 윈도우 기법을 이용하여 메모리 사용량을 절약하는 방법을 사용할 수 있습니다.

단점 : 부분 문제들 간의 의존성 파악을 정확히 해야하며, 이에 맞는 DP 테이블을 채워나가야합니다...(자아아알해야지요)

 

참고