이분 탐색은 최대/최소 문제를 결정 문제 * logN으로 바꾸는 강력한 방법이다. 최적해가 존재하는 범위를 두고 매번 질문을 던지며 범위를 1/2씩 좁혀 나간다. 어떤 함수의 조건을 만족하는 값을 구하려고 할 때 이분 탐색을 적용하려면 이 함수는 단조 함수의 형태여야 한다.
백준 1654 : 랜선 자르기
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net
K개의 랜선의 길이가 각각 주어질 때, 각 랜선을 잘라 N개 이상의 랜선을 얻으려 할 때, 이 자른 랜선의 길이의 최댓값을 구해야 한다.
일단 이런 함수를 생각해 보자.
f(x) : 각 랜선을 x만큼의 길이로 자를 때 만들 수 있는 랜선의 수
이 함수가 단조 감소하는것은 쉽게 알 수 있다. 길이가 커지면 만들 수 있는 랜선의 수는 적어지며, 길이가 작아지면 만들 수 있는 랜선의 수는 많아지기 때문이다.
이제 f(x) >= N을 만족하는 최대의 N을 이분 탐색으로 구하면 된다. int범위 초과를 주의해야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<ll> vec;
int main() {
ll N, M, time, s = 0, e = INT_MAX, result = -1;
cin >> N >> M;
vec.resize(N);
for (int i = 0; i < N; i++) cin >> vec[i];
while (s <= e) {
ll mid = (s + e) / 2, cnt = 0;
for (int i = 0; i < N; i++) cnt += vec[i] / mid;
if (cnt < M) e = mid - 1;
else s = mid + 1;
}
cout << e << "\n";
}
|
cs |
코드의 내용이다. 시간 복잡도는 O(NlogN), 공간 복잡도는 O(N)이다.
백준 2805 : 나무 자르기
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M을
www.acmicpc.net
랜선 자르기와 아주 유사한 문제다.
N개의 나무의 길이가 각각 주어질 때, 모든 나무를 특정 높이만 남기고 잘라 얻을 수 있는 나무의 총 길이를 M 이상으로 하는 최소의 높이를 구해야 한다.
이번에도 비슷하다.
f(x) : x만큼만 남기고 나무를 자를 때 얻는 나무의 총 길이
이 함수 또한 단조 감소하는 것을 알 수 있다. 나무를 많이 남길수록 내가 잘라가는 나무는 적어지고, 나무를 적게 남길수록 내가 잘라가는 나무는 많아지기 때문이다. 이번에도 역시 int범위 초과를 조심해야 한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
vector<ll> vec;
int main() {
ll N, M, time, s = 0, e = INT_MAX, result = -1;
cin >> N >> M;
vec.resize(N);
for (int i = 0; i < N; i++) cin >> vec[i];
while (s <= e) {
ll mid = (s + e) / 2, cnt = 0;
for (int i = 0; i < N; i++) cnt += vec[i] / mid;
if (cnt < M) e = mid - 1;
else s = mid + 1;
}
cout << e << "\n";
}
|
cs |
코드의 내용이다. 시간 복잡도는 O(NlogN), 공간 복잡도는 O(N)이다.
백준 2343 : 기타 레슨
2343번: 기타 레슨
강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경
www.acmicpc.net
이번에도 꽤 유사하다.
f(x) : 블루레이 크기가 x일 때 최소 블루레이 갯수
이번에는 블루레이 갯수를 구하는 데에 그리디 알고리즘을 사용한다. 가능한 한 많은 레슨을 한 블루레이에 담으면 된다.
|
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
|
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;
vector<ll> vec;
ll func(ll x) {
ll ret = 1, cnt = 0;
for (ll i = 0; i < vec.size(); i++) {
if (cnt + vec[i] > x) {
cnt = vec[i];
ret++;
}
else cnt += vec[i];
}
return ret;
}
int main() {
ll N, M, s = 0, e = 2e9;
cin >> N >> M;
while (N--) {
ll temp;
cin >> temp;
vec.push_back(temp);
s = max(s, temp);
}
while (s <= e) {
ll mid = (s + e) / 2;
if (func(mid) > M) s = mid + 1;
else e = mid - 1;
}
cout << s << "\n";
}
|
cs |
코드의 내용이다. 시간 복잡도는 O(NlogN), 공간 복잡도는 O(N)이다.
백준 1300 : K번째 수
1300번: K번째 수
세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B
www.acmicpc.net
A[i][j] = i * j인 N*N행렬에서 K번째로 작은 수를 구하는 문제이다.
f(x) = 행렬에서 x이하인 수의 갯수
f(x)가 K보다 크거나 같은 최소의 x를 구하는 문제로 바꿀 수 있으며, f(x)는 당연하게도 단조 증가한다.
f(x)를 구현할 때는 i번째 행의 x이하인 수의 갯수는 min(N, x / i)개임을 이용하면 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll N;
ll func(ll key) {
ll ret = 0;
for (ll i = 1; i <= N; i++) ret += min(N, key / i);
return ret;
}
int main() {
ll K, s = 0, e = 1e9;
cin >> N >> K;
while (s <= e) {
ll mid = (s + e) / 2;
if (func(mid) < K) s = mid + 1;
else e = mid - 1;
}
cout << s << "\n";
}
|
cs |
코드의 내용이다. 시간 복잡도는 O(NlogN), 공간 복잡도는 O(1)이다.
백준 2613 : 숫자 구슬
2613번: 숫자구슬
첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다. 둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100
www.acmicpc.net
기타 레슨과 완전 똑같지만 정확히 m개로 나눈 걸 출력해줘야 해서 티어가 많이 올라간 것 같다.
구현이 상당히 까다롭다. 유연하게 m개가 될 때까지 결과를 잘 쪼개주면 된다.
|
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
57
58
59
60
61
|
#include <bits/stdc++.h>
using namespace std;
vector<int> vec, res;
int main() {
int N, M, s = 0, e = 30000;
cin >> N >> M;
vec.resize(N);
for (int i = 0; i < N; i++) {
cin >> vec[i];
s = max(s, vec[i]);
}
while (s <= e) {
int mid = (s + e) / 2, cnt = 1, sum = 0;
for (int i = 0; i < N; i++) {
if (mid < sum + vec[i]) {
sum = vec[i];
cnt++;
}
else sum += vec[i];
}
if (M < cnt) s = mid + 1;
else e = mid - 1;
}
cout << s << "\n";
int sum = 0, cnt = 0;
for (int i = 0; i < N; i++) {
if (s < sum + vec[i]) {
sum = vec[i];
res.push_back(cnt);
cnt = 1;
}
else {
sum += vec[i];
cnt++;
}
}
res.push_back(cnt);
if (res.size() == M) {
for (int n : res) cout << n << " ";
cout << "\n";
}
else {
int cnt = M - res.size();
for (int n : res) {
if (cnt && 1 < n) {
if (cnt < n) {
for (int i = 0; i < cnt; i++) cout << "1 ";
cout << n - cnt << " ";
cnt = 0;
}
else {
cnt -= (n - 1);
for (int i = 0; i < n; i++) cout << "1 ";
}
}
else cout << n << " ";
}
cout << "\n";
}
}
|
cs |
코드의 내용이다. 시간 복잡도는 O(NlogN), 공간 복잡도는 O(N)이다.
백준 2102 : 보석 줍기
2102번: 보석 줍기
수영이는 고대 유적을 탐사하던 도중 보석을 발견했다. 유적 속에는 N(1≤N≤100,000)개의 보석들이 일렬로 놓여 있었다. 각각의 보석의 가치는 다를 수 있기 때문에, 수영이는 가급적 많은 이득을
www.acmicpc.net
N개의 보석의 가치가 주어졌을 때 M개 이상의 연속된 보석을 주우면서 얻을 수 있는 가치의 평균의 최대를 구해야한다.
f(x) = x보다 크거나 같은 가치 평균을 만들 수 있다면 1, 그렇지 않다면 0
f(0)은 1이었다가 x가 커지다 보면 언젠가부터는 f(x)가 0이 되기 때문에 단조 감소한다.
f(x)가 0이 되기 직전을 구하면 그게 최적해가 된다.
f(x)는 어떻게 구현할까? n번째 보석까지의 가치 합을 S[n]이라고 하고, 수열의 합의 성질을 이용하자.
을 만족하는 아무 a와 b (a + M <= b) 쌍만 구한다면, 바로 1을 반환하면 된다.
그러나 a와 b 모든 쌍을 일일히 고려하면 O(N^2)으로 시간 초과다. 식을 조금 정리해 보자.
좌변은 b에 대한 식, 우변은 a에 대한 식이 되었다. 이제 우변은 최솟값을 계속해서 갱신하고, 좌변은 가능한 b를 시도해보며 계속해서 비교하면 O(N)에 작동하는 f(x)를 구현할 수 있다.
|
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
|
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll psum[100001], N, M;
bool judge(ll x) {
ll minS = 0, nowE;
for (ll i = 1; i <= N - M + 1; i++) {
minS = min(minS, psum[i - 1] * 1000 - x * (i - 1));
nowE = psum[i + M - 1] * 1000 - x * (i + M - 1);
if (nowE >= minS) return 1;
}
return 0;
}
int main() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
ll temp;
cin >> temp;
psum[i + 1] = psum[i] + temp;
}
ll s = 0, e = 2000000;
while(s <= e) {
ll mid = (s + e) / 2;
if (judge(mid)) s = mid + 1;
else e = mid - 1;
}
cout << e << "\n";
}
|
cs |
코드의 내용이다. 시간 복잡도는 O(NlogN), 공간 복잡도는 O(N)이다.
'알고리즘 문제풀이 공부' 카테고리의 다른 글
| 코포 일기 : Codeforces Round #722 (Div. 2) (0) | 2021.05.25 |
|---|---|
| 코포 일기 : Codeforces Round #721 (Div. 2) (0) | 2021.05.21 |
| 알고리즘 동아리 활동#1 그리디 알고리즘 연습문제 풀이 (0) | 2020.11.27 |
| constructive algorithms에 대하여 #1 (0) | 2020.07.11 |
| [백준 2618] 경찰차 : 동적 계획법 연습하기 (0) | 2020.05.25 |
