다이나믹 프로그래밍1

dragonappear·2021년 1월 3일

Algorithm

목록 보기

3/5

다이나믹 프로그래밍

큰 문제를 작은 문제 여러개로 나눠서(주로크기를기준으로) 풀고 다시 원래의 큰 문제를 푸는 알고리즘
큰 문제를 작은 문제 여러개로 나눴을때, 작은 문제들이 중복이 가능하다.(분할정복은 중복허용X)
DP 문제에서 문제를 작게 만들때 한단계 그리고 나머지 단계로 나누는데, 한단계는 절대로 또 문제로 나누어지면 안된다.
한 단계에 들어갈 값을 정할수없다는것은 다해보면 된다

속성

두가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.

overlapping subproblem: 겹치는 부분(작은)문제
예:
- 피보나치 수열:
  F_0=0
  F_1=1
  F_n=F_n-1+F_n-2(N>=2)
  큰 문제= F_n, 작은 문제=F_n-1,F_n-2
  큰 문제= F_n-1, 작은 문제=F_n-2,F_n-3
  큰 문제= F_n-2, 작은 문제=F_n-3,F_n-4
  -> 작은 문제가 겹침
  -> 큰 문제와 작은 문제를 같은 방법으로 문제를 풀수있기때문에 주로 재귀를 사용한다.
optimal substructure : 최적부분구조(문제의 정답이 작은부분정답을 통하여 구할수있는구조)
예:
- 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면
- 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야한다.
  -> optimal substructure을 만족한다면, 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
- 10번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
- 9번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
- 5번째 피보나치 수를 구하면서 구한 4번째 피보나치 수
- 4번째 피보나치 수는 항상 같다.
DP에서 각 문제는 한 번만 풀어야한다.
optimal substructure를 만족하기 때문에, 같은 문제는 구할때마다 정답이 같다.
따라서, 정답을 한번 구했으면,정답을 어딘가에 메모해놓는다.
이런 메모하는 것을 코드의 구현에서는 배열에 저장하는 것으로 할수있다.(memoization)

memorization 예

int memo[100];
int fibonacci(int n){
	if(n<=1){
   return n;
   }
   else{
   	if(memo[n]>0) return memo[n];
   	memo[n] = fibonacci(n-1) + fibonacci(n-2);
       return memo[n];
   }
}

시간복잡도 = 모든 문제를 1번씩 풀다 -> 작은문제의 개수(==N) X 작은문제 1개를 푸는 시간(1) -> O(N)

구현 방식:

Top-down: 큰 문제부터 작은문제로 쪼개가면서 작은문제로 만들고 다시 큰 문제로 합쳐가는 방식.(재귀)
Bottom-up: 작은문제들을 모아서 큰 문제를 만드는 방식.(반복문) 1->2->3->4->5-> ...

기본문제

1로 만들기(https://www.acmicpc.net/problem/1463)
-> 문제를 작게 만들어야하기 때문에 DP를 생각해본다.
-> 점화식을 생각해보자
-> N을 1로 만드는 최소연산횟수 점화식
-> D[N] = N을 1로 만드는 최소연산횟수
- D[N]= N->N/3(한 문제) + N/3-> 1(나머지문제)
  D[N]= 1 + D[N/3]
- D[N]= N->N/2(한 문제) + N/2-> 1(나머지문제)
  D[N]= 1 + D[N/2]
- D[N]= N-1(한 문제) + (N-1)-> 1(나머지문제)
  D[N]= 1 + D[N-1]
-> D[N] = +1 min(D[N/3],D[N/2],D[N-1])

-> 점화식 시간 복잡도 = 함수의 호출횟수(=문제의 개수) X 함수의 시간복잡도(=문제 1개를 푸는데 필요한 시간복잡도) = O(N) * O(1) = O(N)
2xN 타일링(https://www.acmicpc.net/problem/11726)
-> 점화식을 생각해보자
-> D[N] = 2XN을 채우는 방법의 수
-> D[N] = D[N-1]+D[N-2]
2xN 타일링2(https://www.acmicpc.net/problem/11727)
-> 점화식을 생각해보자
-> D[N] = 2XN을 채우는 방법의 수
-> D[N] = D[N-1] + (2 X D[N-2])
1,2,3 더하기(https://www.acmicpc.net/problem/9095)
-> 점화식을 생각해보자
-> D[N] = n을 1,2,3의 합으로 나타내는 방법의 수
-> D[N] = D[N-1]+D[N-2]+D[N-3]
-> D[0] = 1 (1,2,3 아무것도 사용하지 않으므로)
카드구매하기(https://www.acmicpc.net/problem/11052)
-> 점화식을 생각해보자
-> D[N] = 카드 N개를 구매하는 비용의 최대값
-> 한 단계와 나머지 단계로 나눈다.
-> 한 단계에서 카드팩에 들어있는 카드의 개수는 알수없다? = DP에서는 알수없다는 것은 다해보면 된다고 생각하자
-> 한 단계에 들어갈수있는 카드팩 N개를 각각 집어 넣어본다.

-> D[N]= max(D(N-i)+ p[i]) (1<i<=n)
-> 시간복잡도= 전체문제의 개수(N) * 문제1개의 시간복잡도(N)
카드구매하기2(https://www.acmicpc.net/problem/16194)
-> 점화식을 생각해보자
-> D[N] = 카드 N개를 구매하는 비용의 최솟값
-> 한 단계와 나머지 단계로 나눈다.
-> 배열의 초기값을 잘 설정해야한다.
1,2,3 더하기 5(https://www.acmicpc.net/problem/15990)
-> 점화식을 생각해보자
-> D[i][j] = i 를 1,2,3의 합으로 나타내는 방법의수, 마지막에 사용한 수는 j
-> D[i][1]= i 를 1,2,3의 합으로 나타내는 방법의수, 마지막에 사용한 수는 1
- 바로 전에 사용할 수 있는 수는 2,3
- D[i-1][2]+ D[i-1][3]
-> D[i][2]= i 를 1,2,3의 합으로 나타내는 방법의수, 마지막에 사용한 수는 2
- 바로 전에 사용할 수 있는 수는 1,3
- D[i-2][1]+ D[i-2][3]
-> D[i][3]= i 를 1,2,3의 합으로 나타내는 방법의수, 마지막에 사용한 수는 3
- 바로 전에 사용할 수 있는 수는 1,2
- D[i-3][2]+ D[i-3][2]
-> 초기화도 신경써줘야한다.
-> 1,2,3 더하기처럼 D[0]=1 로 초기화하면 중복이 발생한다.
-> D[0][1]=1 ,D[0][2]=1 , D[0][3]=1로 초기화를 한다면
-> D[1][1]= D[0][2]+D[0][3] = 2 (중복이 발생하게 된다)
-> 따라서 이 문제는 예외처리를 해야한다.

-> D[i][1]=
-D[i-1][2]+D[i-1][3] (i>1)
-1(i==1)
-0(i<1)

-> D[i][2]=
-D[i-2][1]+D[i-2][3] (i>2)
-1(i==2)
-0(i<2)

-> D[i][3]=
-D[i-3][1]+D[i-3][2] (i>3)
-1(i==3)
-0(i<3)

-> 연속된 수를 처리할때는 마지막수를 체크해보자
쉬운 계단수(https://www.acmicpc.net/problem/10844)
-> 점화식을 생각해보자
-> D[N][L] = 길이가 N인 계단수,마지막수 L
-> D[N][L] = D[N-1][L-1]+D[N-1][L+1]
-> 예외처리: 마지막 수가 0이면 L-1 처리가 불가능, 마지막 수가 9이면 L+1=10 이므로 처리가 불가능
이친수(https://www.acmicpc.net/problem/2193)
-> 점화식을 생각해보자
-> D[N][L] = 길이가 N인 이친수의 개수, 마지막 수 L
-> D[N][1] = D[N-1][0], D[N][0] = D[N-1][0]+D[N-1][1]
-> 초기값: D[0][0]=0, D[0][1]=0, D[1][0] = 0 , D[1][1]= 1

-> 다른 방법으로
-> D[N]=N자리 이친수의 개수
-> D[N] = D[N-1]+D[N-2]
가장 긴 증가하는 부분수열(https://www.acmicpc.net/problem/11053)
-> longest increasing subsequence
-> D[i] = A[1], ... ,A[i]까지 수열이 있을때, A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
-> d[i] = max(d[j])+1 (j<i,A[j]<A[i])
-> O(n^2)
가장 긴 증가하는 부분수열4(https://www.acmicpc.net/problem/14002)
-> 역추적 알고리즘
연속합(https://www.acmicpc.net/problem/1912)
-> d[i] = i번째 수로 끝나는 가장 큰 연속합
-> max(i번째수가 i-1번째와 연속, 연속X)
-> d[i] = max(d[i-1]+a[i], a[i])
-> O(N)
제곱수의합(https://www.acmicpc.net/problem/1699)
-> 최소개수를 구하는 문제
-> d[n] = 자연수 n을 표현하는데 필요한 항의 최소개수
-> d[n]= min(d[n-i^2]+1) (1<=i^2<=n)
-> 방법의 개수를 구한다고 하면
-> d[n] = ∑(d[n-i^2])
-> 시간복잡도 O(n * √n)
합분해(https://www.acmicpc.net/problem/2225)
-> 정수 k개를 더해서 경우의 수를 구하는 문제
-> d[k][n] = d[k-1][n-l] , l=마지막에 더하는 수 (l<=n)
-> d[k][n] =∑d[k-1][n-l] (0 <=l<=n)
-> O(KN^2)

연습문제

1,2,3 더하기 3(https://www.acmicpc.net/problem/15988)
RGB거리(https://www.acmicpc.net/problem/1149)
-> 최소비용구하는문제+연속인조건
-> d[i][j] = i번집을 색j로 칠했을때,1~i번 집을 칠하는 비용의 최솟값

j=0일 때
d[i][j] = min(d[i-1][1],d[i-1][2])+a[i][0]
j=1일 때
d[i][j] = min(d[i-1][0] + d[i-1][2])+a[i][1]
j=2일 때
d[i][j] = min(d[i-1][0] + d[i-1][1])+a[i][2]

동물원(https://www.acmicpc.net/problem/1309)
-> 가로기준: 하나도 배치하지않는 경우, 한마리 왼쪽칸에 배치, 한마리 오른쪽칸에 배치
-> 경우의 수

i가 2일때,
d[n][i] = d[n-1][0]+d[n-1][1]
i가 1일때,
d[n][i] = d[n-1][0]+d[n-1][2]
i가 0일때,
d[n][i] = d[n-1][0]+d[n-1][1]+d[n-1][2]

오르막수(https://www.acmicpc.net/problem/11057)
-> d[i][j] = 길이가 i이고 마지막 숫자가 j인 오르막 수의 개수
-> d[1][j] = 1
-> d[i][j] += d[i-1][k](0<=k<=j)
스티커(https://www.acmicpc.net/problem/9465)
-> 최댓값 구하는 문제
-> d[i][j]=2 X i에서 얻을수 있는 최대점수,i번째열에서 뜯는 스티커는 j
-> 하나도 떼지않는 경우, 위쪽칸에 떼기, 아랫칸에 떼기
-> 경우의 수

i가 2일때,
d[n][i] = max(d[n-1][0],d[n-1][1])+a[i][2]
i가 1일때,
d[n][i] = max(d[n-1][0],d[n-1][2])+a[i][1]
i가 0일때,
d[n][i] = max(d[n-1][0],d[n-1][1],d[n-1][2])

6. 포도주시식(https://www.acmicpc.net/problem/2156)

정수삼각형(https://www.acmicpc.net/problem/1932)
-> 최댓값 구하는 문제
-> d[i][j]= i행 j열의 최대점수
-> d[i][j]= max(d[i-1][j-1],d[i-1][j])+a[i][j]
가장 큰 증가하는 부분수열(https://www.acmicpc.net/problem/11055)
-> 최댓값 구하는 문제
-> d[i] = 수열 i까지의 최댓값
-> d[i] = max(d[j]+a[i]) (j<i && a[j]<a[i] )
가장 긴 감소하는 부분수열(https://www.acmicpc.net/problem/11722)
-> 길이 최솟값을 구하는 문제
-> d[i] = 수열 i부터 시작하는 가장 긴 감소하는 부분수열의 길이
-> d[i]= max(d[j]+1) , (i<j && a[i]>a[j])
-> 다른 방법으로 d[i] = 수열 i에서 끝나는 가장 긴 감소하는 부분수열의 길이
-> d[i]= max(d[j]+1) , (j<i && a[i]<a[j])

10. 가장 큰 바이토닉 부분수열(https://www.acmicpc.net/problem/11054)
-> 길이 최댓값을 구하는 문제
-> LIS와 LDS를 활용해서 문제를 푼다.
-> d[i] = i에서 끝나는 증가수열
-> d2[i] = i부터 시작하는 감소수열
-> d[k] = d[k]+d2[k]-1

11. 연속합2(https://www.acmicpc.net/problem/13398)
-> 최댓값 구하는 문제(수는 하나 제거할수있다)
-> d[i] = i에서 끝나는 합의 최댓값
-> d2[i] = i부터 끝나는 합의 최댓값
-> d[k-1]+d2[k+1]

타일채우기(https://www.acmicpc.net/problem/2133)
-> 경우의수
-> d[i] = 3 x i 타일을 채울수있는 방법의수
-> d[i] = d[i-2] x 3 + d[i-4] X 2 + d[i-6] X 2

도전문제

동물원(https://www.acmicpc.net/problem/1309)
-> 다른방식으로 푸는문제
-> 가로기준: 한마리도 배치x, 한마리 왼쪽칸에 배치, 한마리 오른쪽칸에 배치
-> d[i] = 세로크기가 i인 동물원을 채우는 방법의 수, 단 i번째에는 동물이 있어야한다.
-> i번째 줄의 이전에 동물이 있는 줄은 어디일까?
-> d[i]= d[i-1] + 2×d[i-2] + 2×d[i-2] + ... 2× d[1]
-> s[i] = d[1]+ ... d[i]
-> d[i] = d[i-1] + 2* si-2
-> S[N]이 정답이다

2. RGB거리2(https://www.acmicpc.net/problem/17404)
-> 최소비용구하는문제
-> d[i][j] = i번집을 색j로 칠했을때,1~i번 집을 칠하는 비용의 최솟값

초기값으로 1번집의 색깔을 고정한다.
-> 1번: 빨강 -> n번: 초 or 파
-> 1번: 초록 -> n번: 빨 or 파
-> 1번: 파랑 -> n번: 빨 or 초
-> 마지막에 1번과 n번 색 비교한후, min(d[n][0],d[n][1],d[][2])

합분해(https://www.acmicpc.net/problem/2225)
-> D[K][N] = ∑D[K-1][l](0<=l<=N)
-> D[K][N] = D[K-1][0]＋...＋D[K-1][N]
-> D[K][N-1] = D[K-1][0]＋...＋D[K-1][N-1]
-> D[K][N] = D[K][N-1]＋D[K-1][N]