DP, 다이나믹 프로그래밍(동적 계획법)

기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 간단히 말해서 답을 재활용하는 것이다.

DP 문제가 성립할 조건

이럴 때 DP를 사용하면 된다. 단순 재귀코드보다 높은 효율을 갖는 코드를 설계할 수 있다.

• 최적 부분 구조(Optimal Substructure)
  • 상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다.
• 중복되는 부분 문제(Overlapping Subproblem)
  • 동일한 작은 문제를 반복적으로 해결해야 한다.

DP 알고리즘 기법은 무엇인가?

DP 알고리즘 기법은 이미 계산된 결과(하위 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 설계함으로써 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.

DP 구현 방법은 일반적으로 두 가지 방식, Top-down(하향식)과 Bottom-up(상향식)으로 구성된다.

Top-down(하향식)

이 방식은 큰 문제를 해결하기 위해 작은 문제를 해결하는 방식이다. 예를 들어, 피보나치 수열에서 10번째 값을 구하려고 하면, 먼저 9번째 값과 8번째 값을 구하고, 이를 더해서 10번째 값을 구하게 된다. 이런 식으로 큰 문제를 작은 문제로 쪼개서 해결하는 방식이 탑다운 방식이다. 이 때, 한 번 구한 값을 저장해두고 다시 사용하는 방식을 메모이제이션(Memoization)이라고 한다. 이 방식을 사용하면 계산량을 줄일 수 있다.

Bottom-up(상향식)

이 방식은 작은 문제부터 차근차근 답을 도출하는 방식이다. 피보나치 수열에서 10번째 값을 구하려면, 1번째 값과 2번째 값을 먼저 구하고, 이를 바탕으로 3번째, 4번째, ... , 10번째 값을 차례대로 구하게 된다. 이렇게 작은 문제를 해결하면서 점차 큰 문제의 답을 구해가는 방식이 바텀업 방식이다. 이 방식을 사용하면 문제를 시스템적으로 해결할 수 있다.

Top-down VS Bottom-up

두 방식의 주요 차이점은 문제를 해결하는 방향과 접근 방식에 있다. 탑다운 방식은 큰 문제를 작은 문제로 쪼개서 해결하는 반면, 바텀업 방식은 작은 문제부터 시작해서 큰 문제를 해결한다. 그리고 탑다운 방식은 보통 재귀함수를 사용하여 구현하고, 바텀업 방식은 보통 반복문을 사용하여 구현한다.

메모제이션 Memoization

메모이제이션은 DP구현 방법 중 하나로, 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 이를 사용하면 모든 부분 문제가 한 번씩만 계산된다고 보장할 수 있기 때문에 함수 호출 횟수가 엄청나게 감소함을 예상할 수 있다.

메모제이션 특징

같은 문제를 다시 호출 하면 메모했던 결과를 그대로 가져온다
값을 기록해 놓는다는 점에서 캐싱(Cachig)이라고 한다
DP에만 국한된 개념이 아니다. 한 번 계산된 결과를 담아 놓기만 하고 DP가 아닌 다른 방식으로도 사용될 수 있다. (캐싱,메모이제이션)

문제 예시

https://school.programmers.co.kr/learn/courses/18/lessons/1879

• ⓐ를 오른쪽 아래로 하는 정사각형 중 가장 큰 정사각형은 ①, ②, ③ 의 경계 선 중 가장 가까운 값을 변으로 하는 사각형이 가장 큰 정사각형입니다.
  (이 때 ⓐ값은 1이여야 합니다.)

• 이때 ⓐ를 (i, j)라고 했을 때 수식으로 정리한다면 아래와 같습니다.

  	dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1

• 이때 +1은 a의 현재 위치 값입니다.

import java.util.*;

class Solution {
    public int solution(int [][]board) {
        int answer = 0;
        int row = board.length;
        int col = board[0].length;
        int[][] dp = new int[row+1][col+1];

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {
                if (board[i - 1][j - 1] != 0) {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                    answer = Math.max(answer, dp[i][j]);
                }
            }
        }


        return (int) Math.pow(answer, 2);
    }
}