백준 BOJ 4383번 : 점프는 즐거워
문제 난이도 : Silver V
알고리즘 분류 : 구현
길이 N인 수열이 주어질 때 인접한 N-1개의 정수 쌍에 대해 그 차이의 절댓값이 1 ~ N-1까지 모두 등장하는 수열인지 아닌지를 판별하는 문제이다.
간단한 구현 문제인데 정답률이 24%밖에 되지 않아 반례가 있나 싶었는데, 첫 제출에 간단하게 정답 처리를 받은 것으로 보아 EOF까지 입력받는 처리가 까다로워서 많은 사람들이 틀리지 않았나 싶다.
#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;
while(cin >> N) {
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
vector<bool> u(N);
for(int i=1; i<N; i++) u[abs(v[i] - v[i-1])] = true;
bool check = true;
for(int i=1; i<=N-1; i++)
if(!u[i]) check = false;
if(check) cout << "Jolly\n";
else cout << "Not jolly\n";
}
}
백준 BOJ 2477번 : 참외밭
문제 난이도 : Silver III
알고리즘 분류 : 구현, 기하학
모든 변이 x축과 y축에 평행한 육각형이 변의 방향과 길이로 주어질 때, 참외의 개수를 구하는 문제이다.
참외의 개수 = 육각형 면적 × 단위 면적 당 참외의 개수로 구할 수 있으므로, 육각형의 면적을 구하기만 하면 된다.
잘 생각해보면 나올 수 있는 육각형의 형태는 한 쪽 모서리가 들어간 직사각형뿐이다.
따라서 모서리가 들어간 쪽을 어떻게 찾을지만 구현을 해주면 된다.
나의 경우는 별다른 풀이가 생각나지 않아서 3 → 1 → 3 → 1과 같이 가로 세로 방향으로 두 번 꺾는 부분을 찾아서 그 부분의 면적을 빼주는 방식을 사용했다.
#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<pair<int, int>> v(12);
for(int i=0; i<6; i++) cin >> v[i].first >> v[i].second;
for(int i=6; i<12; i++) v[i] = v[i-6];
int a, dir1, dir2;
for(int i=3; i<12; i++)
if(v[i].first == v[i-2].first && v[i-1].first == v[i-3].first) {
a = v[i-2].second * v[i-1].second;
dir1 = v[i-2].first;
dir2 = v[i-1].first;
break;
}
int b, c;
bool check = false;
for(int i=0; i<6; i++) {
if(v[i].first != dir1 && v[i].first != dir2) {
if(!check) {
b = v[i].second;
check = true;
}
else c = v[i].second;
}
}
int ans = (b*c - a) * N;
cout << ans << "\n";
}
혹시나 해서 길이가 짧은 코드의 다른 풀이도 봤는데 다들 비슷비슷하게 구현한 것 같다.
백준 BOJ 1358번 : 하키
문제 난이도 : Silver IV
알고리즘 분류 : 기하학
주어진 도형 안에 입력되는 좌표의 점이 몇 개나 있는지를 구하는 문제이다.
문제 앞 부분에 1초마다 사진을 찍는다는 문구가 있는데 문제에는 의미 없는 문구이다.
단순히 직사각형과 그 양쪽에 붙은 반원 2개의 범위에 점이 몇 개 들어가 있는지만 세어주면 된다.
조건문을 복잡하지 않게 작성하는 방법은, check라는 bool 변수를 활용하여 하나라도 조건이 만족할 경우 true로 바꾸어주고 마지막에 check = true인지만 검사해주는 것이다.
그리고 double과 같은 실수형 자료형을 사용할 때는 루트로 비교하기보다는 제곱으로 비교해주는 것이 오차를 유발하는 극악의 데이터가 들어왔을 때에도 문제 없이 통과 가능하다.
#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 W, H, X, Y, N;
cin >> W >> H >> X >> Y >> N;
int ans = 0;
while(N--) {
double x, y; cin >> x >> y;
bool check = false;
if(x >= X && x <= X+W && y >= Y && y <= Y+H) check = true;
if(pow(x - X, 2) + pow(y - (Y+(H/2)), 2) <= pow(H/2, 2)) check = true;
if(pow(x - (X+W), 2) + pow(y - (Y+(H/2)), 2) <= pow(H/2, 2)) check = true;
if(check) ans++;
}
cout << ans << "\n";
}
백준 BOJ 24479번 : 알고리즘 수업 - 깊이 우선 탐색 1
문제 난이도 : Silver II
알고리즘 분류 : DFS
DFS를 수행하면서 1 ~ N번 정점에 대해 각각 몇 번째로 방문했는지를 구하는 문제이다.
다른 알고리즘 수업 문제는 문제 예시로 주어지는 함수 형태를 거의 비슷하게 따라가야 했는데 DFS는 어떻게 구현하든 그 형태가 거의 비슷하므로 DFS 함수를 구현할 줄 알면 쉽게 풀 수 있는 문제이다.
초기에 방문 순서에 대한 배열을 0으로 초기화해주고, 전역 변수 cnt = 1로 둔 뒤 DFS가 호출될 때마다 해당 정점에 대해 방문 순서를 cnt로 두고, cnt를 1씩 증가시켜 나가면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
vector<int> ans;
int cnt = 1;
void f(int x) {
vis[x] = true;
ans[x] = cnt++;
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(!vis[y]) f(y);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
adj.resize(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=N; i++)
sort(adj[i].begin(), adj[i].end());
vis.resize(N+1, false);
ans.resize(N+1);
f(K);
for(int i=1; i<=N; i++) cout << ans[i] << "\n";
}
백준 BOJ 24480번 : 알고리즘 수업 - 깊이 우선 탐색 2
문제 난이도 : Silver II
알고리즘 분류 : DFS
위의 문제와 거의 동일하며, 방문하는 정점의 순서만 번호의 내림차순으로 방문하면 된다.
main 함수에서 정점을 정렬할 때 오름차순으로 정렬하던 것을 내림차순으로 정렬해주기만 하면 된다.
sort 함수에서 greater<int>()만 사용할 줄 안다면 거저 주는 문제이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
vector<int> ans;
int cnt = 1;
void f(int x) {
vis[x] = true;
ans[x] = cnt++;
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(!vis[y]) f(y);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
adj.resize(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=N; i++)
sort(adj[i].begin(), adj[i].end(), greater<int>());
vis.resize(N+1, false);
ans.resize(N+1);
f(K);
for(int i=1; i<=N; i++) cout << ans[i] << "\n";
}
백준 BOJ 24444번 : 알고리즘 수업 - 너비 우선 탐색 1
문제 난이도 : Silver II
알고리즘 분류 : BFS
그래프가 주어지고 이를 BFS로 탐색했을 때 각 정점이 몇 번째로 방문되는지를 출력하는 문제이다.
위의 문제와 비슷하게 DFS 대신 BFS를 구현해주면 된다.
오름차순으로 방문한다고 조건이 주어졌으므로 adj 벡터에서 각 정점에 대해 연결된 정점을 오름차순으로 정렬해주고 BFS를 수행한다.
BFS는 재귀적으로 수행되는 알고리즘이 아니므로 별도의 함수를 구현할 필요는 없다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
vector<int> ans;
int cnt = 1;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
adj.resize(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=N; i++)
sort(adj[i].begin(), adj[i].end());
vis.resize(N+1, false);
vis[K] = true;
queue<int> q;
q.push(K);
ans.resize(N+1);
while(!q.empty()) {
int x = q.front();
q.pop();
ans[x] = cnt++;
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(vis[y]) continue;
q.push(y);
vis[y] = true;
}
}
for(int i=1; i<=N; i++) cout << ans[i] << "\n";
}
백준 BOJ 24445번 : 알고리즘 수업 - 너비 우선 탐색 2
문제 난이도 : Silver II
알고리즘 분류 : BFS
역시 같은 문제이며, 정점 방문 순서를 내림차순으로만 방문해주면 된다.
즉, sort 함수에서 greater<int>()만 추가해주면 해결된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj;
vector<bool> vis;
vector<int> ans;
int cnt = 1;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M, K; cin >> N >> M >> K;
adj.resize(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
for(int i=1; i<=N; i++)
sort(adj[i].begin(), adj[i].end(), greater<int>());
vis.resize(N+1, false);
vis[K] = true;
queue<int> q;
q.push(K);
ans.resize(N+1);
while(!q.empty()) {
int x = q.front();
q.pop();
ans[x] = cnt++;
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(vis[y]) continue;
q.push(y);
vis[y] = true;
}
}
for(int i=1; i<=N; i++) cout << ans[i] << "\n";
}
백준 BOJ 16928번 : 뱀과 사다리 게임
문제 난이도 : Gold V
알고리즘 분류 : BFS
주사위를 굴려 나오는 수만큼 이동하여 1번 칸에서 100번 칸까지 이동하는 최소 횟수를 구하는 문제이다.
이 때 뱀을 만나면 특정 숫자에서 다른 숫자로 내려갈 수 있고, 사다리를 만나면 특정 숫자에서 다른 숫자로 올라갈 수 있다.
어떠한 시행을 하는 최소 횟수를 구하는 문제이고, 전체 상태의 범위가 1 ~ 100으로 많지 않으므로 BFS를 사용하여 탐색해줄 수 있다.
만약 뱀이나 사다리를 만나면 다음 지점을 이동할 지점의 숫자로 바꿔준다.
만약 queue에서 pop을 한 값이 100이라면 해당 count 값을 출력하고 종료해준다.
#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<pair<int, int>> v(N+M);
for(int i=0; i<v.size(); i++)
cin >> v[i].first >> v[i].second;
queue<int> q;
q.push(1);
vector<int> vis(101, -1);
vis[1] = 0;
while(!q.empty()) {
int x = q.front();
q.pop();
if(x == 100) {
cout << vis[x] << "\n";
break;
}
for(int i=1; i<=6; i++) {
int y = x + i;
for(int i=0; i<v.size(); i++)
if(y == v[i].first) y = v[i].second;
if(vis[y] != -1) continue;
q.push(y);
vis[y] = vis[x] + 1;
}
}
}
백준 BOJ 3896번 : 소수 사이 수열
문제 난이도 : Silver I
알고리즘 분류 : 에라토스테네스의 체
어떤 수가 주어졌을 때, 그 수를 기준으로 가장 가까운 양쪽의 소수가 갖는 구간의 크기를 구하는 문제이다.
물론 소수가 주어지면 그 크기는 0이 되어야 한다.
입력되는 수의 범위가 1000만 부근 이하이므로, 에라토스테네스의 체를 이용하여 해당 범위 내의 모든 소수를 구해줄 수 있다.
while문을 이용하여 양쪽 범위를 탐색 후 count하여 답을 출력해주면 된다.
#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 Max = 1299710;
vector<bool> prime(Max, true);
prime[1] = false;
for(int i=2; i*i<Max; i++)
for(int j=2; i*j<Max; j++) prime[i*j] = false;
int T; cin >> T;
while(T--) {
int x; cin >> x;
if(prime[x]) {
cout << 0 << "\n";
continue;
}
int ans = 0;
int y = x;
while(!prime[y--]) ans++;
y = x;
while(!prime[y++]) ans++;
cout << ans << "\n";
}
}
백준 BOJ 18429번 : 근손실
문제 난이도 : Silver III
알고리즘 분류 : 백트래킹
매일 감소하는 체중이 있고, 특정 운동을 하면 체중이 특정량만큼 늘어난다고 할 때 체중이 특정 값 아래로 내려가지 않고 운동할 수 있는 조합의 수를 구하는 문제이다.
운동의 종류가 8개 이하이고, 모든 경우를 따져봐도 8!가지 이하이므로 간단한 백트래킹 문제임을 알 수 있다.
따라서 재귀 함수를 구현해주고 조건만 잘 설정해주면 쉽게 해결이 가능하다.
나의 경우에는 함수를 실행하기 전에 if문에서 미리 체중이 500 미만이 되는 경우를 거르고 함수를 돌리는 방식을 선택했다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, M, ans = 0;
vector<int> v;
vector<bool> vis;
void f(int cnt, int cur) {
if(cnt == N) {
ans++;
return;
}
for(int i=0; i<N; i++) {
if(!vis[i] && cur + v[i] - M >= 500) {
vis[i] = true;
f(cnt + 1, cur + v[i] - M);
vis[i] = false;
}
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N >> M;
v.resize(N);
for(int i=0; i<N; i++) cin >> v[i];
vis.resize(N);
f(0, 500);
cout << ans << "\n";
}
백준 BOJ 9660번 : 돌 게임 6
문제 난이도 : Gold V
알고리즘 분류 : 게임 이론
두 명이 N개의 돌을 가지고 게임을 하는데, 1개, 3개, 4개 중 한 가지 개수만큼을 가져갈 수 있고 마지막 돌을 가져가는 사람이 이기는 게임일 때 주어진 N에 대해 누가 이길 수 있는지를 구하는 문제이다.
N이 10^12 이하로 입력될 수 있음으로 보아 돌 게임 5에서 입력되는 변수의 범위가 확장된 버전의 문제로 보인다.
이런 경우에는 규칙성을 찾거나, 스프라그-그런디 정리를 이용하는 방법 등이 있는데 나는 아직 스프라그-그런디 정리에 대해 공부를 하지 않았다.
따라서 다음과 같은 코드로 규칙성을 찾은 뒤 규칙성에 따라 답을 구해보자.
#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;
int v[10001] = {0, 1, 0, 1, 1};
for(int i=5; i<=N; i++) {
if(v[i-1] == 0 || v[i-3] == 0 || v[i-4] == 0) v[i] = 1;
else v[i] = 0;
}
for(int i=1; i<=N; i++) cout << v[i] << " ";
cout << "\n";
}
적당히 N = 30을 입력하여 규칙성을 찾아보자.
N = 1부터 보았을 때 {1, 0, 1, 1, 1, 1, 0}이 반복됨을 알 수 있다.
따라서 N을 7로 나눈 나머지에 대해 답을 구해주면 된다.
풀이 코드는 다음과 같다.
#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;
int v[7] = {0, 1, 0, 1, 1, 1, 1};
if(v[N % 7] == 1) cout << "SK\n";
else cout << "CY\n";
}
배열은 0부터 시작하니 조심하자.
백준 BOJ 12931번 : 두 배 더하기
문제 난이도 : Gold V
알고리즘 분류 : 그리디
모두 0으로 이루어진 상태의 배열에서, 다음의 두 가지 연산을 마음대로 수행하여 최소 횟수로 주어진 배열을 만든다고 할 때 그 횟수를 구하는 문제이다.
1. 원소 중 하나의 값에 1을 더한다.
2. 모든 원소의 값을 2배 한다.
이런 유형의 그리디 문제는 코드포스(Codeforces)의 div. 2 B ~ C번 문제에 자주 나오는 유형이니 많이 풀어두면 유용할 것 같다.
내가 생각한 풀이는 역으로 계산하는 것인데, 주어진 배열을 모두 0으로 만드는 것이다.
모든 원소의 값을 1/2배 하려면 모든 원소가 짝수가 되어 있어야하므로, 우선 모든 홀수 원소를 1 감소시키고 2배로 나누는 연산을 반복하여 답을 구했다.
이 때 배열이 1과 0으로만 이루어져 있다면 1 감소시키고 나서 연산이 끝나므로 2로 나누어주기 전에도 검사를 해야한다.
#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];
int ans = 0;
while(true) {
bool check = true;
for(int i=0; i<N; i++)
if(v[i] > 0) check = false;
if(check) break;
for(int i=0; i<N; i++)
if(v[i] % 2 == 1) {
v[i]--;
ans++;
}
check = true;
for(int i=0; i<N; i++)
if(v[i] > 0) check = false;
if(check) break;
for(int i=0; i<N; i++) v[i] /= 2;
ans++;
}
cout << ans << "\n";
}
백준 BOJ 25332번 : 수들의 합 8
문제 난이도 : Gold III
알고리즘 분류 : 누적 합, 해시를 사용한 집합과 맵
두 수열이 주어질 때, 같은 위치의 연속하는 부분 수열의 합이 같은 구간의 수를 구하는 문제이다.
먼저 a_i - b_i인 c_i 배열을 구해보면, 결과적으로는 c_i에서 구간 합이 0인 부분수열의 개수를 구하는 것과 동치가 된다.
따라서 누적 합에서 값이 같은 2개를 뽑으면, 긴 구간에서 짧은 구간을 빼면 나머지 부분수열의 합이 0이 된다.
즉, 누적 합이 같은 쌍의 조합을 구하면 된다.
이건 해시맵을 이용하여 count 해주고 지금까지 나왔던 수들에 대해서 (나는 벡터에 넣고 중복을 제거하는 방식을 이용했다.) cnt C 2의 조합 연산을 해준 값들의 합을 구하면 답을 얻을 수 있다.
#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), u(N);
for(int i=0; i<N; i++) cin >> v[i];
for(int i=0; i<N; i++) cin >> u[i];
vector<int> w(N);
for(int i=0; i<N; i++) w[i] = v[i] - u[i];
vector<int> sum(N+1);
for(int i=1; i<=N; i++) sum[i] = sum[i-1] + w[i-1];
map<int, int> m;
for(int i=0; i<=N; i++) m[sum[i]]++;
vector<int> l;
for(int i=0; i<=N; i++) l.push_back(sum[i]);
sort(l.begin(), l.end());
l.erase(unique(l.begin(), l.end()), l.end());
int ans = 0;
for(int i=0; i<l.size(); i++)
if(m[l[i]] >= 2) ans += m[l[i]] * (m[l[i]] - 1) / 2;
cout << ans << "\n";
}
백준 BOJ 2015번 : 수들의 합 4
문제 난이도 : Gold IV
알고리즘 분류 : 누적 합, 해시를 사용한 집합과 맵
주어진 수열에 대해 구간 합이 K인 수열의 개수를 구하는 문제이다. (이 때 구간 합은 연속된 부분 수열의 합이어야 한다.)
위의 문제와 같은 시리즈의 문제이고 알고리즘 분류도 같지만 푸는 방법이 조금 다르다.
누적 합 u[i]를 구하고 i=0에서부터 오른쪽으로 이동하면서, 지금까지 나온 누적 합 중에서 u[i] - K 크기의 누적 합을 가지는 부분 수열이 몇 개나 있었는지를 체크하면 된다.
왜냐하면 1 ~ j까지의 누적 합이 u[j]라고 할 때 1 ~ i까지의 누적 합이 u[j] - K인 구간의 값을 빼면 K가 되기 때문이다.
이는 해시를 사용한 집합과 맵을 이용하여 간단히 구현해줄 수 있다.
#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);
for(int i=0; i<N; i++) cin >> v[i];
vector<int> u(N+1);
for(int i=1; i<=N; i++) u[i] = u[i-1] + v[i-1];
map<int, int> m;
int ans = 0;
for(int i=0; i<=N; i++) {
ans += m[u[i] - M];
m[u[i]]++;
}
cout << ans << "\n";
}
백준 BOJ 14620번 : 꽃길
문제 난이도 : Silver II
알고리즘 분류 : 브루트포스
어떤 좌표를 선택하면 그 좌표를 포함한 상하좌우 인접 한 칸씩 꽃이 자리를 차지하게 되고, 땅의 비용이 주어질 때 3개의 꽃이 겹치지 않도록 선택하는 최소 비용을 구하는 문제이다.
꽃의 중심 좌표에 해당하는 3개의 좌표만 브루트포스로 골라주면 나머지는 자동적으로 처리가 되므로, 브루트포스로 풀어주면 된다.
문제는 꽃이 겹치는 경우를 생각을 제대로 못했는데, 단순 상하좌우 1칸 이내에 위치할 때만 겹치는 것이 아니라, 같은 축에 있는 경우 2칸 인접한 경우에도 꽃이 겹치게 된다.
좌표 배열을 사용하면 훨씬 간단한 코드로 풀었을 것 같은데, 그럴만한 가치가 별로 있는 문제는 아니라 그냥 더럽게 풀었다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int N, ans = INT_MAX;
vector<vector<int>> v;
vector<pair<int, int>> u;
void g() {
int sum = 0;
for(int i=0; i<u.size(); i++) {
sum += v[u[i].first][u[i].second];
sum += v[u[i].first + 1][u[i].second];
sum += v[u[i].first - 1][u[i].second];
sum += v[u[i].first][u[i].second + 1];
sum += v[u[i].first][u[i].second - 1];
}
ans = min(ans, sum);
}
void f(int cnt) {
if(cnt == 3) {
g();
return;
}
for(int i=1; i<N-1; i++)
for(int j=1; j<N-1; j++) {
bool check = true;
for(int k=0; k<u.size(); k++) {
if(i >= u[k].first - 1 && i <= u[k].first + 1
&& j >= u[k].second - 1 && j <= u[k].second + 1) check = false;
if(i == u[k].first - 2 && j == u[k].second) check = false;
if(i == u[k].first + 2 && j == u[k].second) check = false;
if(i == u[k].first && j == u[k].second - 2) check = false;
if(i == u[k].first && j == u[k].second + 2) check = false;
}
if(!check) continue;
u.push_back({i, j});
f(cnt + 1);
u.pop_back();
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cin >> N;
v.resize(N, vector<int>(N));
for(int i=0; i<N; i++)
for(int j=0; j<N; j++) cin >> v[i][j];
f(0);
cout << ans << "\n";
}
백준 BOJ 20115번 : 에너지 드링크
문제 난이도 : Silver III
알고리즘 분류 : 그리디
N개의 드링크 중 2개를 합치는 과정에서 하나를 절반 버리고 합치는 과정을 반복할 때, 마지막까지 합쳐진 양이 가장 많도록 합쳤을 때의 양을 구하는 문제이다.
생각해보면 두 용액을 합칠 때 양이 적은 것을 절반 버리는 것이 낫다.
그렇다면, 양이 가장 많은 것을 기준으로 세우고 나머지 N-1개의 용액을 절반씩 버리고 합치는 방법이 가장 낫다. (그리디)
정렬은 굳이 필요 없고 최댓값만 구하면 되는데 시간이 넉넉해서 그냥 정렬을 해주고 코드를 짧게 작성하는 방향으로 풀었다.
#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<double> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end());
double ans = 0;
for(int i=0; i<N-1; i++) ans += v[i]/2;
ans += v[N-1];
cout << fixed;
cout.precision(5);
cout << ans << "\n";
}
백준 BOJ 17352번 : 여러분들의 다리가 되어 드리겠습니다!
문제 난이도 : Gold V
알고리즘 분류 : 분리 집합
N개의 노드를 가지고 N-1개의 간선으로 이루어진 트리에서 간선 하나가 제거된 간선이 N-2개인 그래프가 주어질 때, 트리로 만들기 위해 간선을 연결하면 되는 두 노드를 아무거나 구하면 되는 문제이다.
분리 집합을 이용하여 그래프를 연결해주고, 1번 노드와 연결 관계가 아닌 두 노드를 연결해주기만 하면 쉽게 해결이 가능한 문제이다. (분리된 그래프이므로 1번 노드와 연결되지 않은 노드가 반드시 하나 이상 존재하므로)
#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; cin >> N;
v.resize(N+1);
for(int i=1; i<=N; i++) v[i] = i;
for(int i=0; i<N-2; i++) {
int a, b; cin >> a >> b;
v[f(a)] = f(b);
}
for(int i=2; i<=N; i++)
if(f(1) != f(i)) {
cout << 1 << " " << i << "\n";
break;
}
}
백준 BOJ 20152번 : Game Addiction
문제 난이도 : Silver II
알고리즘 분류 : 조합론, 카탈란 수
격자점 위의 (H, H)에서 (N, N)으로 이동할 때, x < y로만 이동하여 도달하는 경로의 수를 구하는 문제이다.
조합론으로만 따져도 꽤 어려운 것 같은데 난이도가 이렇게 배정되는 이유를 잘 모르겠다.
아무튼 이 문제는 abs(H - N) 값을 1에서부터 4 정도까지만 해봐도 익숙한 수열이 보이는데, 이것이 카탈란 수라는 것을 알면 카탈란 수의 점화식을 이용하여 dp로 쉽게 해결이 된다.
다만 카탈란 수를 모른다면 조합론으로 해결을 하면 되는데, 우선 abs(H - N)을 편의상 그냥 N이라고 하자.
그러면 y = x를 넘어가는 것을 고려하지 않고 모든 경로의 수를 구하면 2N C N이 된다.
여기서 y = x를 넘어가는 경우를 빼주면 되는데, y = x를 넘어가는 경로의 경우 넘어가는 부분에서 경로를 접어주면 원래 도착할 지점보다 왼쪽으로 한 칸, 아래로 한 칸 (아무튼 대각선으로 한 칸) 벗어난 지점에 도달하게 된다.
즉, 이들은 모두 2N C N-1가지 경로에 해당하는 이동 경로에 일대일 대응을 시킬 수 있으므로 최종 답은 2N C N - 2N C 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 v[31] = {1, 1};
for(int i=2; i<=30; i++)
for(int j=0; j<i; j++) v[i] += v[j] * v[i-1-j];
int a, b; cin >> a >> b;
cout << v[abs(a-b)] << "\n";
}
백준 BOJ 17204번 : 죽음의 게임
문제 난이도 : Silver III
알고리즘 분류 : 그래프 탐색
문제를 해석해보면, 0번 노드에서 시작하여 해당 노드가 가리키는 노드로 계속 이동하다가, K번 노드가 나올 때까지 이동한 횟수를 구하는 문제이다.
이는 parent 배열을 만들어 가리키는 노드들을 각각 저장해주고, cnt를 증가시키며 이동하다가 K번 노드를 만났을 때 cnt 값을 출력해주기만 되는 간단한 그래프 탐색 문제이다.
다만 사이클이 존재할 수 있으므로 탐색 종료 조건을 만들어주어야 하는데, 사이클의 최대 크기는 N이므로 넉넉하게 cnt가 N보다 커졌을 때 break 해주면 정답 처리를 받을 수 있다.
#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);
for(int i=0; i<N; i++) cin >> v[i];
int cnt = 1, x = 0;
while(true) {
if(v[x] == M) {
cout << cnt << "\n";
return 0;
}
x = v[x];
cnt++;
if(cnt > N) break;
}
cout << -1 << "\n";
}
백준 BOJ 22993번 : 서든어택 3
문제 난이도 : Silver IV
알고리즘 분류 : 정렬, 그리디
수열 A에 대해 a_1보다 더 작은 수가 있으면 a_1에 이를 합치고 합쳐진 원소는 지운다고 할 때 모든 원소를 합칠 수 있는지의 여부를 구하는 문제이다.
a_1을 제외한 나머지 원소들을 오름차순으로 정렬한 다음 작은 것부터 합쳐보면서 모두 합칠 수 있는지 확인해보면 된다.
a_1을 제외한 가장 작은 원소가 a_1과 같아도 더 이상 합치는 것이 불가능하므로 No를 출력해주어야 한다.
#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];
sort(v.begin()+1, v.end());
bool check = true;
for(int i=1; i<N; i++) {
if(v[0] <= v[i]) {
check = false;
break;
}
v[0] += v[i];
}
if(check) cout << "Yes\n";
else cout << "No\n";
}
오늘은 일단 여기까지만..
'알고리즘 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 220717 백준 BOJ 풀이 : 2차원 배열 탐색, 정렬 문제 등 풀이 (0) | 2022.07.17 |
|---|---|
| 220716 PS 일기 : 조합론(DP), 카탈란 수 문제들 위주 풀이 (0) | 2022.07.16 |
| 220714 PS 일기 : DP 알고리즘, 포함-배제 원리, 분리 집합(union find) 등 (0) | 2022.07.14 |
| 220713 PS 일기 : 각종 DP 문제들 풀이 (O(N^2) 실버~골드 난이도) (0) | 2022.07.13 |
| 220712 PS 일기 : 교차 개수 세기, 문자열 조합 DP, 누적 합 활용 등 (0) | 2022.07.12 |