[알고리즘] DP(Dynamic Programming) 이란? (DP 알고리즘)

DP(Dynamic Programming)

💡 DP Dynamic Programming : 동적계획법 (동적 프로그래밍) 복잡한 문제를 재귀적인 방법으로 해결하는 알고리즘 설계 기법이다. 주로 ⭐최적화 문제에 많이 사용되며, 부분 문제의 해답을 저장해서 같은 계산의 반복을 피해 계산 시간을 줄여준다.

• 핵심 : 이전에 계산한 값을 다음 단계에서 써 먹는다는 사실!
• 핵심 : 문제의 재귀적인 구조를 찾아라!
• DP 알고리즘은 중복된 계산을 줄인다는 점에서 굉장히 효율적인 알고리즘이다.

 

DP의 주요 방법

1. 탑다운(Top-down) 접근법 (메모이제이션) : 재귀를 사용하여 큰 문제에서 작은 문제로 나아가며, 각 단계의 결과를 캐시(메모리)에 저장한다.
2. 바텀업(Bottom-Up) 접근법 (타뷸레이션) : 반복문을 사용하여 작은 문제부터 시작해 큰 문제로 나아가며, 각 단계의 결과를 테이블(배열 등)에 저장한다.

 

DP의 접근법

1. 문제를 부분 문제로 분할하기 : 복잡한 문제를 작고 관리 가능한 부분 문제로 분리한다.
2. 재귀적 구조 파악하기 : 부분 문제가 어떻게 연관되어 있는지 파악한다.
3. 점화식 도출하기 : 부분 문제의 해결책을 결합하여 원래 문제의 해결책을 구할 수 있는 수학적인 식을 만든다.
4. 메모이제이션 또는 타뷸레이션 활용하기 : 각 부분 문제의 해답을 저장하고, 메모이제이션 또는 타뷸레이션을 이용한다.
5. 문제 해결하기 : 가장 작은 문제부터 해결을 시작한다.

 

DP Quiz (예제 백준 1463번)

🥇 Bottom-Up 으로 아래 → 위로 올라가면서 푸는 문제

🛠 1로 만들어야 하는 n을 입력 받은 뒤, 2~n 까지 수에 대한 최소 연산 횟수를 DP 테이블에 차례로 저장한다.

가령, n=2 일 경우, 2를 1로 만드는 1)-1 빼기 2)2로 나누기 연산 중에 최소 연산 횟수를 구한다. 최소 연산 횟수를 구하기 위해서는 f(1) 의 값이 필요하다.
- 2-1을 1로 만들기 위한 최소 연산 횟수 dp[n-1] + 1 → dp[1] + 1 → 1
- 2/2을 1로 만들기 위한 최소 연산 횟수 dp[n/2] + 1 → dp[1] + 1 → 1

즉, n=2 의 최소 연산 횟수는 1 이다.

for(int i=2; i <=n; i++) {
    dp[i] = dp[i-1] +1; //1을 빼는 연산이 가장 작다고 가정한다. 
    if(i%2==0) { //2로 나누어 떨어지는지 확인
        dp[i] = Math.min(dp[i], dp[i/2]+1); //현재 저장된 연산 과정과 2로 나누는 연산 중 연산 횟수가 더 작은걸 저장한다. 
        //dp[2]=1 , dp[1]+1 = 0+1 = 1 dp[2] 는 결국 1 
    }
    if(i%3==0) {
        dp[i] = Math.min(dp[i], dp[i/3]+1); //현재 저장된 연산 vs 3으로 나누는 연산 비교 
    }
}

System.out.println(dp[n]);

 

*가령, n=6 일 때
f(2)
dp[2] = ?
dp[2-1] +1 vs dp[2/2] +1
→ 1 vs 1
→ dp[2] = 1

f(3)
dp[3] = ?
dp[3-1] +1 vs dp[3/3] + 1
→ dp[2] + 1 vs dp[1] + 1
→ 2 vs 1
→ dp[3] = 1

f(4)
dp[4] = ?
dp[4-1] + 1 vs dp[4/2] + 1
→ dp[3] + 1 vs dp[2] + 1
→ 1+1 vs 1+1
→ dp[4] = 2

 

f(6)을 구하기 위해서는 f(2) 부터 f(5) 까지의 dp 테이블 값이 앞서 구해져야한다.

→ 2~6 까지의 작은 문제로 쪼개는 DP 문제라는 것을 알 수 있다. (DP 알고리즘으로 풀 수 있는걸 파악하는 것이 중요)

 

DP 대표 문제 

- 백준 1463번 : 1로 만들기 

- 백준 11726번 : 2xn 타일링 https://backshren20.tistory.com/673

[백준 JAVA] 11726번 풀이 - 2xn 타일링