[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';
}