최소값 탐색 문제

주어진 함수 f(x) = floor(n/x) + x - 1의 최소값을 찾는 문제입니다. 수학적 분석을 통해 √n 근처에서 최소값이 발생함을 알 수 있으며, 이분 탐색을 활용해 정확한 위치를 찾습니다.

#include<iostream>
#include<cmath>
using namespace std;

int calculate(int x, int n) {
    return n/x + x - 1;
}

int findMin(int n, int left, int right) {
    int pivot = sqrt(n);
    if(pivot >= left && pivot <= right) {
        while(left < pivot) {
            int mid = (left + pivot)/2;
            if(calculate(mid, n) == calculate(pivot, n)) {
                pivot = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
    return (pivot < left) ? left : right;
}

음악 점수 계산 시스템

각 음표의 위치에 따라 점수를 계산하는 시스템 구현입니다. 맵을 사용해 점수 변화 지점을 관리하고 최대 점수를 추적합니다.

#include<map>
#include<vector>
using namespace std;

int calculateScore(vector<int>& notes, vector<int>& thresholds, vector<int>& scores) {
    map<int, int> changes;
    int base = notes.size() * scores[0];
    
    for(int note : notes) {
        for(int i=0; i<3; i++) {
            changes[thresholds[i]-note] += scores[i+1]-scores[i];
        }
        changes[thresholds[3]-note+1] += scores[4]-scores[3];
    }
    
    int maxScore = base;
    for(auto& change : changes) {
        base += change.second;
        maxScore = max(maxScore, base);
    }
    return maxScore;
}

구간 합 계산 문제

두 구간의 교집합을 활용해 가능한 조합의 수를 계산합니다. 다양한 구간 조건을 처리하는 로직이 포함되어 있습니다.

int countPairs(int total, pair<int,int> range1, pair<int,int> range2) {
    int start = total - range1.second;
    int end = total - range1.first;
    
    if(range2.first > end) return 0;
    if(range2.second < start) return 0;
    
    int overlapStart = max(start, range2.first);
    int overlapEnd = min(end, range2.second);
    return overlapEnd - overlapStart + 1;
}

트리 가중치 계산

트리의 각 노드에 가중치를 할당하고, 깊이에 따라 정렬하여 최적의 합을 계산하는 방법입니다.

#include<algorithm>
#include<vector>
using namespace std;

int calculateTreeValue(vector<int>& depths, vector<int>& weights) {
    sort(depths.begin(), depths.end());
    sort(weights.begin(), weights.end());
    
    int result = 0;
    for(int i=0; i<depths.size(); i++) {
        result += depths[i] * weights[i];
    }
    return result;
}

격자 경로 탐색

DFS를 이용해 2D 격자에서 목적지까지의 가능한 경로를 탐색하는 알고리즘입니다.

bool explorePath(vector<vector<int>>& grid, int x, int y) {
    if(x == grid.size()-1 && y == 2) return true;
    if(grid[x][y] == 2) return true;
    if(grid[x][y] == 1) return false;
    
    grid[x][y] = 2;
    bool down = (x+1 < grid.size()) ? explorePath(grid, x+1, y) : false;
    bool right = (y+1 < 3) ? explorePath(grid, x, y+1) : false;
    
    if(!down && !right) {
        grid[x][y] = 1;
        return false;
    }
    return true;
}