백준 BOJ 12084번 : Captain Hammer (small)
문제 난이도 : Silver IV
알고리즘 분류 : 이분 탐색
물체를 초기 속도 V, 각도 θ로 쏠 때 거리 D만큼 보내기 위해서 몇 도로 쏴야 하는지를 구하는 문제이다.
고등학교 1학년 수준의 물리 지식이 있다면 간단한 이분탐색으로 답을 구해줄 수 있다.
위와 같이 운동 방정식 2개를 가지고 풀어주면 세타에 대한 식이 나온다.
물론 아크사인으로 구할 수도 있겠지만 문제 분류가 이분 탐색으로 되어있으니 이분 탐색으로 풀어보자.
범위는 0도에서 45도 사이로 잡으면 된다. (왜냐하면 x = 90 - x에서 삼각함수의 대칭성에 의해 같은 답이 나온다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
cout << fixed;
cout.precision(6);
int T; cin >> T;
for(int t=1; t<=T; t++) {
double V, D; cin >> V >> D;
double l = 0, r = 45;
for(int i=0; i<100; i++) {
double m = (l + r)/2;
double theta = m * M_PI / 180.0;
if(sin(theta*2) < 9.8*D/(V*V)) l = m;
else r = m;
}
cout << "Case #" << t << ": " << l << "\n";
}
}
이분탐색을 풀 줄 알면 3차 이상의 다항식이나 삼각함수 등 다양한 방정식의 해를 구할 수 있으니 연습해보는 것도 나쁘지 않다. (물론 그래프의 개형을 알아야 하는데, 이것은 수식을 미분하거나 값 몇 개만 넣어보면 되기 때문에 쉽게 알 수 있다.)
백준 BOJ 1947번 : 선물 전달
문제 난이도 : Gold III
알고리즘 분류 : 조합론 (완전순열)
N명의 사람들이 각자 자신의 선물을 가져와 다른 사람한테 나눠주는 방법의 수를 구하는 문제이다. (모두 다른 사람의 선물을 받아야 한다.)
이는 유명한 수열인 완전순열으로, 선형 점화식을 세우는 방법은 다음과 같다.
문제 상황을 단순화 시켜서 1 ~ N 수 아랫줄에 각각 다른 수에 대응되는 수들을 1 ~ N 중 하나씩 쓰는 경우의 수 C_i를 생각해보자.
이 때 1이 k에 대응된다고 하면, 다음의 두 가지 경우가 존재한다.
( i ) k도 1에 대응되는 경우, 나머지 수들을 배치하는 경우의 수는 N-2개의 수를 모두 다르게 배치하는 경우이므로 C_i-2이다.
( ii ) k가 1에 대응되지 않는 경우, 1과 k를 같은 것으로 생각해버리면 총 N-1개의 수를 서로 다른 것끼리 매치하는 상황과 일대일 대응이 되므로 C_i-1이다.
이 모든 경우에서 k는 2 ~ N-1 중 하나로 생각할 수 있으므로, C_i = (C_i-1 + C_i-2) × (i - 1)임을 알 수 있다.
이를 바탕으로 풀이 코드를 적어보면 다음과 같다.
N = 1일 때 답은 0임에 주의하자.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[1000001] = {0, 1, 2};
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
for(int i=3; i<=1000000; i++)
dp[i] = ((dp[i-1] + dp[i-2]) * i) % (int)(1e9);
int N; cin >> N;
cout << dp[N-1] << "\n";
}
백준 BOJ 4099번 : Skyline
문제 난이도 : Gold III
알고리즘 분류 : 조합론 (카탈란 수)
문제를 요약하면, 주어진 N에 대해 1 ~ N을 a_i < a_j < a_k (i < j < k)가 나타나지 않도록 배치하는 경우의 수를 구하는 문제이다.
우선은 N에 따른 값들을 적어보면서 규칙성을 찾아보자.
입력 범위는 아니지만 N = 1일때는 1, N = 2일 때는 2이다.
그 다음 N = 3일 때는 (3, 2, 1)을 제외한 나머지가 가능하니 5이다.
N = 4일 때는 다음과 같이 14가지가 나온다.
1 4 3 2
2 1 4 3
2 4 1 3
2 4 3 1
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1
이 정도만 해봐도 정답이 카탈란 수임을 알 수 있다. (1, 2, 5, 14, ...)
증명으로 풀이하는 방법은 다음과 같다.
1~N 배치하는 경우의 수를 D_N이라고 하면,
1~N-1 배치하고 N을 맨 앞에 배치하는 경우 : D_N-1 * D_1
1~N-2 배치하고 (N-2)~(N-1)를 맨 앞에 배치하는 경우 : D_N-2 * D_2
...
1 배치하고 2~(N-1)를 앞에 배치하는 경우 : D_1 * D_(N-1)
D_N = D_1*D_N-1 + D_2*D_N-2 + ... + D_N-1*D_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 dp[1001] = {1, 1};
for(int i=2; i<=1000; i++)
for(int j=0; j<i; j++) dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % (int)(1e6);
while(true) {
int N; cin >> N;
if(N == 0) break;
cout << dp[N] << "\n";
}
}
백준 BOJ 9356번 : Skill
문제 난이도 : Gold III
알고리즘 분류 : 조합론
감소하는 수가 나오지 않는 N자리 수열의 개수를 구하는 문제이다.
0 ~ 9에서 수 N개를 뽑으면 이를 오름차순으로 만들 수 있는 경우는 1가지뿐이므로, 결국 0 ~ 9에서 중복을 허용하여 N개를 뽑는 경우의 수와 일대일 대응이 된다.
이는 10 H N = (10 + N - 1) C N = (N+9) C N이므로, dp를 이용하여 combination 값을 구해주면 답을 얻을 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[100010][10] = {};
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
for(int i=0; i<=100009; i++) dp[i][0] = 1;
for(int i=1; i<=100009; i++)
for(int j=1; j<=9; j++)
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % (int)(1e9 + 7);
int T; cin >> T;
while(T--) {
int N; cin >> N;
cout << dp[N+9][9] << "\n";
}
}
백준 BOJ 1749번 : 점수따먹기
문제 난이도 : Gold V
알고리즘 분류 : 누적 합
N x M 배열이 주어질 때 그 중 부분 직사각형을 선택하여 선택 영역 내의 원소들의 최대 합을 구하는 문제이다.
정석적인 누적 합 문제로, (0, 0)부터 (i, j)까지 누적 합들을 모두 구하면 4중 for문으로도 부분 직사각형의 합들을 모두 구할 수 있다. (부분 직사각형의 = 가장 큰 직사각형 - 왼쪽 부분 직사각형 - 위쪽 부분 직사각형 + 왼쪽 위 부분 직사각형)
#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<vector<int>> v(N+1, vector<int>(M+1));
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++) cin >> v[i][j];
vector<vector<int>> u(N+1, vector<int>(M+1));
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++)
u[i][j] = u[i-1][j] + u[i][j-1] - u[i-1][j-1] + v[i][j];
int ans = INT_MIN;
for(int i=1; i<=N; i++)
for(int j=1; j<=M; j++)
for(int k=i; k<=N; k++)
for(int l=j; l<=M; l++)
ans = max(ans, u[k][l] - u[i-1][l] - u[k][j-1] + u[i-1][j-1]);
cout << ans << "\n";
}
백준 BOJ 24390번 : 또 전자레인지야?
문제 난이도 : Silver I
알고리즘 분류 : 구현, 그리디
전자레인지를 조작하여 원하는 시간을 만드는 최소 버튼 횟수를 구하는 문제이다.
보통 이런 종류의 문제들은 간단한 그리디 문제인데 왜 난이도가 Silver I인가 했는데, 30초 버튼 때문에 고려해야 할 변수가 많았다.
전자레인지 작동 중에 30초 버튼을 누르면 시간이 30초 연장되는데, 0초일 때 누르면 30초가 되며 0초가 아닐 때 누르면 작동 시작이 된다.
이러한 예외 때문에 30초 버튼을 먼저 누르고 시작하는 경우와 그렇지 않은 경우를 비교해서 더 적은 값을 답으로 얻어주어야 한다.
또한 0초가 입력으로 들어올 수도 있는데 이 경우는 별도의 버튼을 누를 필요가 없으므로 0을 답으로 얻어주어야 한다.
여러모로 반례가 많아 귀찮은 문제이다.
#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 a, b;
scanf("%02d:%02d", &a, &b);
int x = a * 60 + b;
if(x == 0) {
cout << 0 << "\n";
return 0;
}
else if(x < 30) {
cout << x/10 + 1 << "\n";
return 0;
}
else if(x < 60) {
cout << (x - 30)/10 + 1 << "\n";
return 0;
}
int y = x - 30;
int ans1 = 1, ans2 = 1;
ans1 += x / 600;
x %= 600;
ans1 += x / 60;
x %= 60;
ans1 += x / 30;
x %= 30;
ans1 += x / 10;
ans2 += y / 600;
y %= 600;
ans2 += y / 60;
y %= 60;
ans2 += y / 30;
y %= 30;
ans2 += y / 10;
cout << min(ans1, ans2) << "\n";
}
백준 BOJ 19592번 : 장난감 경주
문제 난이도 : Silver V
알고리즘 분류 : 이분 탐색
자동차 경주에서 부스터를 사용하여 최대 Y미터를 처음 1초에 이동할 수 있다고 할 때, 단독 우승을 하기 위한 최소 부스터 값을 구하는 문제이다.
고려해야 할 경우가 부스터를 사용하지 않고도 우승하는 경우, 부스터를 최대로 써도 우승하지 못하는 경우, 그리고 정상적으로 부스터를 써서 1위를 할 수 있는 경우로 3가지이고, 그 중 마지막 케이스에는 이분 탐색을 사용하여 최소 부스터 값을 찾아주어야 한다.
구현이 나름 고려해야 할 점들이 있어서 난이도가 너무 낮은 것이 아닌가 하고 난이도 기여를 하려고 했는데.. 브루트포스로도 풀린다고 한다.
#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;
while(T--) {
double N, x, y; cin >> N >> x >> y;
vector<double> v(N);
for(int i=0; i<N; i++) cin >> v[i];
sort(v.begin(), v.end()-1, greater<double>());
if(v[N-1] > v[0]) {
cout << 0 << "\n";
continue;
}
double a = x / v[0];
if(a <= 1.0 + (x - y)/v[N-1]) {
cout << -1 << "\n";
continue;
}
int l = 1, r = y, ans = INT_MAX;
while(l <= r) {
int m = (l + r) / 2;
double b = 1.0 + (x - m)/v[N-1];
if(b < a) {
ans = min(ans, m);
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
}
백준 BOJ 19637번 : IF문 좀 대신 써줘
문제 난이도 : Silver III
알고리즘 분류 : 이분 탐색
N개의 조건문과 M개의 값이 입력되었을 때 if문에서 걸러지는 조건문을 찾아 그 조건문에 해당하는 문자열을 출력하는 문제이다.
N과 M이 10^5 이하이므로, O(NM)으로는 시간 초과가 발생한다.
따라서 N에 대한 시간 복잡도를 줄이기 위해 이분 탐색을 사용한다. (O(M log N))
이분 탐색 범위에서 l = 0, r = 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, M; cin >> N >> M;
vector<pair<string, int>> v(N);
for(int i=0; i<N; i++) cin >> v[i].first >> v[i].second;
while(M--) {
int x; cin >> x;
int l = 0, r = N-1;
string ans;
while(l <= r) {
int m = (l + r)/2;
if(x <= v[m].second) {
ans = v[m].first;
r = m - 1;
}
else l = m + 1;
}
cout << ans << "\n";
}
}
백준 BOJ 1590번 : 캠프가는 영식
문제 난이도 : Silver IV
알고리즘 분류 : 브루트포스
기다리기 시작하는 시간과 N 종류의 버스의 첫 출발 시간, 배차 간격, 총 버스 대수가 주어진다고 할 때 가장 빠른 다음 버스를 타기까지 기다려야 하는 시간을 구하는 문제이다.
간단한 브루트포스로 답을 찾을 수 있다.
기다리기 시작하는 시간보다 늦게 출발하는 버스 중 그 시간의 최솟값을 답으로 얻어줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
struct s { int a, b, c; };
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<s> v(N);
for(int i=0; i<N; i++) cin >> v[i].a >> v[i].b >> v[i].c;
int ans = INT_MAX;
for(int i=0; i<N; i++) {
for(int j=0; j<v[i].c; j++) {
if(v[i].a + v[i].b * j >= M)
ans = min(ans, (v[i].a + v[i].b * j) - M);
}
}
if(ans != INT_MAX) cout << ans << "\n";
else cout << -1 << "\n";
}
백준 BOJ 9953번 : Paula's search
문제 난이도 : Silver V
알고리즘 분류 : 이분 탐색
주어진 규칙대로 1 ~ 100번의 가게 중에서 특정 번호의 가게를 찾을 때 필요한 시행의 횟수를 구하는 문제이다.
규칙을 잘 보면 홀짝을 나누는 것 외에는 이분 탐색 알고리즘대로 가게를 찾으므로, 규칙대로 구현만 해주면 된다.
찾는 가게의 번호가 짝수라면 그대로 짝수 중에서 이분 탐색을 해주면 되고, 홀수라면 길을 한 번 건너고 나서 이분 탐색을 시작하므로 답에 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);
while(true) {
int N; cin >> N;
if(N == 0) break;
int ans = 1;
vector<int> v(50);
if(N % 2 == 0) {
for(int i=0; i<50; i++) v[i] = (i+1)*2;
}
else {
for(int i=0; i<50; i++) v[i] = i*2 + 1;
ans++;
}
int l = 0, r = 49;
while(l <= r) {
int m = (l + r)/2;
if(v[m] == N) break;
if(v[m] < N) l = m + 1;
else r = m - 1;
ans++;
}
cout << ans << "\n";
}
}
백준 BOJ 18265번 : MooBuzz
문제 난이도 : Silver V
알고리즘 분류 : 이분 탐색
3의 배수와 5의 배수를 제거한 자연수를 수열로 만들 때, N번째 수를 구하는 문제이다.
이 문제는 백준 BOJ 1557번 : '제곱 ㄴㄴ'에 나온 아이디어와 비슷하다.
우리는 몇 번째 수가 어떤 값인지를 알기는 어렵지만 특정 수가 몇 번째 수인지는 알기 쉽다.
예를 들어 N은 N 이하의 3의 배수와 5의 배수의 수를 빼고, 포함과 배제의 원리에 의해 15의 배수의 개수를 더해주면 된다.
따라서 이분 탐색을 통해 답을 찾아주면 된다.
다만 이 문제도 제곱 ㄴㄴ 문제와 동일한 문제점이 있는데, 바로 3의 배수 또는 5의 배수가 답으로 얻어질 수 있다는 것이다.
이런 경우를 대비하여 최종 답에서 3의 배수나 5의 배수가 아닐 때까지 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;
int l = 1, r = INT_MAX, ans;
while(l <= r) {
int m = (l + r)/2;
int x = m - m/3 - m/5 + m/15;
if(x == N) {
while(m % 3 == 0 || m % 5 == 0) m--;
cout << m << "\n";
break;
}
if(x < N) l = m + 1;
else r = m - 1;
}
}
백준 BOJ 25379번 : 피하자
문제 난이도 : Silver V
알고리즘 분류 : 그리디
인접한 두 수를 여러 번 swap하여 짝수는 짝수끼리, 홀수는 홀수끼리 모으는 최소 swap 수를 구하는 문제이다.
최종 결과는 짝수가 왼쪽, 홀수가 오른쪽으로 모이거나 그 반대인 경우밖에 없다.
따라서 두 결과를 모두 해보고 그 중 최소 연산 횟수를 답으로 구해주면 된다.
연산 횟수를 쉽게 계산하는 방법은 예를 들어 짝수가 0, 2, 4번 위치에 있다고 할 때 이들은 최종적으로 0, 1, 2번 위치에 있어야 하므로, 짝수의 개수를 cnt라고 하면 (초기 짝수 위치들의 합) - cnt * (cnt - 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);
int cnt = 0;
for(int i=0; i<N; i++) {
cin >> v[i];
if(v[i] % 2 == 0) cnt++;
}
int a = 0;
for(int i=0; i<N; i++)
if(v[i] % 2 == 0) a += i;
a -= cnt * (cnt - 1) / 2;
int b = 0;
for(int i=0; i<N; i++)
if(v[i] % 2 == 1) b += i;
b -= (N - cnt) * (N - cnt - 1) / 2;
cout << min(a, b) << "\n";
}
백준 BOJ 25377번 : 빵
문제 난이도 : Bronze III
알고리즘 분류 : 구현
N개의 가게가 있고 가는 시간과 빵이 들어오는 시간이 주어질 때, 빵이 주어지는 시간보다 늦게 도착하면 빵이 없다고 가정하면 빵을 구할 수 있는 최단 기간을 구하는 문제이다.
문제에서는 설명이 다소 난잡하게 되어있는데 핵심만 요약하면 가게에 가는 시간이 빵이 들어오는 시간보다 길어지면 그 가게에서는 빵을 구할 수 없다.
따라서 가게에 가는 시간이 빵이 들어오는 시간보다 짧은 가게들 중 가는 시간이 가장 짧은 값을 출력하면 된다.
#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 ans = INT_MAX;
while(N--) {
int a, b; cin >> a >> b;
if(a > b) continue;
ans = min(ans, b);
}
if(ans != INT_MAX) cout << ans << "\n";
else cout << -1 << "\n";
}
백준 BOJ 10422번 : 괄호
문제 난이도 : Gold III
알고리즘 분류 : 조합론 (카탈란 수)
괄호 문자열의 길이가 주어졌을 때, 가능한 올바른 괄호 표기식으로 가능한 것의 개수를 구하는 문제이다.
괄호 예시가 카탈란 수 예시들 중에 가장 대표적인 예시일 것이다.
길이 N 짜리 문자열 f(N) = f(2) * f(N-2) + f(4) * f(N-4) + ... + f(N-2) * f(2)와 같이 나타낼 수 있으므로 이를 dp로 계산해주면 된다.
다만 카탈란 수를 이미 알고 있다면, 길이 N이 홀수인 경우는 그냥 0을 출력해주고 나머지는 2로 나누어 카탈란 수의 N/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 dp[2501] = {1, 1};
for(int i=2; i<=2500; i++)
for(int j=0; j<i; j++) dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % (int)(1e9 + 7);
int T; cin >> T;
while(T--) {
int N; cin >> N;
if(N % 2 == 1) {
cout << 0 << "\n";
continue;
}
cout << dp[N/2] << "\n";
}
}
백준 BOJ 1670번 : 정상 회담 2
문제 난이도 : Gold III
알고리즘 분류 : 조합론 (카탈란 수)
원탁 위의 N개의 점을 이을 때 겹치지 않고 N/2개의 선분을 잇는 경우의 수를 구하는 문제이다.
백준 BOJ 17268번 : '미팅의 저주' 문제와 완전히 동일한 문제이다.
둘 중 늦게 나온 문제는 백준에 등록이 confirm이 안 났어야 하지 않나 싶은데 백준에는 두 문제가 모두 등록되어 있다.
(사실 백준에는 지문까지 아예 동일한 문제들도 있긴 하다.)
아무튼 선분을 겹치지 않고 연결하는 방법도 위의 문제와 동일한 점화식이 나타나므로 똑같은 방식으로 풀어주면 된다.
#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 dp[5001] = {1, 1};
for(int i=2; i<=5000; i++)
for(int j=0; j<i; j++) dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % 987654321;
int N; cin >> N;
cout << dp[N/2] << "\n";
}
'프로그래밍 > 알고리즘 공부 내용 정리' 카테고리의 다른 글
| 백준 BOJ 풀이 : 이분 탐색 문제들 마저 해치우기 (220723) (0) | 2022.07.23 |
|---|---|
| 백준 BOJ 풀이 : 이분 탐색 문제들 위주 풀이 (220722) (0) | 2022.07.22 |
| 220720 백준 BOJ 풀이 : LIS (가장 긴 증가하는 부분 수열) 문제들 (0) | 2022.07.20 |
| 220719 백준 풀이 : BOJ 18977, BOJ 25369, BOJ 25370 등 (0) | 2022.07.19 |
| 220718 백준 BOJ 풀이 : 그래프 탐색 문제들 (너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)) (4) | 2022.07.18 |