동적 계획법(Dynamic Programming)
복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 각 하위 문제의 해결책을 저장하고, 이를 활용하여 전체 문제의 해결책을 구하는 방법
중복되는 연산을 반복하지 않도록 하여, 실행 시간을 줄여 프로그램 효율성을 높이기 위해 사용되는 알고리즘이다.
동적 계획법의 특징
중복된 하위 문제: 동적 계획법은 중복된 하위 문제의 해결책을 저장함으로써 효율적으로 문제를 해결한다.
최적 부분 구조 (Optimal Substructure): 큰 문제의 최적해가 그 문제의 하위 문제의 최적해에서 구해질 수 있다.
메모이제이션 (Memoization) 또는 테이블화 (Tabulation): 탑다운은 메모이제이션, 바텀업은 테이블화 방식을 사용하여 계산 결과를 저장한다.
동적 계획법의 사용 조건
1. Overlapping Subproblems(겹치는 부분 문제)
동적 계획법은 기본적으로 문제를 나누고, 그 문제의 결과값을 재활용하여 문제 전체의 답을 구하므로 동일한 작은 문제들이 반복하여 나타나는 경우에 효율적이다.
2. Optimal Substructure(최적 부분 구조)
부분 문제의 최적 결과값을 사용해 전체 문제의 최적 결과를 도출할 때 사용한다.
같은 문제는 항상 정답이 같고, 작은 문제에서 반복적으로 일어난다는 점을 활용해 큰 문제를 해결한다.
동적 계획법의 구현 방식
탑다운 (Top-Down) 방식 (메모이제이션)
- 재귀를 사용하여 문제를 해결한다. 큰 문제를 해결하기 위해 작은 문제로 나눠 각각의 작은 문제를 재귀적으로 해결한다.
- 한 번 계산한 하위 문제의 결과는 메모리에 저장(메모이제이션)하여, 동일한 하위 문제가 발생했을 때 재계산 없이 메모리에서 결과를 가져온다.
- 가독성이 좋지만 코드 작성이 힘들다.
바텀업 (Bottom-Up) 방식
- 가장 작은 문제부터 시작하여 차례대로 상위 문제의 해결책을 구한다.
- 일반적으로 반복문을 사용하여 구현하며, 각 단계에서의 계산 결과를 배열에 저장하며 최종적인 문제의 해결책을 도출한다.
- 해결이 용이하지만, 가독성이 떨어진다.
동적 계획법 구현까지의 과정
1. DP로 풀 수 있는 문제인지 확인
- Overlapping Subproblems(겹치는 부분 문제)
- Optimal Substructure(최적 부분 구조) 두 가지 조건을 만족하는지 확인한다.
2. 문제의 변수 파악 - DP는 문제의 변수에 따라 결과값을 찾고, 찾은 결과값을 재사용하기 때문에 변수를 파악한다.
3. 변수 간 관계식(점화식) 생성 - 하위 문제의 해결책을 이용해 다음 하위 문제를 해결할 변수 간 관계식을 생성한다. 점화식은 문제를 재귀적으로 해결하는 데 사용한다.
4. 결과 저장 - 메모이제이션(Memoization) 또는 테이블화(Tabulation)를 통해 결과를 저장한다.
5. 문제 해결 - Bottom-Up (Tabulation 방식 - 반복문 사용)
- Top-Down (Memoization 방식 - 재귀 사용) 두 가지 방법과 정의된 점화식으로 하위 문제들을 해결한다.
1. 피보나치 수열 (Fibonacci Sequence)
문제 설명:
피보나치 수열에서 첫 번째와 두 번째 수는 각각 0과 1이며, 그 이후의 모든 수는 바로 앞 두 수의 합으로 이루어진다. 즉, F(0)=0, F(1)=1이고, F(n)=F(n-1)+F(n-2) (n≥2)다.
동적 계획법 접근 방법:
바텀업 방식: 0과 1로 시작하여, 배열에 이전 두 수의 합을 계속해서 저장해 나가며 n번째 피보나치 수를 구한다.
탑다운 방식 (메모이제이션): n번째 피보나치 수를 구하기 위해 재귀 함수를 사용하되, 한 번 계산한 값은 배열에 저장하여 중복 계산을 방지한다.
2. 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS)
문제 설명:
주어진 수열에서 어떤 원소들을 삭제하고 남은 수열 중, 모든 원소가 증가하는 순서를 유지하는 수열의 최대 길이를 찾는다.
동적 계획법 접근 방법:
배열의 각 위치에 대해 그 위치를 마지막으로 하는 최장 증가 부분 수열의 길이를 저장한다.
각 위치에서 그보다 앞에 있는 원소들 중 작은 원소들을 찾고, 그 중 최대 길이에 1을 더해 현재 위치의 최대 길이를 계산한다.
3. 최소 코인 문제 (Minimum Coin Change)
문제 설명:
특정 금액을 만들기 위해 필요한 최소한의 동전 개수를 구한다. 각 동전은 무한히 많다고 가정한다.
동적 계획법 접근 방법:
금액을 만들기 위한 최소 동전 개수를 저장하는 배열을 사용한다.
각 금액에 대해 가능한 모든 동전을 시도하며, 해당 동전을 사용했을 때와 사용하지 않았을 때의 최소값을 계산해 배열을 갱신한다.
4. 배낭 문제 (Knapsack Problem)
문제 설명:
한정된 무게를 가진 배낭에 최대 가치를 가지도록 물건을 담는다.
각 물건은 무게와 가치를 가지고 있으며, 물건은 쪼갤 수 없다. (0-1 배낭 문제)
각각의 무게에 대해 최대 가치를 저장하면서 전체 문제의 최적해를 구한다.
동적 계획법 접근 방법:
배열을 사용하여 특정 무게에서 담을 수 있는 물건들의 최대 가치를 저장한다.
각 물건에 대해 배낭의 무게 한도 내에서 이 물건을 추가했을 때와 추가하지 않았을 때의 최대 가치를 비교하여 배열을 갱신한다.
참고
알고리즘 - Dynamic Programming(동적 계획법)
github.com/gyoogle/tech-interview-for-developer
