1. 최적의 h-index 산출 (이분 탐색)

h-index는 연구자가 발표한 논문 중 인용 횟수가 h회 이상인 논문이 h편 이상일 때, h의 최댓값을 의미합니다. 추가적으로 L회의 인용 횟수를 논문들에 배분하여(논문당 최대 1회) h-index를 높일 수 있는 경우, 이분 탐색을 통해 최적의 값을 찾을 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool is_feasible(int target_h, int extra_l, const vector<int>& citations) {
    long long needed = 0;
    int count = 0;
    
    for (int c : citations) {
        if (c >= target_h) {
            count++;
        } else if (c + 1 == target_h) {
            if (extra_l > 0) {
                count++;
                needed++;
            }
        }
    }
    return count >= target_h && needed <= (long long)extra_l;
}

int main() {
    int n, l;
    cin >> n >> l;
    vector<int> reports(n);
    for (int i = 0; i < n; i++) cin >> reports[i];

    int low = 0, high = n;
    int answer = 0;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (is_feasible(mid, l, reports)) {
            answer = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << answer << endl;
    return 0;
}

2. 상대적 순위 유지 여부 판별

여러 번의 경기 결과가 주어질 때, 항상 특정 객체 A가 B보다 앞서 있는 쌍의 개수를 구하는 문제입니다. 인접 행렬 형태의 배열을 사용하여 각 쌍의 선후 관계를 누적 기록함으로써 해결할 수 있습니다.

#include <iostream>
#include <vector>

using namespace std;

int relation_matrix[25][25];

int main() {
    int k_sessions, n_cows;
    cin >> k_sessions >> n_cows;

    for (int s = 0; s < k_sessions; s++) {
        vector<int> ranking(n_cows);
        for (int i = 0; i < n_cows; i++) cin >> ranking[i];

        for (int i = 0; i < n_cows; i++) {
            for (int j = i + 1; j < n_cows; j++) {
                // ranking[i]가 ranking[j]보다 앞에 있음을 기록
                relation_matrix[ranking[i]][ranking[j]]++;
            }
        }
    }

    int consistent_pairs = 0;
    for (int i = 1; i <= n_cows; i++) {
        for (int j = 1; j <= n_cows; j++) {
            if (relation_matrix[i][j] == k_sessions) {
                consistent_pairs++;
            }
        }
    }
    cout << consistent_pairs << endl;
    return 0;
}

3. 백트래킹을 활용한 8-Queens (대각선 인덱싱)

N-Queen 문제에서 핵심은 퀸이 서로 공격할 수 없도록 행, 열, 그리고 두 종류의 대각선을 체크하는 것입니다. 대각선은 row + col 및 row - col + n의 수식을 통해 고유한 인덱스로 관리할 수 있습니다.

#include <iostream>
#include <vector>

using namespace std;

int board_size;
bool col_used[20], diag1[40], diag2[40];
char board[20][20];

void solve_queens(int row) {
    if (row == board_size) {
        for (int i = 0; i < board_size; i++) {
            for (int j = 0; j < board_size; j++) cout << board[i][j];
            cout << endl;
        }
        cout << endl;
        return;
    }

    for (int col = 0; col < board_size; col++) {
        if (!col_used[col] && !diag1[row + col] && !diag2[row - col + board_size]) {
            col_used[col] = diag1[row + col] = diag2[row - col + board_size] = true;
            board[row][col] = 'Q';
            solve_queens(row + 1);
            board[row][col] = '.';
            col_used[col] = diag1[row + col] = diag2[row - col + board_size] = false;
        }
    }
}

int main() {
    cin >> board_size;
    for (int i = 0; i < board_size; i++)
        for (int j = 0; j < board_size; j++) board[i][j] = '.';
    
    solve_queens(0);
    return 0;
}

4. 최적의 정사각형 절단 (이분 탐색)

여러 개의 직사각형 초콜릿을 동일한 크기의 정사각형 조끼들로 나눌 때, 얻을 수 있는 정사각형의 최대 변의 길이를 구합니다. 변의 길이 S에 대해 만들 수 있는 개수는 (가로/S) * (세로/S)의 합입니다.

#include <iostream>
#include <vector>

using namespace std;

struct Box { int h, w; };

bool can_cut(int side, int k, const vector<Box>& boxes) {
    long long total = 0;
    for (const auto& b : boxes) {
        total += (long long)(b.h / side) * (b.w / side);
    }
    return total >= k;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<Box> boxes(n);
    for (int i = 0; i < n; i++) cin >> boxes[i].h >> boxes[i].w;

    int low = 1, high = 100000;
    int best_side = 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (can_cut(mid, k, boxes)) {
            best_side = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    cout << best_side << endl;
    return 0;
}

5. 구간 합 나머지 연산 (Prefix Sum & Modular)

구간 [L, R]의 합이 K로 나누어떨어지는 조건은 (S[R] - S[L-1]) % K == 0이며, 이는 S[R] % K == S[L-1] % K와 같습니다. 따라서 나머지가 같은 접두사 합들의 개수를 카운트하여 조합(Combination)을 계산합니다.

나머지가 0인 경우는 그 자체로 조건을 만족하는 구간이 되므로 초기값 설정 혹은 결과 합산 시 주의가 필요합니다.

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<long long> remainder_count(k, 0);
    remainder_count[0] = 1; // 나머지가 0인 경우 초기 처리

    long long current_sum = 0;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        current_sum += val;
        remainder_count[current_sum % k]++;
    }

    long long total_intervals = 0;
    for (int i = 0; i < k; i++) {
        // nC2 계산: 동일한 나머지를 가진 지점 중 2개를 선택
        total_intervals += (remainder_count[i] * (remainder_count[i] - 1)) / 2;
    }

    cout << total_intervals << endl;
    return 0;
}