알고리즘 - 다이나믹 프로그래밍
알고리즘 문제에서 흔히들 동적계획법 으로 알려져 있는 다이나믹 프로그래밍에 대한 개념설명과 기초 문제 풀이이다. 매우 기초를 벗어난 모든 알고리즘 문제는 이 접근법을 필수적으로 사용하는 경우가 많기 때문에 반드시 숙지해야 하는 알고리즘이다.
다이나믹 프로그래밍
큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다
다이나믹 프로그래밍의 속성
- 작은 문제(부분 문제)가 모두 겹친다
- 최적 부분 구조이다. 작은(부분) 문제의 답이 결과 값을 구할때의 과정에 사용된 값과 항상 같다.
예를들어 피보나치 문제의 경우에는 작은 문제 두개의 합으로 큰 문제를 구한다. 또한 계속해서 나타나는 작은 문제들의 값이 중복적으로 같다.
- 다이나믹 프로그래밍에서 각 문제는 한번만 푼다
- 최적 부분구조를 만족하므로, 같은 문제는 항상 답이 같다
- 정답을 구했으면, 어딘가에 저장(메모)한다
- 메모는 배열에 저장하는것으로 할 수 있다
- 메모를 하는 것이라서 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];
}
}위 코드의 시간복잡도는 다음과 같이 계산할 수 있다.
기억해야 할 점은 모든 문제를 한번씩 푼다는 것이다.
함수 호출은 n번 일어난다. 여기에 함수의 시간복잡도를 계산해주면 된다. 함수의 시간복잡도는 O(1) 이다.
따라서 위 코드의 시간복잡도는 O(n) 이다.
다이나믹 프로그래밍 구현 방법
- Top-down : 재귀함수를 이용한 방법 (모든 문제를 쪼개놓고 필요할 때 구한다)
- Bottom-up : 작은문제부터 풀고, 조금씩 크게 만들면서 문제를 푼다 (모든 문제를 쪼개놓고 풀어놓는다)
위 방법중 아무거나 쓰면 된다. 정답이 없다.
문제 풀이 전략
맨 처음 먼저 점화식을 세운다!!
이 문제를 구하기 위해서 어떤 작은 문제들이 필요한가??
작은 문제들이 어떻게 원래 문제를 풀어낼 수 있는가??
-
문제를 크기가 작은문제부터 차례대로 푼다
for(int i=0;i<n;i++) -
문제의 크기를 점점 크게 만들면서 푼다
1로 만들기 (1463번 문제)
이 문제의 경우 3가지의 행동이 가능하다. 문제를 다이나믹 프로그래밍으로 풀기 위해 작은 문제들로 쪼개어 로직을 구성하면 다음과 같다.
- X가 3으로 나누어 떨어지면, 3으로 나눈다 : N->N/3 => D[N] -> D[N/3] + 1
- X가 2로 나누어 떨어지면, 2로 나눈다 : N->N/2 => D[N] -> D[N/2] + 1
- 1을 뺀다 : N->N-1 => D[N] -> D[N-1] + 1
최소의 결과값을 얻기 위해서는 항상 최소의 과정이 필요하다 따라서 D[N] 을 계산하는 과정은 항상 최소가 되어야 한다. 결과적으로 점화식은 다음과 같은 형태를 하게 된다.
D[N] = min(D[N/3]+1,D[N/2]+1,D[N-1]+1) = min(D[N/3],D[N/2],D[N-1]) + 1
이 문제의 시간복잡도는 전체문제의 개수(배열의 크기) * 1문제를 푸는 시간(O(1)) 이므로 O(N) 이다.
코드는 다음과 같다
#include <stdio.h>
int dp[1000001];
int r(int n) {
int res;
if(n==1) return 0; // 1은 아무런 행동도 하지 않고 끝난다
if(dp[n]>0) return dp[n]; // 메모되어 있다면 꺼낸다
dp[n] = r(n-1) +1;
if(n%3==0) {
int temp = r(n/3) + 1;
if(temp<dp[n]) dp[n] = temp;
}
if(n%2==0) {
int temp = r(n/2) + 1;
if(temp<dp[n]) dp[n] = temp;
}
return dp[n];
}
int main() {
int n;
scanf("%d",&n);
printf("%d",r(n));
}
2Xn 타일링 (11726번 문제)
문제를 점화식으로 파악하는 것이 가장 중요하다.
이 문제에서는 2XN 크기의 타일을 채울 수 있는 경우의 수를 D[N]이라고 잡자. 2X1 타일을 맨 뒤에 붙인다고 생각하면, 2X(N-1) 만큼의 타일이 남는다. 이것은 D[N-1] 이라고 할 수 있다. 또 1X2 타일 두개를 맨 뒤에 붙인다고 생각하면 2X(N-2) 만큼의 타일이 남고, 이것은 D[N-2] 이다.
따라서 점화식은
D[N] = D[N-1] + D[N-2]
라고 할 수 있다.
또한 여기서 D[1] (즉 2X1) 일 때는 무조건 1가지의 경우의 수이기 때문에 D[1] = 1이다. D[2] 는 가로로 두개를 놓거나 세로로 두개를 넣는 경우 딱 두가지로 나오기 때문에 D[2] = 2 이다. D[3] 부터는 D[N] = D[N-1] + D[N-2] 점화식이 적용될 수 있다. 코드를 짜보면 다음과 같다.
#include <stdio.h>
int dp[1001];
int r(int n) {
if(n==1) return 1;
if(n==2) return 2;
if(dp[n]>0) return dp[n];
dp[n] = r(n-1)+r(n-2);
if(dp[n]>10007) dp[n] %= 10007;
return dp[n];
}
int main() {
int n;
scanf("%d",&n);
printf("%d",r(n));
}
2Xn 타일링2 (11727번 문제)
위의 문제와 완벽하게 동일하지만, 추가할 수 있는 2x2 타일이 추가되었다. 2x2 타일이 맨 뒤에 오는 경우를 생각해보면 D[N-2] 와 같다. 따라서 점화식은 D[N] = D[N-1] + 2*D[N-2] 로 나타낼 수 있다. 또 D[1] = 1 은 변하지 않지만, D[2] 는 가로 블럭이 두개 오는경우, 세로 블럭이 두개 오는 경우, 2x2 타일이 한개 오는 경우로 D[2] = 3 으로 나타낼 수 있다.
코드는 다음과 같다
#include <stdio.h>
int dp[1001];
int r(int n) {
if(n==1) return 1;
if(n==2) return 3;
if(dp[n]>0) return dp[n];
dp[n] = r(n-1)+2*r(n-2);
if(dp[n]>10007) dp[n] %= 10007;
return dp[n];
}
int main() {
int n;
scanf("%d",&n);
printf("%d",r(n));
}
1,2,3 더하기 (9095번 문제)
다이나믹 프로그래밍으로 풀어보자. 먼저 n 을 만들 수 있는 경우의 수를 D[N] 이라고 한다면, 마지막에 1을 더하고 끝난 것은 D[N-1], 2를 더하고 끝난 것은 D[N-2], 3을 더하고 끝난 것은 D[N-3] 이라고 할 수 있다. 그래서 점화식은 D[N] = D[N-1] + D[N-2] + D[N-3] 이라고 할 수 있다. 단 1을 만들 수 있는 경우의 수는 1이므로 D[1] = 1 이고, 2를 만들 수 있는 방법은 D[2] = 2, 3을 만들 수 있는 방법은 (3,2+1,1+2,1+1+1) 4가지 이므로 D[3] = 4 이다.
코드는 다음과 같다
#include <stdio.h>
int dp[11];
int r(int n) {
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
if(dp[n]>0) return dp[n];
dp[n] = r(n-1) + r(n-2) + r(n-3);
return dp[n];
}
int main() {
int t,n;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
printf("%d\n",r(n));
}
}
1,2,3 더하기3 (15988번 문제)
위 문제와 똑같으나 범위가 늘어났다. 여기서 중요한 점은 int 형으로는 계산할 수 없기 때문에 long long 을 써야 한다
코드는 다음과 같다
#include <stdio.h>
long long dp[1000001];
long long m = 1000000009;
long long r(int n) {
if(n==1) return 1;
if(n==2) return 2;
if(n==3) return 4;
if(dp[n]>0) return dp[n];
dp[n] = r(n-1) + r(n-2) + r(n-3);
dp[n] %= m;
return dp[n];
}
int main() {
int t,n;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
printf("%lld\n",r(n));
}
}
카드 구매하기 (11052번 문제)
이 문제는 다음과 같이 접근할 수 있다. 카드 i 개를 구매하는 최대 비용을 D[i] 라고 한다면, 카드팩 j 를 구매하고 남은 i-j 개의 카드를 고르는 최대 비용은 D[i-j] 이다. 따라서 점화식은 D[i] = P[j] + D[i-j] 라고 할 수 있다. 그런데 여기서 중요한 점은 j 의 범위를 꼭 기억해야 한다는 것이다. 여기서 j 의 범위는 1<=j<=i 이다. j 가 0 이 되는 것은 D[i]=D[i] 로 의미없는 식이 되기 때문에 1부터 시작한다. 이렇게 점화식 안에 또다른 변수가 나타난 경우에는 모든 경우의 수를 다 구해보고, 그 중에 해당하는 값을 골라야 한다. 따라서 완성된 점화식은 다음과 같다.
D[i] = max(P[j] + D[i-j]) where (1<=j<=i)`
코드는 다음과 같다
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int arr[1001];
int dp[1001];
int r(int n) {
if(n==0) return 0;
if(dp[n]>0) return dp[n];
dp[n] = 0;
for(int i=1;i<=n;i++) {
int temp = arr[i]+r(n-i);
if(temp>dp[n]) dp[n] = temp;
}
return dp[n];
}
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&arr[i]);
}
printf("%d",r(n));
}
카드 구매하기 (11052번 문제)
위의 문제와 완벽하게 동일하나, 최솟값을 구하는 문제이다. 이때 최솟값을 구할 때 초기 값을 -1 로 정하고 만약 -1 이라면 무조건 다음 값을 최솟값으로 만들어 주는 과정만 추가해 주면 된다.
코드는 다음과 같다
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
int arr[1001];
int dp[1001];
int r(int n) {
if(n==0) return 0;
if(dp[n]>0) return dp[n];
dp[n] = -1;
for(int i=1;i<=n;i++) {
int temp = arr[i]+r(n-i);
if(dp[n]==-1 || temp<dp[n]) dp[n] = temp;
}
return dp[n];
}
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&arr[i]);
}
printf("%d",r(n));
}
1,2,3 더하기 5 (15990번 문제)
이 문제에서는 같은 수를 두번 이상 연속해서 사용하면 안된다. 그렇다면 점화식이 달라지게 된다. 그냥 다이나믹 프로그래밍으로 기존 점화식을 사용하면 안된다.
점화식을 세개로 쪼갠다
D[i][j] = i 를 1,2,3 의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j
여기서 마지막에 사용한 수라는 것은 i 를 만들기 위해서 사용한 마지막의 바로 전 문자열이라는 것이다. 따라서 j 를 마지막에서 두번째에 사용했기 때문에, 마지막에는 사용할 수 없다.
D[i][1] = D[i-1][2] + D[i-1][3]
D[i][2] = D[i-2][1] + D[i-2][3]
D[i][3] = D[i-3][1] + D[i-3][2]
이 문제에서 점화식만 세우면 큰 어려움은 없는데, 나눈 나머지를 구해야 하므로, 모든 과정에서 %= 를 적용해주고 마지막 결과값 출력에도 %= 를 해주어야 한다.
코드는 다음과 같다
#include <stdio.h>
long long dp[100001][4];
long long mod = 1000000009;
long long r(int n,int idx) {
if(idx==1) {
if(n<1) return 0;
if(n==1) return 1;
if(dp[n][1]>0) return dp[n][1];
dp[n][1] = r(n-1,2)+r(n-1,3);
dp[n][1] %= mod;
return dp[n][1];
}
else if(idx==2) {
if(n<2) return 0;
if(n==2) return 1;
if(dp[n][2]>0) return dp[n][2];
dp[n][2] = r(n-2,1)+r(n-2,3);
dp[n][2] %= mod;
return dp[n][2];
}
else if(idx==3) {
if(n<3) return 0;
if(n==3) return 1;
if(dp[n][3]>0) return dp[n][3];
dp[n][3] = r(n-3,1)+r(n-3,2);
dp[n][3] %= mod;
return dp[n][3];
}
return 0;
}
int main() {
int t,n;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
printf("%lld\n",(r(n,1)+r(n,2)+r(n,3))%mod);
}
}
쉬운 계산 수 (10844번 문제)
먼저 점화식을 세우기 위해 규칙을 찾아본다.
D[N] = 길이가 N인 *계단 수*의 개수 (여기서 계단수란 옆자리와의 값이 1씩 차이나는 수) 라고 정의하게 되면 문제가 발생한다. 계단수를 만들기 위해서 옆자리와 비교를 할 수 있어야 하는데, 위 점화식으로는 불가능하다. 따라서 임의의 수를 맨 마지막에 넣고, 그 앞자리에 무엇이 올 수 있는지에 대한 점화식으로 쪼개서 생성해야 한다.
만약 D[N][L] 이 길이가 N인 계산수이고 마지막 숫자가 L 인 식이라고 하자. 그러면 마지막 바로 전 숫자는 L-1 또는 L+1 이 올 수 있다. 따라서 점화식은 다음과 같이 생성된다.(예외처리 포함)
D[N][L] = D[N-1][L-1](L>0) + D[N-1][L+1](L<9)
이에 맞추어 코드를 생성해주면 된다. 예외처리를 잘 생각해야 한다. 맨 앞에는 0이 올 수 없고(D[1][0] 은 없다) 1자리수를 제외한 마지막 자리들에는 0이 들어갈 수 있다.
#include <stdio.h>
long long dp[101][10];
long long mod = 1000000000;
long long r(int n, int idx) {
if(n==1 && idx!=0) return 1;
else if(n==1 && idx==0) return 0; // 맨앞에 오는 수가 0일 수 없다
if(dp[n][idx]>0) return dp[n][idx];
dp[n][idx] = 0;
if(idx>0) dp[n][idx] += r(n-1,idx-1);
if(idx<9) dp[n][idx] += r(n-1,idx+1);
dp[n][idx] %= mod;
return dp[n][idx];
}
int main() {
int n;
long long sum = 0;;
scanf("%d",&n);
for(int i=0;i<10;i++) { // 마지막 자리에는 0이 올 수 있다.
sum += r(n,i);
sum %= mod;
}
printf("%lld",sum);
}
오르막 수 (11057번 문제)
D[N][L] 을 마지막 숫자가 L인 N자리수 수라고 한다면, 마지막 전 숫자는 L 이하인 모든 수가 올 수 있다. 따라서 점화식은 D[N][L] = D[N-1][K](K<=L) 로 세울 수 있다.
또한 맨 앞자리 수가 0으로 시작할 수 있기 때문에, 항상 K를 0이상 L이하로 생각하고 풀면 된다. 초기화는 D[1][L] = 1 이다.
코드는 다음과 같다
#include <stdio.h>
int dp[1001][10];
int mod = 10007;
int r(int n,int idx) {
if(n==1) return 1;
if(dp[n][idx]>0) return dp[n][idx];
dp[n][idx] = 0;
for(int i=0;i<=idx;i++) {
dp[n][idx] += r(n-1,i);
dp[n][idx] %= mod;
}
return dp[n][idx];
}
int main() {
int n,sum=0;
scanf("%d",&n);
for(int i=0;i<10;i++) {
sum+= r(n,i);
sum%= mod;
}
printf("%d",sum);
}
이친수 (2193번 문제)
이친수에서는 0으로 시작하지 않고, 1이 연속으로 나오지 않는다. 이 문제도 전형적인 점화식 쪼개주는 문제이다.
D[N][0] = N자리 이친수인데, 마지막 수가 0인 개수 와 D[N][1] = N자리 이친수인데, 마지막 수가 1인 개수 로 나누어 볼 수 있다. 따라서 점화식은 다음과 같다.
D[N][0] = D[N-1][0] + D[N-1][1]
D[N][1] = D[N-1][0]
0으로 시작하지 않기 때문에, D[1][0] = 0, D[1][1] = 1 이다.
또한 이 문제는 0,1 만 존재하기 때문에 2차원으로 풀지 않고 1차원으로도 풀 수 있다. 다음과 같이 나타낼 수 있다.
D[i] = D[i-1] // 바로 전에는 모두 다 올 수 있다 (0인경우)
D[i] = D[i-2] // 바로 전에는 0만 올 수 있고, 두번째 전에는 모두 올수 있기 때문이다 (1인경우)
이 문제의 경우에는 우연히 1차원으로 풀 수 있었다. 그러나 모든 문제가 이러한 풀이 방식으로 가능하지는 않기 때문에, 연습할 때는 항상 2차원으로 만들어서 푸는 것을 추천한다!(대부분의 점화식 쪼개기 문젠는 2차원 범위에서 해결이 가능하다.
이 문제의 값은 int 형의 범위를 벗어나기 때문에 long long 을 써 주어야 한다
#include <stdio.h>
long long dp[91][2];
long long r(int n, int idx) {
if(n==1 && idx==0) return 0;
if(n==1 && idx==1) return 1;
if(dp[n][idx]>0) return dp[n][idx];
dp[n][idx] = 0;
if(idx==0) {
dp[n][idx] += r(n-1,1)+r(n-1,0);
}
else if(idx==1) {
dp[n][idx] += r(n-1,0);
}
return dp[n][idx];
}
int main() {
int n;
scanf("%d",&n);
printf("%lld",r(n,0)+r(n,1));
}
스티커 (9465번 문제)
이 문제가 다이나믹 프로그래밍이 되는 이유는, 마지막에 뜯는 스티커가 같다고 생각한다면, 그 전까지의 최댓값이 결과의 최댓값과 같기 때문이다.
D[N] = 뗄 수 있는 스티커들의 최댓값 이라고 하자. 그렇다면 최댓값을 구하기 위해서 하나의 스티커를 뜯었을 때, 그 이후의 결과가 어떻게 나오는지 보자.
맨마지막 column (1x2) 스티커를 뜯는 방법은 세가지가 있다.
D[i][j] 를 2xi 에서 얻을 수 있는 최대 점수라고 생각할 때, j 는 이전에 column 에서 어떤 스티커를 떼어냈는지를 나타낸다.
- 아예 뜯지 않는다(j==0) =>
D[i][0] = max(D[i-1][0],D[i-1][1],D[i-1][2]) - 위에만 뜯는다(j==1) =>
D[i][1] = A[i][0] + max(D[i-1][0],D[i-1][2]) - 밑에만 뜯는다(j==2) =>
D[i][2] = A[i][1] + max(D[i-1][0],D[i-1][1])
이 문제는 Top-down 방식의 재귀 함수로 풀게 되면 시간초과가 뜨게 된다. 또한 주의할 점은 2xn 판에서 최댓값을 구하는 것은 n 일때의 D[n][0],D[n][1],D[n][2] 중에서 고르는 것이 아니라 1부터 n까지 모두 중 최댓값을 구해야 한다는 것이다.
코드는 다음과 같다
#include <stdio.h>
#define max(a,b) (((a)>(b))?(a):(b))
long long a[100001][2];
long long d[100001][3];
int main() {
int t;
scanf("%d",&t);
while(t--) {
int n;
scanf("%d",&n);
for (int i=1; i<=n; i++) {
scanf("%lld",&a[i][0]);
}
for (int i=1; i<=n; i++) {
scanf("%lld",&a[i][1]);
}
d[0][0] = d[0][1] = d[0][2] = 0;
for (int i=1; i<=n; i++) {
d[i][0] = max(d[i-1][0],max(d[i-1][1],d[i-1][2]));
d[i][1] = max(d[i-1][0],d[i-1][2])+a[i][0];
d[i][2] = max(d[i-1][0],d[i-1][1])+a[i][1];
}
long long ans = 0;
for (int i=1; i<=n; i++) {
ans = max(max(ans,d[i][0]),max(d[i][1],d[i][2]));
}
printf("%lld\n",ans);
}
}
포도주 시식 (2156번 문제)
연속으로 놓여진 3잔은 마실 수 없다. 이 문제도 경우의 수를 나누어서 생각할 수 있다. D[N][L] 에서 L은 이번(마지막)에 잔을 마시지 않거나(0), 마시는데 이번으로 연속 1번(1)이거나, 이번으로 연속 2번(2)이거나로 나누어서 점화식을 세워본다.
D[N][0] = 전에 연속으로 마시지 않음 = max(D[N-1][0],D[N-1][1],D[N-2][2])
D[N][1] = 이번에 마셔서 1번 연속 = D[N-1][0]
D[N][2] = 이번에 마셔서 2번 연속 = D[N-1][1]
dp 문제(백준)를 시간 초과 없이 풀려면 아무래도 top-down 방식보다 bottom-up 방식이 더 빠른 것 같다. 이제부터 bottom-up 으로 풀려고 한다.
#include <stdio.h>
#define max(a,b) (((a)>(b))?(a):(b))
int a[10001];
int dp[10001][3];
// D[n][0] = max(D[n-1][0],D[n-1][1],D[n-1][2])
// D[n][1] = a[n] + D[n-1][0]
// D[n][2] = a[n] + D[n-1][1]
// D[1][0] = 0
// D[1][1] = a[1]
// D[1][2] = 0 <- 불가능
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
dp[1][0] = 0;
dp[1][1] = a[1];
dp[1][2] = 0;
for(int i=2;i<=n;i++) {
dp[i][0] = max(dp[i-1][0],max(dp[i-1][1],dp[i-1][2]));
dp[i][1] = a[i] + dp[i-1][0];
dp[i][2] = a[i] + dp[i-1][1];
}
int res = 0;
for(int i=1;i<=n;i++) {
if(dp[i][0]>res) res = dp[i][0];
if(dp[i][1]>res) res = dp[i][1];
if(dp[i][2]>res) res = dp[i][2];
}
printf("%d",res);
}
가장 긴 증가하는 부분수열 (11053번 문제)
Longest Increasing Subsequence
수열에서 몇개를 순서대로 빼내어 가장 긴 증가하는 수열을 만드는 문제이다.
수열에서 부분수열을 만드는 방법
2^N 개가 있다. 이 문제는 N<=1000 이기 때문에 2^1000 까지 다 구하는 것은 불가능하다.
다이나믹 프로그래밍으로 푸는 방법
D[i] = A[i]를 마지막으로 하는 가장 긴 증가하는 부분수열 이라고 하자. 그렇다면 그 뒤에 올 수 있는 최대값을 만드는 뒷 부분 수열은 항상 같다. 구하는 방법은 다음과 같다.
A = {10, 20, 10, 30, 20, 50,10} 이라고 하자. 순차적으로 1개부터 N개까지 D[N] 을 구해본다. 여기서 하나의 D[N] 을 구할때는 이전의 D[N-1] ~D[1] 중 만족하는 가장 큰 녀석을 자신에게 더해준다. 따라서 순서는 N-1 부터 1 순으로 찾아간다.
- D[1] 은 스스로 증가하는 부분수열을 만족하기 때문에 1이다.
- D[2] 는 스스로 만족 & D[1] 을 포함하여 만족하므로 1+D[1] = 2 이다.
- D[3] 은 스스로만 만족하므로 1이다.
- D[4] 는 스스로 만족 & D[3] 도 가능하고 D[2] 도 가능하고 D[1]도 가능하다. 이 중 가장 값이 큰 녀석을 저장하기 때문에 3이 저장된다.
- D[5] 는 스스로 & D[3],D[1] 을 만족하므로 2가 저장된다.
- D[6] 은 스스로 & D[5~1] 다되기 때문에 그 중 가장 큰 값을 저장하여 4가 된다.
- D[7]은 스스로만 만족하므로 1이 저장된다.
D[] = {1,2,1,3,2,4,1}
이 LIS 문제에서 정답은 4가 된다. 이 문제에서 가장 큰 D[N] 이 정답이 된다.
코드는 다음과 같다
#include <stdio.h>
int a[1001];
int dp[1001];
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++) {
dp[i] = 1;
for(int j=1;j<i;j++) {
if(a[j]<a[i] && dp[j]+1>dp[i]) {
dp[i] = dp[j]+1;
}
}
}
int res = 0;
for(int i=1;i<=n;i++) {
if(dp[i]>res) res = dp[i];
}
printf("%d",res);
}
가장 긴 증가하는 부분 수열4 (14002)
위 문제와 정확하게 동일하게 가장 긴 증가하는 부분 수열을 찾는 문제이지만, 그 긴 수열 자체를 출력하는 문제이다.
이 문제에서는 앞에서 한 과정에 기록하는 과정을 추가해야 한다. 앞의 D[i] 에 의해 현재 D[N] 이 바뀔 때, V[N] 에는 i (인덱스) 를 기록해주어 어떤 D[i] 에 의해 영향을 받았는지 기록해준다.
인덱스를 보고 쭉쭉 거꾸로 따라가다 보면(V[i] 가 0이 나올때까지), 앞의 모든 수열들을 찾아낼 수 있다. 찾아낼 때 재귀함수를 이용하면 순서대로 나오고, 그냥 반복으로 찾아주면 거꾸로 나오기 때문에 뒤집어 줘야 한다.
코드는 다음과 같다
#include <stdio.h>
int a[1001];
int dp[1001];
int v[10001];
void r(int n) { // 뒤집어주는 부분이다
if(n==0) return;
r(v[n]);
printf("%d ",a[n]);
}
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++) {
dp[i] = 1;
for(int j=1;j<i;j++) {
if(a[j]<a[i] && dp[j]+1>dp[i]) {
dp[i] = dp[j]+1;
v[i] = j;
}
}
}
int res = 0;
int l = 0;
for(int i=1;i<=n;i++) {
if(dp[i]>res) {
res = dp[i];
l = i;
}
}
printf("%d\n",res);
r(l);
}
가장 큰 증가하는 부분 수열 (11055번 문제)
이 문제는 다 똑같은데 개수 대신 합 이 가장 큰 수열을 고르는 문제이다. 간단하게 개수를 구하는 부분을 합을 구하도록 바꾸기만 하면 된다.
코드는 다음과 같다
#include <stdio.h>
int a[1001];
int dp[1001];
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
}
for(int i=1;i<=n;i++) {
dp[i] = a[i];
for(int j=1;j<i;j++) {
if(a[j]<a[i] && dp[j]+a[i]>dp[i]) {
dp[i] = dp[j]+a[i];
}
}
}
int res = 0;
for(int i=1;i<=n;i++) {
if(dp[i]>res) res = dp[i];
}
printf("%d",res);
}
가장 긴 감소하는 부분 수열 (11722번 문제)
먼저 A[i] 에서 시작하는 가장 긴 감소하는 부분 수열을 구하는 방식으로 풀 수 있다. 또는 더 쉬운 방법으로는 뒤집어서 가장 긴 증가하는 부분 수열을 찾고, 다시 뒤집으면 된다.
처음에 받을 때만 반대로 받고 가장 긴 증가하는 부분 수열의 개수를 찾아주면 된다.
for(int i=n;i>0;i--) {
scanf("%d",&a[i]);
}
가장 긴 바이토닉 부분 수열 (11054번 문제)
가장 긴 증가하는 부분수열(D1)과 가장 긴 감소하는 부분 수열(D2)을 구한다. 결과는 D1 + D2 - 1 이 된다.
- 증가하는 부분수열의 개수를 모두 찾는다
- 감소하는 부분수열의 개수를 모두 찾는다 (뒤집어서 했음)
- 두개를 합친다음 1씩 빼서 저장한 것 중 최댓값을 찾는다
코드는 다음과 같다
#include <stdio.h>
#include <algorithm>
using namespace std;
int a[1001];
int ra[1001];
int dp1[1001];
int dp2[1001];
int main() {
int n,temp;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d",&temp);
a[i] = temp;
ra[n-i+1] = temp;
}
for(int i=1;i<=n;i++) {
dp1[i] = 1;
dp2[i] = 1;
for(int j=1;j<i;j++) {
if(a[j]<a[i] && dp1[j]+1>dp1[i]) {
dp1[i] = dp1[j]+1;
}
if(ra[j]<ra[i] && dp2[j]+1>dp2[i]) {
dp2[i] = dp2[j]+1;
}
}
}
reverse(dp2+1,dp2+n+1);
int res = 0;
for(int i=1;i<=n;i++) {
if(dp1[i]+dp2[i]-1>res) {
res = dp1[i]+dp2[i]-1;
}
}
printf("%d",res);
}
연속합 (1912번 문제)
연속된 숫자들을 뽑아서 가장 큰 합을 구하는 문제이다.
각각의 수가 연속합에 포함되었을 때의 최댓값을 찾는 방식으로 풀어나가면 된다.
D[i] = A[i] 에서 끝나는 연속합의 최대 라고 하자. 즉 D[i] = A[i] + D[i-1] 이라고 생각할 수 있다. 아니면 자기 자신 혼자만 존재하는 D[i] = A[i] 라고 할 수도 있다. 따라서 점화식은 D[i] = max(A[i],A[i]+D[i-1]) 이라고 할 수 있다.
코드는 다음과 같다
#include <stdio.h>
long long a[100001];
long long dp[100001];
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%lld",&a[i]);
}
dp[1] = a[1];
for(int i=2;i<=n;i++) {
if(a[i]+dp[i-1]>a[i]) dp[i] = dp[i-1]+a[i];
else dp[i] = a[i];
}
long long res = dp[1];
for(int i=2;i<=n;i++) {
if(dp[i]>res) res = dp[i];
}
printf("%lld",res);
}
연속합2 (13398번 문제)
이 문제는 위의 문제와 완벽하게 동일하지만 수1개를 제거할 수 있다. 그냥 쉽게 제거할 수를 하나 선택하고 제거한 다음 위와 같이 구하면 O(백만) 나와서 시간안에 절대로 못푼다!
이 문제는 하나의 제거할 대상을 두고 오른쪽에서부터 dr 을 구하고 왼쪽에서부터 dl 을 구하는 방식으로 풀어나가야 한다. 결과값은 dr 과 dl 을 합친 값이 된다.
- 먼저 일반적인 방식으로 왼쪽에서부터 모든 부분합의 값을 구한다.
- 오른쪽부터 시작해서 구하는 부분합을 구해놓는다.
- 일반적인 부분합과, 하나를 제거하고 왼쪽과 오른쪽을 연결한 부분합 중 가장 큰 값을 결과값에 넣고 출력한다.
코드는 다음과 같다
#include <stdio.h>
long long a[100001];
long long dl[100001];
long long dr[100001];
int main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%lld",&a[i]);
}
dl[1] = a[1];
dr[n] = a[n];
for(int j=2;j<=n;j++) {
if(dl[j-1]>0) dl[j] = dl[j-1]+a[j];
else dl[j] = a[j];
}
for(int j=n-1;j>0;j--) {
if(dr[j+1]>0) dr[j] = dr[j+1]+a[j];
else dr[j] = a[j];
}
long long res = dl[1];
for(int i=2;i<=n;i++) {
if(dl[i]>res) res = dl[i];
}
for(int i=2;i<n;i++) {
if(dl[i-1]+dr[i+1]>res) res = dl[i-1]+dr[i+1];
}
printf("%lld",res);
}
제곱수의 합 (1699번 문제)
주어진 N을 제곱수들의 합으로 표현할 때 그 항의 최소개수를 구하는 문제이다.
여기서 D[N]은 항의 개수이다. 그런데 더해진 마지막 수가 뭔지를 알 수가 없다. 편의상 i^2 이라고 한다면, D[N] = min(D[N-i^2] +1) 이라고 할 수 있다. 여기서 i^2 은 1보다 커야하고, N보다 작아야 한다. 따라서 점화식은 다음과 같다.
D[N] = min(D[N-i^2] +1) (1<=i^2<=N)
코드는 다음과 같다
#include <stdio.h>
int d[100001];
int main() {
int n;
scanf("%d",&n);
for (int i=1; i<=n; i++) {
d[i] = i;
for (int j=1; j*j <= i; j++) {
if (d[i] > d[i-j*j]+1) {
d[i] = d[i-j*j]+1;
}
}
}
printf("%d",d[n]);
}
합분해 (2225번 문제)
0~N까지 정수 K개 더해서 그 합이 N이 되는 경우의 수를 구하는 것이다.
D[K][N] = N까지의 정수 K개를 더해서 N을 만드는 경우의 수 라고 하자. 맨 뒤에 더해진 값이 L이라고 한다면, D[K][N] = sum(D[K-1][L] + 1) (0<=L<=N) 이다.
이 방법은 N^3 의 시간 복잡도가 나오게 되는데, 더 빠르게 풀 수 있는 방법이 있다. 이 점화식을 그림으로 그려보고 D[K][N] 을 파악해보면 다음과 같다.
다음과 같이 D[K][N] = D[K][N-1] + D[K-1][N] 이 된다.
코드는 다음과 같다
#include <stdio.h>
long long d[201][201];
long long mod = 1000000000;
int main() {
int n, k;
scanf("%d %d",&n,&k);
d[0][0] = 1;
for (int i=1; i<=k; i++) {
for (int j=0; j<=n; j++) {
for (int l=0; l<=j; l++) {
d[i][j] += d[i-1][j-l];
d[i][j] %= mod;
}
}
}
printf("%lld\n",d[n][k]);
}
Comments