01_DynamicProgramming

PLO·2023년 5월 27일

CS/Algorithm

1. Dynamic Programing이란?

다이나믹 프로그래밍(Dynamic Programming)은
복잡한 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법입니다.
이 기법은 주어진 문제를 여러 하위 문제(subproblem)로 분할하여 각 하위 문제의 해를 계산하고,
그 해들을 결합하여 전체 문제의 해를 도출하는 방식으로 동작합니다.
다이나믹 프로그래밍은 중복되는 하위 문제들을 반복해서 해결함으로써
전체적인 문제 해결 과정을 효율적으로 수행할 수 있습니다.
다이나믹 프로그래밍은
최적 부분 구조(Optimal Substructure)와
중복되는 하위 문제(Overlapping Subproblems)의 특성을 가지고 있습니다.
최적 부분 구조는 큰 문제의 최적해가 작은 문제의 최적해로부터 구성될 수 있다는 의미입니다.
중복되는 하위 문제는 작은 문제들을 반복해서 해결해야 할 때,
동일한 하위 문제들이 반복해서 발생한다는 것을 의미합니다.

다이나믹 프로그래밍은 문제마다 적용되는 구체적인 접근 방법과 알고리즘이 다를 수 있으며,
문제의 특성과 요구사항에 따라 적합한 다이나믹 프로그래밍 기법을 선택하여 사용해야 합니다.

2. Dynamic Programing 단계

다이나믹 프로그래밍(Dynamic Programming)은 다음과 같은 단계를 거쳐 문제를 해결합니다.

문제를 하위 문제로 분할(Divide)
주어진 문제를 더 작은 하위 문제(subproblem)들로 분할합니다.
이때, 하위 문제들은 중복되거나 상호 의존적인 성질을 가집니다.
작은 문제의 해 구하기(Solve)
가장 작은 하위 문제부터 시작하여 각 하위 문제의 해를 구합니다.
작은 문제의 해는 상위 문제의 해결에 필요한 중간 단계로 활용됩니다.
상위 문제의 해 구하기(Combine)
작은 문제들의 해를 이용하여 상위 문제의 해를 구합니다.
작은 문제들의 해를 조합하거나 점화식 등을 활용하여 상위 문제를 해결합니다.
전체 문제의 해 구하기(Solve)
상위 문제의 해를 구하면서 전체 문제의 해를 도출합니다.
이때, 중복되는 하위 문제를 효율적으로 처리하며, 중간 결과를 저장하여 재사용합니다.

3. Dynamic Programing 의 충족 요소

최적 부분 구조(Optimal Substructure)
큰 문제의 최적해가 작은 문제의 최적해로부터 구성될 수 있어야 합니다.
즉, 작은 문제들의 최적해를 조합하여 전체 문제의 최적해를 얻을 수 있어야 합니다.
중복되는 하위 문제(Overlapping Subproblems)
작은 문제들을 반복해서 해결해야 할 때, 동일한 하위 문제들이 반복해서 발생해야 합니다.
이렇게 하위 문제들이 중복되어야 다이나믹 프로그래밍의 효율성을 발휘할 수 있습니다.
하위 문제의 독립성(Independent Subproblems)
각 하위 문제는 독립적이어야 하며,
하위 문제의 해를 구하기 위해 다른 하위 문제의 해에 의존해서는 안 됩니다.
이를 통해 하위 문제들을 독립적으로 해결할 수 있습니다.
메모리/저장 공간(Memory/Storage)
중복되는 계산을 피하기 위해 작은 문제들의 해를 저장하고 재사용해야 합니다.
이를 위해 적절한 메모리나 저장 공간을 사용하여 중간 결과를 저장할 수 있어야 합니다.

4. Dynamic Programing의 장점

중복 계산을 피할 수 있음
다이나믹 프로그래밍은 하위 문제들을 효율적으로 해결하기 위해 중복 계산을 피할 수 있습니다.
작은 문제의 해를 저장하고 재사용함으로써, 동일한 하위 문제를 반복해서 계산할 필요가 없어집니다. 이는 계산량을 줄이고 실행 속도를 향상시킬 수 있습니다.
최적 부분 구조 활용 가능
다이나믹 프로그래밍은 최적 부분 구조(Optimal Substructure)를 활용할 수 있는 문제에 효과적입니다. 최적 부분 구조란 큰 문제의 최적해가 작은 문제의 최적해로부터 구성될 수 있는 성질을 말합니다.
작은 문제의 최적해를 구한 뒤, 이를 조합하여 전체 문제의 최적해를 구할 수 있습니다.
작은 문제의 해를 활용하여 전체 문제의 해 도출 가능
다이나믹 프로그래밍은 작은 문제의 해를 활용하여 전체 문제의 해를 구할 수 있습니다.
작은 문제들을 해결하면서 중간 결과를 저장하고 활용함으로써, 전체 문제의 해를 구할 수 있습니다.
이는 상위 문제의 해를 계산하는 데에 필요한 중간 단계의 계산 결과를 재사용함으로써
효율적인 문제 해결이 가능합니다.
다양한 문제에 적용 가능
다이나믹 프로그래밍은 다양한 종류의 문제에 적용될 수 있습니다.
최적화 문제나 조합 최적화 문제뿐만 아니라, 그래프 알고리즘, 문자열 처리, 순차적 결정 문제 등
다양한 문제에 다이나믹 프로그래밍을 적용할 수 있습니다.
따라서, 다이나믹 프로그래밍은 범용적인 문제 해결 기법으로 활용될 수 있습니다.
메모리를 사용하여 중간 결과 저장 가능
다이나믹 프로그래밍은 중간 계산 결과를 저장함으로써 효율적인 문제 해결을 가능케 합니다.
작은 문제의 해를 저장하는 메모리를 사용하여 중간 결과를 저장하고,
필요할 때마다 재사용할 수 있습니다. 이를 통해 중복 계산을 피하고,
계산 시간을 단축시킬 수 있습니다.

5. Dynamic Programing의 단점

모든 하위 문제를 해결해야 함
다이나믹 프로그래밍은 모든 하위 문제를 해결해야 하는 단점이 있습니다.
큰 문제를 작은 하위 문제로 분할하여 해결하는데, 작은 문제들의 해를 구하기 위해서는
이전에 발생한 모든 작은 문제들의 해를 계산해야 합니다.
이는 문제의 크기에 따라 계산량이 급격하게 증가할 수 있으며,
실행 시간과 메모리 요구량이 증가할 수 있습니다.
모든 문제가 다이나믹 프로그래밍에 적합하지는 않음
다이나믹 프로그래밍은 모든 문제에 적용될 수 있는 것은 아닙니다.
다이나믹 프로그래밍을 적용하기 위해서는 최적 부분 구조와
중복되는 하위 문제의 특성이 충족되어야 합니다.
때로는 이러한 특성을 가지지 않는 문제도 있을 수 있으며,
다른 알고리즘 설계 기법을 사용해야 할 수도 있습니다.
하위 문제의 정의와 점화식 구성이 어려울 수 있음
다이나믹 프로그래밍을 사용하려면 하위 문제들의 정의와
점화식(Recurrence Relation)을 구성해야 합니다.
하위 문제의 정의와 점화식을 올바르게 구성하는 것은 어려울 수 있으며,
실수를 할 가능성이 있습니다. 이를 위해서는 문제에 대한 충분한 분석과 설계가 필요합니다.
추가적인 메모리 요구
다이나믹 프로그래밍은 중간 계산 결과를 저장하기 위한 메모리가 필요합니다.
작은 문제의 해를 저장하고 재사용하기 위해 메모리를 사용해야 하므로,
문제의 크기가 커질수록 메모리 요구량이 증가할 수 있습니다.
따라서, 메모리 사용량을 고려해야 하는 경우에는 추가적인 메모리 비용이 발생할 수 있습니다.
모든 문제에 대해 최적해를 보장하지 않음
다이나믹 프로그래밍은 주어진 문제에 대해 최적해를 구할 수 있을 때에만 적용됩니다.
최적 부분 구조를 가지는 문제에 대해서는 최적해를 보장할 수 있지만,
모든 문제에 대해서 항상 최적해를 보장하는 것은 아닙니다.
따라서, 최적해를 구할 수 있는지 분석하는 과정이 필요합니다.
점화식

점화식(Recurrence Relation)은 다이나믹 프로그래밍에서 사용되는 수학적인 식으로,
주어진 문제를 작은 하위 문제들로 분할하는 데에 활용됩니다.
점화식은 하위 문제들 간의 관계를 나타내는 식으로서,
작은 문제의 해와 상위 문제의 해 사이의 관계를 정의합니다.

점화식은 일반적으로 재귀적인 형태를 가지며,
작은 문제의 해를 이용하여 상위 문제의 해를 구하는 방법을 정의합니다.
작은 문제와 상위 문제 사이의 관계를 나타내기 위해 수식, 등식, 부등식 등으로 표현됩니다.
```
피보나치 수열의 점화식
F(n) = F(n-1) + F(n-2) 
```