좀 더 어려운 DP 문제랄까...☆ 집에서 맨날 코딩만 하니까 뭔가 좋고 싫어..ㅋㅋㅋㅋㅋ 양갱이랑 또 맥주마시러 가고싶당 우리 집앞에 맥주집 짱마싯는데 코로나 확진자 동선이 약간 가까워서 사리는중 ㅜㅅㅜ
+) ㅋㅋㅋㅋㅋㅋㅋ에어팟 2세대 사버렸닼ㅋㅋㅋ 쿠팡으로 결제하면 결제화면 안나오고 바로 결제되서 항상 기분이 엥..?함 알바와 공부 둘 다 열심히 해야겠다 이제... 이번달 돈 진짜 짱마니썼어..
<11053번 / 가장 긴 증가하는 부분 수열>
수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 이는 영어로 LIS(Longest Increasing Subsequence)라고 한다. 이 문제는 이전 문제와 달리 점화식을 먼저 구하지 않고 표로 먼저 구한 뒤 문제를 풀어보자.
A[i]는 실제 수열의 숫자고, D[i]는 A[i]를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이다. 여기서 D[i]는 A[i]가 반드시 포함되어야 한다. 가장 긴 부분 수열이 A[?], A[?], ..., A[j], A[i]라고 했을 때 A[?] ~ A[j]는 D[j]로 나타낼 수 있다. 이 때 A[j] < A[i]가 되어야 한다. 왜? 증가수열이니까!!!
그럼 위 표에서 D[i]를 순서대로 구해보면 우선 D[i]는 무조건 1이 초기값이고 이전에 A[i]보다 작은 값이 있으면 그 값의 D[j]값을 D[i]에 더한다. 그래서 구한 값 중에서 가장 큰 값이 D[i]가 된다.
위에서 말한 방법을 반복하여 D[i]를 모두 구한다. 이 때 n을 입력받을 때 정답은 D[n]이 아니라 max(D[n])이다. 그럼 이를 통해 점화식을 구해보자. 여기서 A[i]앞의 수가 무너지 모르니까 변수로 두면 D[i] = A[1], A[2], ..., A[j], A[i]가 된다. 그러면 A[j]는 D[j]의 최댓값과 같고 A[i]는 그 값에 1을 더해주면 된다. (1은 i번째 수의 값이다.) 이 때 j의 조건은 j<i, A[j]<A[i]이다. 이 문제의 시간 복잡도는 문제개수 * j를 찾는 경우의 수이므로 N * N이므로 O(N^2)이다.
자 이제 내가 코드를 구현해볼게 하나 둘 셋 얍
알고리즘은 강의대로 사용하였고 max_element함수를 통해 배열의 최댓값을 구했다. 함수에는 배열의 이름과 배열 + 배열의 사이즈를 입력하면 된다. 그리고 출력할때는 max_element앞에 *을 붙혀서 포인터의 값을 반환해야 한다.
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX 1000
long long a[MAX];
long long d[MAX];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
a[0] = 0;
d[0] = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
for (int i = 1; i <= n; i++)
{
d[i] = 1;
for (int j = 1; j <= i; j++)
{
if (a[j] < a[i] && d[i] < d[j] + 1)
{
d[i] = d[j] + 1;
}
}
}
cout << *(max_element(d, d + MAX)) << '\n';
return 0;
}
<14002번 / 가장 긴 증가하는 부분 수열 4>
이번에 위의 문제에서 조금 바뀐건데 수열의 길이가 아니라 그 수열을 구하는 문제이다. 이는 역추적 방법을 사용하면 되는데 역추적은 하나의 값이 바뀔때마다 왜 바뀌었는지 기록해두면 원래의 정답을 찾을 수 있다. 그래서 위의 문제에서 V[i] 배열을 추가하여 그 배열에 이전 수열의 인덱스를 저장한 후 출력할 때 역추적하여 출력하면 된다.
이제 코드를 또 구현해볼게 하나 둘 셋 YAP
아 진짜 위에랑 똑같이 최대값구하고 출력했는데 틀려서 설마,,, 하고 max_element부분을 구해놓은 m으로 출력했더니 맞음.... 알다가도 모를 코딩 World,,,,,☆
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 1000 long long a[MAX]; long long d[MAX]; long long v[MAX]; void go(int p) { if (p == 0) return; go(v[p]); cout << a[p] << ' '; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; a[0] = 0; d[0] = 0; v[0] = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { d[i] = 1; v[i] = 0; for (int j = 1; j <= i; j++) { if (a[j] < a[i] && d[i] <= d[j] + 1) { d[i] = d[j] + 1; v[i] = j; } } } int p = 1; int m = 0; for (int i = 1; i <= n; i++) { if (m < d[i]) { m = d[i]; p = i; } } cout << m << '\n'; go(p); cout << '\n'; return 0; } |
cs |
<1912번 / 연속합>
n개의 정수로 이루어진 임의의 수열이 주어지는데, 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 이 때는 앞의 수와 연속하는 경우와 그렇지 않은 경우로 나눠서 문제를 해결하면 된다. 이 문제에서 제일 조심해야할것은 수열에 음수가 있다는 점이다. 음수가 있으면 작아져서 당연히 포함이 안된다고 생각할 수 있지만, 음수가 포함되어 연속해야 하는 경우도 있기 때문에 조심해줘야 한다.
D[i]를 i번째 수로 끝나는 가장 큰 연속합이라고 하자. 그러면 i번째 수에게 가능한 경우를 세야 한다. i번째 수에 가능한 경우는 두 가지이다.
1. i-1번째 수의 연속합에 포함되는 경우 -> D[i-1] + A[i]
2. 새로운 연속합을 시작하는 경우 -> A[i]
i번째수에는 두가지 경우 중 큰 값을 넣으면 된다.
>D[i] = max(D[i-1]+A[i],A[i])
A[i] 배열에는 실제 입력받은 수를 저장하고, D[i]에는 i번째 수로 끝나는 가장 큰 연속합으로 하면 아래의 표처럼 표현할 수 있다. (위의 A[i] 경우 중 큰 값으로 D[i] 설정)
다 구하고 D[i]의 최댓값이 답이 된다. 이 문제는 N번 반복하면 되기 때문에 시간복잡도는 O(N)이다.
코드 구현 ㄱ
아 초기화 진짜... 전체 배열이 음수인 경우 생각안하고 max 0으로 초기화했더니 틀려써.. 틀리는거 아주그냥 지교와 죽겄어 으휴으휴
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 100000 long long d[MAX]; long long a[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } int max = a[0]; for (int i = 0; i < n; i++) { d[i] = a[i]; if (i == 0) continue; if (d[i] < d[i - 1] + a[i]) { d[i] = d[i - 1] + a[i]; } if (max < d[i]) { max = d[i]; } } cout << max << '\n'; return 0; } |
cs |
<1699번 / 제곱수의 합>
주어진 자연수 N을 제곱수들의 합으로 표현할때에 그 항의 최소개수를 구하는 문제이다. 이 문제도 맨 마지막항에 집중해서 문제를 해결하면 된다. 이 때 마지막항에 뭐가 올지 모르기 때문에 i^2이라고 둔다.(제곱수니까) 그러면 이전에는 N-i^2이 된다. 여기서 D[N]을 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수라고 하고, 마지막항을 i^2이라고 하면 점화식은 다음과 같다.
>D[N] = min(D[N-i^2] + 1) 항의 개수니까 i^2은 1개의 항, 따라서 1을 더해준다.)
이 때 i^2의 범위는 1<=i^2<=N이다. 따라서 시간복잡도는 문제개수 N과 i를 구하는 방법의 개수 루트N이다. 따라서 둘을 곱하면 O(N루트N)이다.
만약 항의 최소개수가 아니라 합으로 표현하는 방법의 수를 구한다면 D[N] = D[N-i^2]의 전체의 합이다.
코구기(코드 구현 기 라는뜻... (퍽)ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ)
여기서 최소값을 배열에 저장하기 때문에 배열의 초기화값을 잘 설정해야 하는데 d[i]는 아무리 커도 i를 못넘기 때문에 최댓값인 i로 초기화한다.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 100000 long long d[MAX]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> 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; } } } cout << d[n] << '\n'; return 0; } |
cs |
<2225번 / 합분해>
0부터 N까지 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제이다. 점화식을 다음과 같이 세워서 문제를 풀어보자
> D[K][N] = 0부터 N까지 정수 K개를 더해서 그 합이 N이 되는 경우의 수
이 문제도 마지막에 더해지는 수에 집중을 해보자. 마지막에 더해지는 수가 뭔지 모르니까 이걸 L이라고 한다. (0<=L<=N) 그러면 앞에 합은 N-L이고 이는 D[K-1][L-1]로 표현할 수 있다. 따라서 점화식은 이거다.
>D[K][L] = D[K-1][L-1]의 모든 합 (0<=L<=N)
여기서 문제의 개수는 K개를 N번 반복해야하니까 KN개이고 문제 1개를 푸는데, 즉 L을 찾는데 N이 걸리니까 시간복잡도는 O(KN^2)이 된다.
코구기
와 런타임에러,,,돌았나,,,, n이랑 k 최댓값이 200인데 max를 200으로 설정했더니 런타임에러만 세번남. 뭐지뭐지하다가 엥 설마하고 고쳤더니 진짜였어ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 짜증나ㅠㅠㅠㅠ 하지만 해결했지
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> #include <algorithm> using namespace std; #define MAX 201 long long d[MAX][MAX]; #define mod 1000000000 int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int k, n; cin >> n >> k; d[0][0] = 1LL; 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; } } } cout << d[k][n] << '\n'; return 0; } |
cs |
여기서 1LL이 뭔지 찾아봤는데 아래와 같다고 한다. 음 int형을 long long으로 바꿔서 오류를 방지한다고 한다.
에고 끝났당
'코딩테스트 > 알고리즘 기초 강의' 카테고리의 다른 글
| 1강 브루트 포스 - 브루트 포스 (0) | 2020.08.27 |
|---|---|
| 4강 다이나믹 프로그래밍 1 - 연습 (0) | 2020.08.25 |
| 4강 다이나믹 프로그래밍 1 - 이친수까지 (0) | 2020.08.22 |
| 4강 다이나믹 프로그래밍 1 - 1, 2, 3 더하기까지 (0) | 2020.08.22 |
| 4강 다이나믹 프로그래밍 1 - 다이나믹 프로그래밍 소개 (0) | 2020.08.21 |
댓글