정화 코딩
[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 5회차 과제 에디토리얼 본문
5회차 - 브루트포스, 이분탐색
</19532> 수학은 비대면강의입니다
https://www.acmicpc.net/problem/19532
모든 x와 y에 대해서 조건을 체크해주면 됩니다.
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a, b, c, d, e, f;
cin >> a >> b >> c >> d >> e >> f;
// -999부터 999까지 가능한 x, y 값을 전부 탐색
for (int x = -999; x < 1000; x++) {
for (int y = -999; y < 1000; y++) {
// 두 식을 모두 만족하는 (x, y) 값을 찾으면 출력 후 종료
if ((a * x + b * y == c) && (d * x + e * y == f)) {
cout << x << ' ' << y << '\n';
break;
}
}
}
}
</18111> 마인크래프트
https://www.acmicpc.net/problem/18111
높이를 계속 바꿔서 고정해놓고 계산하는 방식으로 구현했습니다. 즉, 전체 땅을 특정 높이로 만들기 위해 드는 비용을 계산하는데, 이 행동을 가능한 모든 높이에 대해서 계산하는 것입니다.
저는 처음에 땅 높이를 입력받을 때 최대 높이와 최소 높이를 미리 구해두고, 그 범위 내에서만 완전 탐색을 하도록 했습니다. (시간은 별 차이 없습니다.)
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, b;
cin >> n >> m >> b;
vector<vector<int>> data(n, vector<int>(m));
int minHeight = 256, maxHeight = 0;
// 기존의 땅의 높이 입력받기
// 입력을 받으면서 최대, 최소 높이 탐색
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> data[i][j];
minHeight = min(minHeight, data[i][j]);
maxHeight = max(maxHeight, data[i][j]);
}
}
// mint: 최적 시간, minh: 최적 높이
// tmp: 작업 시간, lack: 부족한 블록 수, over: 제거할 블록 수
int mint = 1e9, minh, tmp, lack, over;
// minHeight ~ maxHeight 범위 내 모든 높이 탐색
for (int h = minHeight; h <= maxHeight; h++) {
lack = over = 0;
// 지도 전체를 순회하며 블록 높이를 h로 맞추는 데 필요한 블록 계산
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (data[i][j] > h) // 현재 블록 높이가 목표 높이보다 높다면
over += data[i][j] - h; // 제거해야 할 블록 개수 증가
else // 현재 블록 높이가 목표 높이보다 낮다면
lack += h - data[i][j]; // 추가로 필요한 블록 개수 증가
}
}
// 부족한 블록이 {제거된 블록 + 인벤토리 블록}보다 많으면 불가능
if (lack <= over + b) {
tmp = over * 2 + lack;
// 최소 시간 갱신 (시간이 같다면 더 높은 높이를 선택)
if (tmp <= mint) {
mint = tmp;
minh = h;
}
}
}
// 최적의 시간과 땅 높이 출력
cout << mint << ' ' << minh << '\n';
}
</1051> 숫자 정사각형
https://www.acmicpc.net/problem/1051
입력으로 들어오는 n과 m의 크기가 50 이하로 매우 작기 때문에 브루트포스로 충분히 해결 가능합니다.
모든 점을 탐색하며 해당 점이 정사각형의 왼쪽 상단 점일 때 가능한 정사각형 크기를 탐색하여 3중 반복문을 사용하였습니다.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
int ans = 1; // 정사각형 변의 길이의 최대
// 모든 좌표 (si, sj)를 정사각형의 왼쪽 상단 점으로 설정
for (int si = 0; si < n; si++) {
for (int sj = 0; sj < m; sj++) {
// 가능한 정사각형 크기 탐색
for (int size = 1; si + size < n && sj + size < m; size++) {
if (a[si][sj] == a[si][sj + size] &&
a[si][sj] == a[si + size][sj] &&
a[si][sj] == a[si + size][sj + size]) {
ans = max(ans, size + 1);
}
}
}
}
// 제곱한 후 출력
cout << ans * ans << '\n';
}
</1920> 수 찾기
https://www.acmicpc.net/problem/1920
전형적인 이분 탐색 문제입니다. 물론 C++ STL에 이진 탐색이 있지만 직접 구현해보시는 연습을 해보는 걸 추천드립니다.
함수로 구현
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<int> a;
int bs(int target, int start, int end) {
if (start > end) return -1;
int mid = (start + end) / 2;
if (a[mid] == target) return mid;
else if (a[mid] > target) end = mid - 1;
else start = mid + 1;
return bs(target, start, end);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
a = vector<int>(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
cin >> m;
while (m--) {
int x;
cin >> x;
if (bs(x, 0, n - 1) == -1) cout << 0 << '\n';
else cout << 1 << '\n';
}
}
반복문 구현
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
vector<int> a;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
a = vector<int>(n);
for (int i = 0; i < n; i++) cin >> a[i];
sort(a.begin(), a.end());
cin >> m;
while (m--) {
int x;
cin >> x;
bool find = false;
int start = 0;
int end = n - 1;
while (start <= end) {
int mid = (start + end) / 2;
if (a[mid] == x) {
find = true;
break;
} else if (a[mid] > x) {
end = mid - 1;
} else {
start = mid + 1;
}
}
if (find) cout << 1 << '\n';
else cout << 0 << '\n';
}
}
두 풀이의 시간 차이는 거의 없습니다.
</15810> 풍선 공장
https://www.acmicpc.net/problem/15810
이 문제는 풍선이 다 만들어지는 최소 시간을 구해야 하므로 1. 최솟값 또는 최댓값을 구하는 문제입니다. 그리고 시간이 많을수록 풍선을 더 많이 터뜨릴 수 있기 때문에 2. 단조 증가(또는 단조 감소)하는 성질을 가집니다.
이 두 특징으로부터 이분 탐색을 떠올릴 수 있습니다.
mid분 동안 터트릴 수 있는 풍선의 개수를 계산하고, m개 이상 터뜨릴 수 있으면 더 작은 시간을 탐색하고, 불가능하면 더 긴 시간을 탐색하여 최소 시간을 구하도록 구현했습니다.
아, 자료형에 주의하세요!
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
long long s = 1, e = 1e12 + 1; // 최소, 최대 시간 설정
long long ans = e;
while (s <= e) {
long long mid = (s + e) / 2;
long long tmp = 0;
// mid 시간 동안 터뜨릴 수 있는 풍선 개수 계산
for (int x: a) {
tmp += mid / x;
if (tmp >= m) break; // m개 이상이면 더 계산할 필요 없음
}
if (tmp < m) { // 풍선을 충분히 못 터뜨렸다면 시간 증가
s = mid + 1;
} else { // 충분히 터뜨릴 수 있다면 정답 후보로 저장하고 더 작은 값 탐색
ans = mid;
e = mid - 1;
}
}
cout << ans << '\n';
return 0;
}
</1654> 랜선 자르기
https://www.acmicpc.net/problem/1654
이 문제도 이분 탐색의 전형적인 문제입니다. 앞서 언급한 두 조건을 만족하기 때문입니다.
1. 최솟값 또는 최댓값을 구하는 문제
2. 단조 증가(또는 단조 감소)하는 성질
이 문제 또한 자료형에 주의하셔야겠네요.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int k, n;
cin >> k >> n;
vector<long long> data(k);
for (int i = 0; i < k; i++) {
cin >> data[i];
}
long long l = 0; // 최소 길이
long long r = data[0] + 1; // 최대 길이
while (l < r) {
long long m = (l + r) / 2;
int cnt = 0; // 잘라서 얻을 수 있는 랜선 개수
for (int i = 0; i < k; i++) {
cnt += data[i] / m;
}
if (cnt >= n) // 필요한 개수 이상이면 더 긴 길이도 가능할 수도 있음
l = m + 1;
else // 필요한 개수보다 적으면 더 짧게 잘라야 함
r = m;
}
cout << l - 1 << '\n';
return 0;
}
</28449> 누가 이길까
https://www.acmicpc.net/problem/28449
최대/최소를 구할 때 직접 구현하는 이분 탐색 함수는 주로 lower bound, 즉 첫 번째로 조건을 만족하는 위치를 찾는 방식입니다. 하지만 이 문제에서는 upper bound 방식도 필요합니다.
저는 C++ STL 내장 함수 lower_bound와 upper_bound를 이용하여 구현했습니다. <algorithm> 헤더를 포함시켜 주면 됩니다.
- lower bound
auto lower = lower_bound(v.begin(), v.end(), x);
- 정렬된 배열에서 x 이상의 첫 번째 원소 위치를 반환
- 즉, x 이상인 값이 처음 등장하는 인덱스를 얻을 수 있음
- upper bound
auto upper = upper_bound(v.begin(), v.end(), x);
- 정렬된 배열에서 x 초과인 첫 번째 원소 위치를 반환
- 즉, x보다 큰 값이 처음 등장하는 인덱스를 얻을 수 있음
upper_bound - lower_bound를 하면 x의 개수를 구할 수 있습니다. 이러한 방식은 특정 원소의 개수를 구할 때 자주 사용되므로 기억해두시면 좋습니다.
이 문제도 자료형 조심!! 승부의 개수인 N * M은 최대 10^10입니다.
그리고 또 하나 주의할 점은 이분 탐색을 위해서는 탐색의 대상이 되는 배열이 정렬된 상태여야 합니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m;
cin >> n >> m;
vector<int> a(n);
vector<int> b(m);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
// 이분 탐색을 위해 배열 b 정렬
sort(b.begin(), b.end());
long long hi = 0, arc = 0, draw = 0;
for (int i = 0; i < n; i++) {
auto lower = lower_bound(b.begin(), b.end(), a[i]);
auto upper = upper_bound(b.begin(), b.end(), a[i]);
hi += lower - b.begin();
arc += b.end() - upper;
draw += upper - lower;
}
cout << hi << ' ' << arc << ' ' << draw << '\n';
}
'PS' 카테고리의 다른 글
[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 7회차 과제 에디토리얼 (0) | 2025.03.07 |
---|---|
[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 6회차 과제 에디토리얼 (0) | 2025.03.07 |
[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 4회차 과제 에디토리얼 (0) | 2025.03.05 |
[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 3회차 과제 에디토리얼 (0) | 2025.03.05 |
[ICPC Sinchon] 25W 알고리즘 캠프 초급 강의 2회차 과제 에디토리얼 (0) | 2025.03.05 |