DP(Dynamic Programming)

동적 계획법 : 큰 문제를 작은 문제로 나누어 푸는 방법

- 최적화 이론의 한 기술
- 특정 범위까지의 값을 구하기 위해서 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법

조건

• 작은 문제가 반복되는 경우(겹치는 부분 문제)
  • 동일한 작은 문제들이 반복하여 나타나는 경우
  • 부분 문제의 결과를 저장하여 다시 계산하지 않아야 함
• 같은 문제에 대해서 항상 정답이 같은 경우(최적 부분 구조)
  • 부분 문제의 최적 결과 값을 사용해 전체 문제의 최적 결과를 낼 수 있는 경우

메모이제이션(캐싱)

동일한 계산을 반복해야 할 경우 한번 계산한 값을 메모리에 저장해 두었다가 써서 중복 계산 방지
동적 계획법의 핵심이 되는 기술 → 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식

타뷸레이션

메모이제이션은 결과가 필요해질 때 계산하지만, 타뷸레이션은 필요하지 않은 값도 미리 계산
초기화 오버헤드가 있음

• 계산해둔 값은 시간복잡도가 O(1)

하향식 접근(Top-down) - 메모이제이션

배열[0] 에서 시작이 아닌 배열[n] 의 값을 찾기 위해 위에서부터 호출을 시작해서 배열[0] 의 상태까지 내려간 후 결과를 재귀를 통해 전이시켜 재활용

이미 이전에 계산을 완료한 경우, 저장되어 있는 값을 꺼내서 활용
가장 최근 값을 메모해 두었다고 해서 Memoization 이라고 불림

상향식 접근(Bottom-up) - 타뷸레이션

아래부터 계산을 하고 큰 문제를 해결하는 방식

메모를 위한 배열을 만들고 배열[0] 부터 시작해서 배열[n] 까지 반복문을 통해 점화식으로 결과를 내서 재활용

반복을 통해 배열[0] 부터 하나씩 채우는 과정을 Table-filling 이라고 함
Table 에 저장된 값에 접근해서 활용하기 때문에 Tabulation 이라고 불림

DP 사용하기

1. DP로 풀 수 있는 문제인가?

   작은 문제로 나눠서 풀 수 있는지 확인

2. 문제 변수 파악

   현재 변수에 따라 결과 값을 찾고 전달하여 재사용

3. 점화식 만들기

   동일 변수에 대해서 결과가 동일해야 하고, 결과값을 이용하는 관계식 만들기

4. 메모하기

   변수 값에 따른 결과를 저장, 재사용

5. 기저 상태 파악

   가장 작은 문제 상태 파악

6. 구현하기

문제 풀기

공부한 이론을 가지고 자신감 만땅으로 문제를 풀어봤다!

퇴사 (입사도 안했는데...)

백준 실버3 문제를 한 번 풀어보려고 열심히 문제를 봤는데...
감도 안오고 문제만 뚫어져라 쳐다보고 있었다..

어찌저찌 다른 사람들의 코드를 보며 풀어봤는데... 이러고 그냥 넘어가면 습득되지 않으니 한 케이스에 대해서 직접 써보면서 보자....

public class P14501 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] tArr = new int[n + 1];
        int[] pArr = new int[n + 1];
        int[] resultArr = new int[n + 1];

        StringTokenizer st;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());

            tArr[i] = Integer.parseInt(st.nextToken());
            pArr[i] = Integer.parseInt(st.nextToken());
        }

        for(int j = 0; j < n; j++){
            if(j + tArr[j] <= n){       // 퇴사날 이전이면
                resultArr[j + tArr[j]] = Math.max(resultArr[j + tArr[j]], resultArr[j] + pArr[j]);      // 기존보다 큰 경우 갱신
            }
            resultArr[j + 1] = Math.max(resultArr[j], resultArr[j + 1]);
        }

        System.out.println(resultArr[n]);
    }
}

case
10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6

위의 케이스에 대해서

	0	1	2	3	4	5	6	7	8	9	10
t	5	5	5	5	5	5	5	5	5	5
p	10	9	8	7	6	10	9	8	7	6
dp	0	0	0	0	0	10	10	10	10	10	20

표로 한 번 그려봤다
이렇게 계속해서 갱신해가면서 오늘과 내일, 그리고 t 만큼 뒤의 날짜의 값을 비교하면서 값을 구하는 과정을 DP로 표현할 수 있다!

DP 문제 좀 더 풀어보긴 해야겟다;;;

출처

https://hongjw1938.tistory.com/47
https://galid1.tistory.com/507
https://en.wikipedia.org/wiki/Dynamic_programming