백준 BOJ 20162번 : 간식 파티
문제 난이도 : Silver II
알고리즘 분류 : DP
문제에 조건이 앞쪽에 숨겨져 있는데, 잘 보면 이전에 먹은 간식보다 점수가 높은 간식만 먹는다는 조건이 있다.
따라서 이 문제는 합이 가장 큰 증가하는 부분 수열 문제가 된다.
마지막에 답을 출력할 때 dp[N-1]이 아닌 모든 dp 값 중 최댓값을 출력해야 함에 유의하자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
vector<int> dp(v);
for(int i=0; i<N; i++)
for(int j=0; j<i; j++)
if(v[i] > v[j]) dp[i] = max(dp[i], dp[j] + v[i]);
int ans = INT_MIN;
for(int i=0; i<N; i++) ans = max(ans, dp[i]);
cout << ans << "\n";
}
백준 BOJ 21555번 : 빛의 돌 옮기기
문제 난이도 : Silver II
알고리즘 분류 : DP
돌을 가지고 가는 방법과 그 때 드는 힘이 A_i와 B_i 두 가지가 있고, 이 때 i는 각 구간 1 ~ N을 나타낸다고 하며, 옮기는 방법을 바꿀 경우 드는 에너지 K가 있을 때 모든 구간을 통과할 수 있는 최소 힘을 구하는 문제이다.
DP 분야의 문제들을 풀어봤다면 백준 BOJ 1149번 : 'RGB 거리'를 풀어봤을 확률이 매우 높은데, 그 문제와 동일한 방식의 문제이다.
dp 배열을 단순히 1차원으로 두지 않고 2차원으로 두어 dp[i][j] = 'i번째까지 왔을 때 마지막에 j번째 방법으로 이동시키고 있을 때 현재 까지 든 최소 힘' (j = 0 or 1)으로 정의하여 점화식을 세우면 된다.
v[i]를 A_i, u[i]를 B_i라고 하면 점화식은 다음과 같아진다.
dp[i][0] = min(dp[i-1][0], dp[i-1][1] + M) + v[i];
dp[i][1] = min(dp[i-1][1], dp[i-1][0] + M) + u[i];
이를 토대로 풀이 코드를 작성하면 다음과 같이 풀이할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N), u(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<N; i++) cin >> u[i];
vector<vector<int>> dp(N, vector<int>(2));
dp[0][0] = v[0], dp[0][1] = u[0];
for(int i=1; i<N; i++) {
dp[i][0] = min(dp[i-1][0], dp[i-1][1] + M) + v[i];
dp[i][1] = min(dp[i-1][1], dp[i-1][0] + M) + u[i];
}
int ans = min(dp[N-1][0], dp[N-1][1]);
cout << ans << "\n";
}
백준 BOJ 22971번 : 증가하는 부분 수열의 개수
문제 이름 그대로 수열이 주어질 때, 1 ~ N의 모든 i에 대해 1 ~ i까지의 부분 수열 중에서 증가하는 부분 수열의 개수를 구하는 문제이다. (즉, 답이 N개의 정수로 출력되어야 한다.)
N이 5,000 이하이므로 O(N^2) 풀이를 할 수가 있고, 따라서 이를 보자마자 증가하는 i에 대해 i보다 작은 j를 잡아 모든 j와 i의 쌍을 검사할 생각을 해주어야 한다.
풀이 코드는 다음과 같으며, mod를 사용해야 함에만 주의해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
vector<int> dp(N, 1);
int mod = 998244353;
for(int i=0; i<N; i++)
for(int j=0; j<i; j++)
if(v[j] < v[i]) dp[i] = (dp[i] + dp[j]) % mod;
for(int i=0; i<N; i++) cout << dp[i] << " ";
cout << "\n";
}
A_i가 5,000 이하이므로 해시를 사용한 집합과 맵을 이용하여 풀이할 수도 있을 것 같다.
또한 문제나 코드의 조건식을 수정함에 따라 감소하는 부분 수열, 증가하는 "연속하는" 부분 수열, 비감소하는 부분 수열 등으로 문제를 응용해서 낼 수 있을 것 같다.
백준 BOJ 10748번 : Cow Hopscotch
문제 난이도 : Silver I
알고리즘 분류 : DP
규칙에 따라서 소가 맨 왼쪽 맨 위 칸에서 맨 오른쪽 맨 아래 칸까지 이동하는 경우의 수를 구하는 문제인데, 규칙은 다음과 같다.
소는 다음의 조건을 모두 만족하는 이동만 가능하다.
1. 이동하려는 칸의 숫자가 현재 칸의 숫자와 달라야 한다.
2. 이동하려는 칸이 현재 칸보다 오른쪽 아래에 있어야 한다.
위의 조건만 만족하면 되므로 소는 거리가 얼마가 되었던 이동이 가능하며, 조금 생각을 해보면 첫 칸을 제외한 1행과 1열의 칸은 거쳐갈 일이 없으며, 도착점을 제외한 N행과 M열 역시 거쳐갈 일이 없다.
그리고 범위를 보면 R과 C가 100 이하로 매우 작으므로, O(N^2 M^2)의 풀이가 가능하다.
따라서 DP를 이용하되 각 칸에 대해, 해당 칸보다 왼쪽 위에 있는 모든 칸들에 대해 검사를 하고 그 경우의 수를 현재 칸의 경우의 수에 더해주면 된다.
모듈로 연산이 있으므로 주의하자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
vector<vector<int>> v(N, vector<int>(M));
for(int i=0; i<N; i++)
for(int j=0; j<M; j++) cin >> v[i][j];
vector<vector<int>> dp(N, vector<int>(M));
dp[0][0] = 1;
for(int i=1; i<N; i++)
for(int j=1; j<M; j++)
for(int k=0; k<i; k++)
for(int l=0; l<j; l++)
if(v[k][l] != v[i][j]) dp[i][j] = (dp[i][j] + dp[k][l]) % (int)(1e9 + 7);
cout << dp[N-1][M-1] << "\n";
}
백준 BOJ 12037번 : Polynesiaglot (Small1), 백준 BOJ 12038번 : Polynesiaglot (Small2), 백준 BOJ 12039번 : Polynesiaglot (Large)
세 문제 모두 같은 문제이고, 범위만 다르므로 가장 범위가 큰 12039번 문제를 기준으로 다룬다.
문제 난이도 : Silver I
알고리즘 분류 : DP
자음의 개수, 모음의 개수, 만들 문자열의 길이가 주어지는데 모든 자음 뒤에는 모음이 오는 문자열의 개수가 몇 개인지 구하는 문제이다.
점화식을 세워야 하는데, 1차원 dp 배열로는 풀기가 까다로우므로 길이가 k인 문자열의 개수 dp[k]를 2개로 나누어 길이가 k인데 규칙을 만족하며 자음이 맨 뒤에 오는 문자열의 수를 dp[k][0]으로 두고 (물론 맨 뒤의 자음이 규칙을 만족하지 않지만 여기서는 무시한다.) 길이가 k인데 규칙을 만족하며 모음이 맨 뒤에 오는 문자열의 수를 dp[k][1]로 둔다.
우리는 dp[L][1]을 답으로 출력해주면 된다.
세팅을 위와 같이 해주면 이제 점화식은 간단하다.
dp[i][0] = (dp[i-1][1] * N) % mod;
dp[i][1] = ((dp[i-1][0] + dp[i-1][1]) * M) % mod;
자음 뒤에는 모음만 올 수 있지만, 모음 뒤에는 자음과 모음이 모두 올 수 있으므로 위와 같은 점화식을 얻을 수 있다.
이제 O(N) 시간에 계산해준 뒤 답을 출력해주기만 하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mod = (int)(1e9 + 7);
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
for(int t=1; t<=T; t++) {
int N, M, K; cin >> N >> M >> K;
int dp[K+1][2] = {{0, 0}, {N, M}, {M * N, (N + M) * M}};
for(int i=3; i<=K; i++) {
dp[i][0] = (dp[i-1][1] * N) % mod;
dp[i][1] = ((dp[i-1][0] + dp[i-1][1]) * M) % mod;
}
cout << "Case #" << t << ": " << dp[K][1] << "\n";
}
}
참고로 이 문제는 범위가 다른 세 개의 동일한 문제가 존재하므로 12039번 Large 문제를 푼 뒤 나머지 문제에 같은 소스 코드를 제출하면 3문제를 정답으로 인정받을 수 있다.
백준 BOJ 12175번 : Dreary Design (Small), 백준 BOJ 12176번 : Dreary Design (Large1), 백준 BOJ 12177번 : Dreary Design (Large2)
역시 구글 CodeJam 기출의 세트 문제로 범위만 다르고 문제는 같으므로 범위가 가장 큰 12177번 문제를 기준으로 풀이한다.
문제 난이도 : Silver I
알고리즘 분류 : 조합론, 포함 배제의 원리
K와 V가 주어질 때, 0 ~ K에서 3개의 값을 선택했을 때 그 최댓값과 최솟값의 차이가 V 이하로 나타나는 조합의 수를 구하는 문제이다. 이 때 3개의 값은 순서쌍으로써 선택 순서에 영향이 있습니다. (즉, Combination이 아닌 거듭제곱으로 경우의 수 계산)
0 ~ K에서 0 ~ V 구간을 잡을 수 있는 경우의 수는 위와 같이 K-V+1가지이고, RGB 각각의 값에 대해 V+1의 선택지가 있으므로 중복을 고려 안하고 세주면 (V+1)^3 × (K-V+1)이 된다.
그런데 위와 같이 구간을 작대기로 나타내어 생각해보면, 겹치는 길이 V짜리 구간을 K-V개 빼주면 겹치는 구간이 없이 모든 구간의 합집합만 남게된다.
따라서 답은 (V+1)^3 × (K-V+1) - V^3 × (K-V)로 간단하게 얻어진다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
for(int t=1; t<=T; t++) {
int K, V; cin >> K >> V;
int ans = (V+1)*(V+1)*(V+1)*(K-V+1) - V*V*V*(K-V);
cout << "Case #" << t << ": " << ans << "\n";
}
}
백준 BOJ 1976번 : 여행 가자
문제 난이도 : Gold IV
알고리즘 분류 : 그래프 탐색, 분리 집합
N개의 도시가 있고, 이들의 연결 관계가 N*N 인접 행렬로 주어진다고 할 때, M개의 도시를 여행할 수 있는지의 여부를 구하는 문제이다.
즉, M개의 도시가 서로 연결 관계임만 확인하면 되므로 분리 집합(disjoint set, union find) 문제임을 알 수 있다.
인접 행렬을 이용해 그래프를 연결해주고 마지막 줄 입력에 대해 연결 관계만 확인해주면 된다.
(분리 집합 구현을 까먹어서 연결할 때 v[f(i)] = f(j)와 같이 루트 노드끼리 연결해주어야 하는데 v[i] = j처럼 연결해버려서 계속 틀렸다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
int x; cin >> x;
if(x == 1 && f(i) != f(j)) v[f(i)] = f(j);
}
vector<int> u(M);
for(int i=0; i<M; i++) cin >> u[i];
bool check = true;
for(int i=1; i<M; i++)
if(f(u[i]) != f(u[i-1])) check = false;
if(check) cout << "YES\n";
else cout << "NO\n";
}
백준 BOJ 4195번 : 친구 네트워크
문제 난이도 : Gold II
알고리즘 분류 : 분리 집합, 해시를 사용한 집합과 맵
친구 목록이 추가될 때마다 그 친구들이 속한 그룹에 속한 총 친구들의 수를 쿼리 형식으로 계속해서 출력하는 문제이다.
연결 관계를 추가하고 그 때마다 해당 집합의 크기를 구해주면 되는 분리 집합 문제이다.
다만 노드가 숫자로 주어지는 것이 아닌 문자열로 주어지기 때문에 해시맵을 사용해야 한다.
큰 차이가 없는데 괄호 한두 개 더 사용하는 것 때문에 헷갈려서 실수를 많이 했다.
특히 집합의 크기를 구하는 핵심 아이디어는 배열을 따로 하나 더 선언해서 root 노드에 그 집합의 크기를 저장해주는 것인데, 연결을 먼저 하고 크기를 더해주는 바람에 오답 처리를 받았다.
연결을 먼저 할 경우 두 노드의 루트가 같아지므로 (크기가 단순히 2배가 되어버리므로) 크기를 먼저 합치고 두 집합을 연결해주어야 한다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v;
int f(int x) {
if(v[x] == x) return x;
else return v[x] = f(v[x]);
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
while(T--) {
int N; cin >> N;
v.clear();
v.resize(200001);
for(int i=1; i<=200000; i++) v[i] = i;
vector<int> u(200001, 1);
map<string, int> m;
int cnt = 1;
while(N--) {
string a, b; cin >> a >> b;
if(m[a] == 0) m[a] = cnt++;
if(m[b] == 0) m[b] = cnt++;
if(f(m[a]) != f(m[b])) {
u[f(m[a])] += u[f(m[b])];
v[f(m[b])] = f(m[a]);
}
cout << u[f(m[a])] << "\n";
}
}
}
백준 BOJ 1990번 : 소수인팰린드롬
문제 난이도 : Gold V
알고리즘 분류 : 정수론, 문자열(?)
1 ~ 1억 사이의 a와 b가 주어질 때 a 이상 b 이하의 팰린드롬 소수를 모두 찾는 문제이다.
배열 크기를 1억으로 잡으면 메모리 초과가 발생하고, 그렇다고 브루트포스로 소수 판별을 하자니 시간 초과가 발생한다.
이 문제의 정석 풀이는 짝수 팰린드롬의 성질을 이용하는 것인데, 짝수 팰린드롬 수는 모두 11의 배수라는 특성을 가지고 있다.
풀이를 보고 이걸 어떻게 알아!! 라고 생각했지만, 잘 생각해보니 1 ~ 10000 사이의 수에 대해 각 수의 뒤에 그 수를 뒤집은 수를 적당히 붙여서 (한 자리 자르고 붙이거나 해서) 팰린드롬 수를 먼저 만들고 그 다음 소수 판별을 하면 되겠다는 생각이 들었다.
아무튼 핵심은 정수론을 잘하면 좋다는 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
vector<bool> prime((int)(1e7 + 1), true);
prime[1] = false;
for(int i=2; i*i<=(int)(1e7); i++)
for(int j=2; i*j<=(int)(1e7); j++) prime[i*j] = false;
int a, b; cin >> a >> b;
if(b > (int)(1e7)) b = (int)(1e7);
for(int i=a; i<=b; i++) {
if(!prime[i]) continue;
string str = to_string(i);
bool check = true;
for(int j=0; j<str.length()/2; j++)
if(str[j] != str[str.length()-1-j]) check = false;
if(check) cout << i << "\n";
}
cout << -1 << "\n";
}
+ 2022.07.15 수정 ) 코드가 잘못 올라와 있어서 다시 수정했다.
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 220716 PS 일기 : 조합론(DP), 카탈란 수 문제들 위주 풀이 (0) | 2022.07.16 |
|---|---|
| 220715 PS 일기 : 탐색(DFS, BFS, 백트래킹), 그리디 쉬운 문제들 (실버 ~ 골드) (0) | 2022.07.15 |
| 220713 PS 일기 : 각종 DP 문제들 풀이 (O(N^2) 실버~골드 난이도) (0) | 2022.07.13 |
| 220712 PS 일기 : 교차 개수 세기, 문자열 조합 DP, 누적 합 활용 등 (0) | 2022.07.12 |
| 금광 세그먼트 트리 : 2차원 배열의 최대 구간 합 알고리즘 (설명, 예제 코드) (0) | 2022.07.10 |