DP (dynamic programming)

DP 문제 유형의 발상 :

Overlapping Subproblem(문제 P는 A1,A2,... 로 같은 구조로 쪼깨짐.)
Optimal Substructure (답 A는 A1,A2,... An을 통해 구함) -> 메모지에이션

*하나의 커다란 문제가 작은 유사한 문제들로 점진적으로 분리된다.! 캐싱을 통해서 풀수 있겠다! 라는 느낌.

풀이방법 : 1.Top Down : 문제를 작은 문제로 나눈다. -> 작은 문제를 푼다. -> 작은 문제를 풀었으니 전체 문제를 이제 푼다.

예) n을 구하기 위해서 n-1, n-2를 구하는 재귀함수를 호출한다.
2.Bottom Up : 문제를 크기가 작은 문제부터 차례대로 푼다. -> 문제의 크기를 조금씩 크게 만들면서 문제를 점점 푼다. -> 큰 문제가 풀린다.
예) n을 1에서부터 쌓아올라가는 식을 바탕으로 for을 돌려 최종 답을 구한다.

풀이 순서 :

1. d[i] 를 문장으로 정의 한다
1. 변수의 개수 만큼 메모배열 만들기
1. d[i] 관한 식을 찾는다. 초기값 및 i 범위를 설정한다.
1. 탑다운 or 바텀업 으로 푼다.

기본문제

1, 2, 3 더하기 https://www.acmicpc.net/problem/9095

재귀함수로도 풀리지만 DP로 접근해서 풀 수 있다.
n이 작은것부터 쌓아올려가는 bottom up 문제이다.
특이점 : d[n] = d[n-1] + d[n-2] + d[n-3]에서 d[n-1]과 d[n-3]은 포함관계가 아니다.!
- 문뜩 d[n-1]이 뭔가 d[n-3]의 경우의 수를 포함하고 있는게 아닌가? 라고 생각했지만 완전 베타적이었다.
- 그 이유는 1,2,3 더하기로 구분되어 경우의 수가 쌓이기 때문이다.
- 1 - 1 <-- 반드시 3을 접미로 붙여서 4를 만들것.
- 2 - 11, 2 <-- 반드시 2을 접미로 붙여서 4를 만들것.
- 3 - 12, 111, 21, 3 <-- 반드시 1을 접미로 붙여서 4를 만들것.
- 4 - 13, 112, 22, 121, 1111, 211, 31

// 재귀 버전
int go(int sum, int goal)
{
    if (sum == goal)
        return 1;
    if (sum > goal)
        return 0;
    int ans_node = 0;
    for (int i = 1; i <= 3; i++)
    {
        ans_node += go(sum + i, goal);
    }
    return ans_node;
}

// dp버전
int dp(int n)
{
    d[1] = 1;
    d[2] = 2;
    d[3] = 4;
    for (int i = 4; i <= n; i++)
    {
        d[i] = d[i - 1] + d[i - 2] + d[i - 3];
    }
    return d[n];
}

// 1.d정의
// d[i] : i를 1,2,3합으로 나타내는 방법

// 2.답을 정의
// 정답 : d[n]을 구하면 된다.

// 3.연관관계 정의
// d[10] = d[9] + 1
// d[10] = d[8] + 2
// d[10] = d[7] + 3
// --> d[n] = d[n-1] + d[n-2] + d[n-3] (n>=4)

// 4.초기값
// d[0] = 0 , d[1] = 1, d[2] = 2, d[3] = 4

const T = Number(readline());
const d = Array(11).fill(0);
(d[0] = 0), (d[1] = 1), (d[2] = 2), (d[3] = 4);
for (let k = 4; k <= 10; k++) {
  d[k] = d[k - 1] + d[k - 2] + d[k - 3];
}

for (let i = 0; i < T; i++) {
  const ans = Number(readline());
  console.log(d[ans]);
}

문제 예시: 피보나치 수열

재귀함수를 작성한다. 중간 정답을 메모한다.

const memo = {};

function fibonacci(n) {
  // 메모이제이션: 이미 계산한 결과가 있으면 반환
  if (n in memo) return memo[n];
  // 기본 경우
  if (n === 0) return 0;
  if (n === 1) return 1;
  // 피보나치 수 계산
  memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
  return memo[n];
}

// 예제: n = 10
const n = 10;
console.log(fibonacci(n)); // 출력: 55

문제유형 - 점화식, if, min, max, sum ( 가장 기본 )

- 피보나치 문제

d[ i ] : i 번째 피보나치 수
d[ i ] = d[ i -2 ] + d[ i - 1]
특이점 : 숫자가 너무 크기때문에, 문자열을 통해 저장을 하고, 문자열간에 + 연산을 하는 함수를 작성. ( python 시간초과 / but 정수 무제한 )


- 1로 만들기

d[ i ] : i 를 1로 만드는데 필요한 최소 연산 횟수 : 연산은 -1, //2, //3 세 종류가 있다. d[ i ] = min ( d [ i - 1 ] , d [ i // 2 ] , d [ i // 3 ] ) + 1

특이점 : python에서 stack을 10**6번 호출하니 메모리 초과가 뜬다. 무조건 bottom up 으로 for문으로 돌려야했음.

- 타일 문제

d [ i ] = 2i 번째 타일을 만드는 방법의 수 ( 타일의 길이를 overlap ) d [ i ] = d[ i -1 ] + d[ i -2 ] d [ i ] = d[ i -1 ] + d[ i -2 ] 2

- 1,2,3 더하기

d[ i ] = i 를 1,2,3 으로 나타내는 경우의 수라 정의 ( 작은 수부터 만들면서 overlap ) d[ i ] = d[ i - 1 ] + d[ i - 2 ] + d[ i - 3 ]

-파도반 수열

특이점

dp 공식을 찾는데 기하적 도형을 이용한다.
그리고 dp 공식이 두가지가 나온다.

d[ n ] : n번째 삼각형의 한변의 길이 d[ n ] = d[ n-2 ] + d[ n-3 ] d[ n ] = d[ n-1 ] + d[ n-4 ]

암호 코드 https://www.acmicpc.net/problem/2011

특이점so

dp 공식인데, 조건을 조금 꼼꼼히 따져야함
basecase 조정이 필요함 : 초기값은 특이하게 1로 셋팅, 원본데이터 조정

d [ n ] += ( S [ n ] 가 1~9 일 때 d[ n -1 ] , 그 외는 0 ) += ( S [ n-1:n+1] 이 10~26일 때 d[ n - 2 ] , 그 외는 0 )

문제유형 - 지금까지의 모든 D를 살펴야 하는 경우

- 붕어빵 판매하기

d[ i ] = i개의 붕어빵을 팔아서 얻는 최대 수익 d[ i ] = MAX ( d[ 0 ] + p [ i ], d[ 1 ] + p[ i-1 ], ….. , d [ i -1 ] + p [ 1 ] )

특이점 : 다음의 D로 넘어가려면, 모든 D를 탐색해야함.

- 타일 채우기

3N 타일을 21,1*2 타일로 채워야 한다.

d[ n ] = 3*N 타일을 채웠을때 가능한 경우의 수

특이점

- for문으로 안보이는 블럭부터 채워야 한다.
- 홀수인 경우는 무조건 0 이다. 
- 하지만 d[ 0 ] 은 1로 basesetting 

for i in range(5, N + 1):
    if (i % 2 == 1):
        d[i] = 0
        continue
    d[i] = d[i-2]*3
    for j in range(i - 4, -1, -2):
        d[i] += (d[j] * 2)

제곱수의 합 🚀

자연수 N을 제곱수의 합으로 나타낼때, 최소 제곱수의 항을 나타내기.

- 특이점

0부터 N 까지 다 돌면시간초과 (2중 for문) 제곱번만 돌면 그것이 최소 제곱수의 항으로 표현이 가능하다.

d[ n ] = n번째제곱수를 나타내는 최소항의 개수

n=int(input()) dp=[n]*(n+1) dp[0], dp[1]=0,1

for i in range(1,n+1): end=int(i**0.5)+1

dp[i]=min((dp[i-j*j]+1) for j in range(1, end))

print(dp[n])

문제유형 - D[ ][ 추가조건 ] 차원을 추가해 풀어야 하는 경우

- 1,2,3 더하기 5

D[ n ][ k ] = n자리수리고 k로 끝나는 수라고 정의 특이점 : 차원 1개 증가, CASE by Case 로 덧셈하면 됨

# 1을 붙이는 경우
d[i][0] = d[i-1][1] + d[i-1][2]
# 2를 붙이는 경우
d[i][1] = d[i-2][0] + d[i-2][2]
# 3을 붙이는 경우
d[i][2] = d[i-3][0] + d[i-3][1]



- 쉬운 계단수

11>112,110

d[ n ][ k ] = 길이가 n개인 계단수, 단 마지막 숫자가 k 이다. ( 길이를 늘려가며 overlap ) d[ n ][ k ] = d[ n -1 ][ k -1 ] + d[ n -1 ][ k + 1 ] ( 한계단 올라가는경우, 내려가는 경우 )

특이점 : 2차원 배열로 만들어서, 문제를 overlap

- 오르막 수

0000,0001,0002,0012 …

d[ n ][ k ] = 길이가 n인 오르막수의 갯수, 단 끝 자리 수가 k 이다. d[ n ][ k ] = d[ n-1 ][ k ] + d[ n-1 ][ k-1 ] + … .+ d[ n-1 ][ 0 ]

특이점 :

- 2차원 배열로 만들기. 문제를 2단계로 분리해서 overlap

- 이친수

1,10,100,101, 1000, 1001

- d[ n ][ k ] = 길이가 n인 이친수의 개수, 끝나는 숫자는 k이다. 
- d[ n ][ 1 ] = d[ n-1 ][ 0 ]    // 0으로 끝나야만 1로 늘릴 수 있다.
- d[ n ][ 0 ] = d[ n-1 ][ 0 ] + d[ n-1 ][ 1 ]

특이점:

- 2차원 배열로 분리해서 overlap


- 스티커

- d[ n ][ 번k ] = n째 스티커까지의 최대 점수 ( k = 0 안뜯 / 1 위뜯, / 2 아래 뜯 )
    d[i][0] = max(d[i - 1][0], d[i - 1][1], d[i - 1][2])  # 스티커를 안뜯는 경우
    d[i][1] = max(d[i - 1][0], d[i - 1][2]) + P[0][i-1]  # 위에를 뜯는경우
    d[i][2] = max(d[i - 1][0], d[i - 1][1]) + P[1][i-1]  # 아랠르 뜯는 경우

특이점 :

- 스티커 문제를 앞에서부터 하나씩 때는것으로 문제를 overlapping 해나간다.
- 2차원 배열로 Case를 나누어서 해결


- 포도주 시식

최대 2잔만 연속으로 먹을때 먹은 최대 포도주 양

- d[ n ][ k ] = n번째 까지 k번 연속으로 포도주를 먹었을때, 포도주의 최대 양
 
    D[i][0] = max( D[i-1][0], D[i-1][1], D[i-1][2])
    D[i][1] = D[i-1][0] + P[i]
    D[i][2] = D[i-1][1] + P[i]

- 계단오르기

한칸 이동, 한칸 점프해서 이동 단, 3번 연속 계단오르기 안됨, 이때 최대 점수

d[ n ][ k ] = n번째 계단까지 올랐을때 최대 점수, 현재 k번 연속 계단을 올랐다.

d[i][1] = max(d[i-2][2], d[i-2][1]) + P[i]
d[i][2] = d[i-1][1] + P[i]

문제유형 - D 메모방향이 forward인 경우

https://dndi117.tistory.com/entry/aaa

✨✨✨ 퇴사2 https://www.acmicpc.net/problem/15486 특이점 : 추가적인 메모변수(스칼라)가 하나 필요함

d[ 상담종료날 ] = max( p[오늘날짜의 상담 보수] + 오늘까지 회득한상담금액 최대값 , d[ 상담종료날 ] )

점프 https://www.acmicpc.net/problem/1890 특이점 : 현재 위치에서 미래로, 메모를 업데이트 한다. ( bottom up )
그러기 위해 , x = 0 부터 , y = 0~N 방향으로 돌면서, 가로로 점프하는 경우부터 센다. ( 특정 경우에 메모를 리턴하는 그런 dp랑 다르다. )

파이프 옮기기 2 https://www.acmicpc.net/problem/17069 특이점 : 점프 문제의 변형 ( bottom up 으로 접근 가능 )
축 z가 추가되었음, 업데이트 조건이 추가되었음

문제유형 - 메모방식이 Set인 경우, (점화식 구하기 어렵)

✨✨✨ N으로 표현 , https://programmers.co.kr/learn/courses/30/lessons/42895?language=javascript

특이점 : 발상이 매우 어렵다. 문제를 겹치는 방법이. 주어진 연산(사칙연산)의 횟수이다. Eg) 값을 연산 6번으로 만들 수 있는 케이스는 = 피연산자 A( 연산 1번 의 결과 값 Set ) 연산자( 주어진 5개의 연산 ) 피연산자 B ( 연산 5번의 결과 값 Set ) = 피연산자 A( 연산 2번 의 결과 값 Set ) 연산자( 주어진 5개의 연산 ) 피연산자 B ( 연산 4번의 결과 값 Set ) = 피연산자 A( 연산 3번 의 결과 값 Set ) 연산자( 주어진 5개의 연산 ) 피연산자 B ( 연산 3번의 결과 값 Set ) = 피연산자 A( 연산 4번 의 결과 값 Set ) 연산자( 주어진 5개의 연산 ) 피연산자 B ( 연산 2번의 결과 값 Set ) = 피연산자 A( 연산 5번 의 결과 값 Set ) 연산자( 주어진 5개의 연산 ) 피연산자 B ( 연산 1번의 결과 값 Set ) 이렇게 구할 수 있다.

d[ N ] = operation ( d[ K ] , d[ N - K ] ) ( 단, K = 1,...,N-1 , 단, Operation은 문제에서 주어진 연산 )

DP (dynamic programming)

기본문제​

문제유형 - 점화식, if, min, max, sum ( 가장 기본 )​

문제유형 - 지금까지의 모든 D를 살펴야 하는 경우​

문제유형 - D[ ][ 추가조건 ] 차원을 추가해 풀어야 하는 경우​

문제유형 - D 메모방향이 forward인 경우​

문제유형 - 메모방식이 Set인 경우, (점화식 구하기 어렵)​