이분 탐색과 깊이 우선 탐색 기반 문제 해결

T1. 이분 탐색: 정렬된 배열에서 값 찾기

정렬된 배열 내에서 특정 값을 찾아 그 인덱스를 반환하는 문제입니다. 배열 크기가 최대 106까지 가능하므로, 배열 선언 시 크기를 충분히 확보해야 합니다.

  • 오류 원인: 배열 크기 지정이 부족 (105+7로 설정했으나, 106+7 필요)
  • 핵심 전략: 이분 탐색은 값이 일치할 경우에도 왼쪽 경계를 찾기 위해 r = mid로 업데이트
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 7;
int arr[MAXN];
int n;

int binary_search(int target) {
    int left = 0;
    int right = n + 1;
    arr[0] = -1e9;
    arr[n + 1] = 1e9;

    while (left + 1 < right) {
        int mid = (left + right) / 2;
        if (arr[mid] > target) {
            right = mid;
        } else if (arr[mid] < target) {
            left = mid;
        } else {
            right = mid;
        }
    }

    return (arr[right] == target) ? right : -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    int queries;
    cin >> queries;

    for (int i = 1; i <= n; ++i) {
        cin >> arr[i];
    }

    while (queries--) {
        int x;
        cin >> x;
        cout << binary_search(x) << ' ';
    }

    return 0;
}

T2. 깊이 우선 탐색: 순열 생성

1부터 n까지의 숫자로 이루어진 모든 순열을 출력하는 문제입니다. 방문 여부를 관리하며 재귀적으로 진행합니다.

  • 기법: 백트래킹을 활용한 순열 생성
  • 최적화: setw(5)로 출력 형식 조절
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10;
bool visited[MAXN];
int result[MAXN];
int n;

void print_result() {
    for (int i = 1; i <= n; ++i) {
        cout << setw(5) << result[i];
    }
    cout << '\n';
}

void dfs(int pos) {
    if (pos == n + 1) {
        print_result();
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            result[pos] = i;
            visited[i] = true;
            dfs(pos + 1);
            visited[i] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    dfs(1);

    return 0;
}

T3. 이분 탐색: 쿠키 분할 문제

각 쿠키는 가로세로 길이가 주어지고, 동일한 크기의 정사각형 쿠키로 나누어질 때, 최대 몇 개를 만들 수 있는지 묻는 문제입니다.

  • 핵심 아이디어: 한 변의 길이를 이분 탐색으로 결정
  • 오류 수정: (h[i]/x) + (w[i]/x) → (h[i]/x) * (w[i]/x)
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 7;
int n, k;
int height[MAXN], width[MAXN];

bool can_divide(int size) {
    long long total = 0;
    for (int i = 1; i <= n; ++i) {
        total += (height[i] / size) * (width[i] / size);
        if (total >= k) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    int max_dim = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> height[i] >> width[i];
        max_dim = max(max_dim, max(height[i], width[i]));
    }

    int left = 0;
    int right = max_dim + 1;

    while (left + 1 < right) {
        int mid = (left + right) / 2;
        if (can_divide(mid)) {
            left = mid;
        } else {
            right = mid;
        }
    }

    cout << left << '\n';
    return 0;
}

T4. 이분 탐색: 목재 자르기

목재의 길이를 일정 길이 이상으로 자르고, 최소 몇 개의 조각을 얻을 수 있는지 묻는 문제입니다. 이분 탐색으로 최대 가능한 조각 길이를 찾습니다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 7;
int n, k;
long long wood[MAXN];

bool can_cut(long long length) {
    long long pieces = 0;
    for (int i = 1; i <= n; ++i) {
        pieces += wood[i] / length;
        if (pieces >= k) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> k;
    long long max_len = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> wood[i];
        max_len = max(max_len, wood[i]);
    }

    long long left = 0;
    long long right = max_len + 1;

    while (left + 1 < right) {
        long long mid = (left + right) / 2;
        if (can_cut(mid)) {
            left = mid;
        } else {
            right = mid;
        }
    }

    cout << left << '\n';
    return 0;
}

T5. 가지치기 적용: 부분합 계산

배열에서 연속되지 않은 요소들의 합이 [L, R] 범위에 들어가는 경우의 수를 세는 문제. 전체 순열을 탐색하지 않고, 현재 누적합이 제한을 초과하면 가지치기합니다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50;
int n, l, r;
int nums[MAXN];
int count = 0;

void dfs(int start, long long current_sum) {
    if (current_sum >= l && current_sum <= r) {
        count++;
    }
    if (current_sum > r || start == n) return;

    for (int i = start + 1; i <= n; ++i) {
        dfs(i, current_sum + nums[i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> l >> r;
    for (int i = 1; i <= n; ++i) {
        cin >> nums[i];
    }
    sort(nums + 1, nums + n + 1);

    for (int i = 1; i <= n; ++i) {
        dfs(i, nums[i]);
    }

    cout << count << '\n';
    return 0;
}

T6. K-퀸 문제: 공격 범위 최적화

기존 퀸의 공격 범위를 미리 계산하여, 행, 열, 대각선에 대한 마킹을 사용해 빠른 판단을 수행합니다. 전체 격자 탐색을 피하고, 이미 마킹된 행은 건너뜁니다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 7;
bool row_used[MAXN];
bool col_used[MAXN];
bool diag1[MAXN];  // n + x - y
bool diag2[MAXN];  // x + y

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 0; i < k; ++i) {
        int x, y;
        cin >> x >> y;
        row_used[x] = true;
        col_used[y] = true;
        diag1[n + x - y] = true;
        diag2[x + y] = true;
    }

    int safe_count = 0;
    for (int i = 1; i <= n; ++i) {
        if (row_used[i]) continue;
        for (int j = 1; j <= m; ++j) {
            if (col_used[j] || diag1[n + i - j] || diag2[i + j]) continue;
            safe_count++;
        }
    }

    cout << safe_count << '\n';
    return 0;
}

T7. 이분 탐색: 도로에 루프 표시 설치

도로 위에 루프 표시를 설치하여 가장 큰 간격을 최소화하는 문제. 이분 탐색으로 최대 간격을 찾고, 필요한 루프 수를 계산합니다.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 7;
int positions[MAXN];
int n, m, max_loops;

bool can_place(int gap) {
    int placed = 0;
    for (int i = 1; i <= m; ++i) {
        placed += (positions[i] - positions[i - 1] - 1) / gap;
    }
    placed += (n - positions[m] - 1) / gap;
    return placed <= max_loops;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> max_loops;
    for (int i = 1; i <= m; ++i) {
        cin >> positions[i];
    }

    int left = 0;
    int right = 1e9 + 1;

    while (left + 1 < right) {
        int mid = (left + right) / 2;
        if (can_place(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }

    cout << right << '\n';
    return 0;
}

T8. 이분 탐색: 기기 배터리 소모량 모델링

기기들이 일정 시간 작동할 때, 배터리 용량과 보조 배터리의 충전 용량을 고려해 가능한 최대 작동 시간을 이분 탐색으로 찾는 문제.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 7;
double a[MAXN], b[MAXN];
double p;
int n;

bool can_work(double time) {
    double total_charge_needed = 0.0;
    for (int i = 1; i <= n; ++i) {
        double required = a[i] * time;
        if (b[i] < required) {
            total_charge_needed += required - b[i];
        }
    }
    return total_charge_needed <= p * time;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> p;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
    }

    double left = -1e-5;
    double right = 1e10 + 1e-5;

    while (right - left > 1e-5) {
        double mid = (left + right) / 2;
        if (can_work(mid)) {
            left = mid;
        } else {
            right = mid;
        }
    }

    if (abs(right - 1e10) < 1e-5) {
        cout << -1 << '\n';
    } else {
        cout << left << '\n';
    }

    return 0;
}

태그: 이분탐색 깊이우선탐색 백트래킹 배열처리 조건부탐색

6월 25일 21:05에 게시됨

인기 태그

©2026 괴물 클럽