부분합 차이 최소화 문제

주어진 배열에서 연속된 부분 수열의 합 차이를 최소화하고, 해당 조건을 만족하는 최대 길이를 찾는 문제입니다. O(n2) 복잡도의 단순 접근법은 모든 부분 수열을 계산하여 해결합니다. 최적화된 접근법은 다음과 같습니다:

1. 배열의 누적 합을 계산
2. 누적 합을 값 기준으로 정렬 (값이 동일할 경우 인덱스 내림차순)
3. 인접한 누적 합 간의 차이와 인덱스 거리 계산
4. 최소 차이와 해당 조건의 최대 길이 추적

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long ll;

const int MAX = 100005;
const ll INF = LLONG_MAX;

struct Cumulative {
    ll value;
    int index;
};

bool compare(Cumulative a, Cumulative b) {
    return (a.value == b.value) ? a.index > b.index : a.value < b.value;
}

int main() {
    int n;
    ll arr[MAX];
    Cumulative prefix[MAX];
    
    cin >> n;
    prefix[0] = {0, 0};
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        prefix[i] = {prefix[i-1].value + arr[i], i};
    }

    sort(prefix, prefix + n + 1, compare);
    
    ll minDiff = INF;
    ll maxLength = 0;
    ll prevDiff = INF;
    ll prevLen = 0;

    for (int i = 0; i < n; i++) {
        ll diff = abs(prefix[i+1].value - prefix[i].value);
        int idxDist = abs(prefix[i+1].index - prefix[i].index);

        if (diff < minDiff) {
            minDiff = diff;
            maxLength = idxDist;
        } 
        else if (diff == minDiff) {
            if (diff == prevDiff && diff == 0) 
                idxDist += prevLen;
            maxLength = max(maxLength, (ll)idxDist);
        }
        prevDiff = diff;
        prevLen = idxDist;
    }
    cout << minDiff << '\n' << maxLength;
    return 0;
}

이진 트리 생성 알고리즘

n개의 노드로 구성 가능한 모든 이진 트리 중 k번째 트리를 생성하는 문제입니다. 카탈랑 수를 이용해 트리 구조의 수를 계산합니다.

1. 카탈랑 수 DP 배열 생성: dp[i] = Σ(dp[j] * dp[i-j-1])
2. 누적 합으로 트리 크기 결정
3. 재귀적으로 좌/우 서브트리 구성

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAX_NODES = 20;

struct Node {
    int left = 0;
    int right = 0;
};

ll catalan[MAX_NODES];
ll prefixSum[MAX_NODES];
Node tree[MAX_NODES];
int nodeCounter = 0;
int globalRoot = 0;

void generateTree(int& root, int size, ll order) {
    if (size == 0) return;
    root = ++nodeCounter;
    if (size == 1) return;

    for (int i = 0; i < size; i++) {
        ll subtreeCount = catalan[i] * catalan[size - i - 1];
        if (order > subtreeCount) {
            order -= subtreeCount;
        } else {
            ll leftOrder = (order - 1) / catalan[size - i - 1] + 1;
            generateTree(tree[root].left, i, leftOrder);
            generateTree(tree[root].right, size - i - 1, order - catalan[size - i - 1] * (leftOrder - 1));
            break;
        }
    }
}

void printTree(int node, bool isRoot) {
    if (!isRoot) cout << "(";
    if (tree[node].left) printTree(tree[node].left, false);
    cout << "X";
    if (tree[node].right) printTree(tree[node].right, false);
    if (!isRoot) cout << ")";
}

int main() {
    catalan[0] = 1;
    for (int i = 1; i < MAX_NODES; i++) {
        for (int j = 0; j < i; j++) {
            catalan[i] += catalan[j] * catalan[i - j - 1];
        }
    }
    for (int i = 1; i < MAX_NODES; i++) {
        prefixSum[i] = prefixSum[i - 1] + catalan[i];
    }

    ll n;
    cin >> n;
    int treeSize = lower_bound(prefixSum, prefixSum + MAX_NODES, n) - prefixSum;
    n -= prefixSum[treeSize - 1];
    
    generateTree(globalRoot, treeSize, n);
    printTree(globalRoot, true);
    return 0;
}

고급 수학 문제

복잡한 수학적 추론이 필요한 문제로, 검증되지 않은 가설을 기반으로 접근했습니다. 10점의 부분 점수를 획득했으며, 동일 문제가 온라인 저지 사이트에 존재합니다.

전역 단일 수정 문제

전체 데이터 구조에서 O(log n) 시간 복잡도로 단일 점 수정을 구현하는 문제입니다. 단순한 접근법으로는 해결이 어려우며, 효율적인 자료 구조 설계가 필요합니다.