부제: 기본적인 수학 논리와 자료구조를 통한 효율적 설계

다음 내용은 특정 알고리즘 대회에서 자주 등장하는 4 가지 핵심 유형에 대한 접근법과 개선된 구현 예시를 다룹니다. 각 문제는 수학적 성질 검증, 그리디(Greedy) 할당, 해싱 기반 카운팅, 그리고 동적 계획법(DP) 과 재귀 탐색을 포함하고 있습니다.

1. 짝수 합분해 가능성 판정

목표: 주어진 양의 정수가 두 개의 양의 짝수 정수의 합으로 표현될 수 있는지 확인해야 합니다.

논리적 접근:
임의의 양의 짝수 $a$ 와 $b$ 를 가정할 때, 그 합 $S = a + b$ 역시 반드시 짝수가 됩니다. 또한, 가장 작은 양의 짝수는 2 이므로 가능한 최소 합은 $2+2=4$ 가 되어야 합니다.
따라서 다음 두 조건을 동시에 충족해야만 가능함을 알 수 있습니다:

• 수 $S$ 는 짝수여야 합니다.
• 수 $S$ 는 최소 4 이상이어야 합니다.

이를 바탕으로 입력 값을 검증하는 로직을 작성합니다.

#include <iostream>
#include <string>

using namespace std;

// 주어진 수가 두 양의 짝수의 합인지 반환
bool isSumOfTwoPosEvens(int targetNum) {
    // 홀수는 불가능하며, 2 는 두 양의 짝수(최소 2+2=4) 의 합으로 만들 수 없음
    return (targetNum % 2 == 0 && targetNum >= 4);
}

void solve() {
    int inputValue;
    if (!(cin >> inputValue)) return;
    
    if (isSumOfTwoPosEvens(inputValue)) {
        cout << "Possible\n";
    } else {
        cout << "Impossible\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}

2. 구간 제약 하의 배열 합 구성

목표: $N$ 개 요소의 배열을 생성하되, 각 요소는 주어진 최소/최대 범위 내에서 선택되어야 하며 전체 합이 특정 목표값과 일치해야 합니다.

해결 전략:
우선 모든 위치를 최소값으로 채웠을 때의 총합 ($MinSum$) 과 최대값으로 채웠을 때의 총합 ($MaxSum$) 을 계산합니다. 목표 합이 이 구간에 포함되지 않으면 해가 존재하지 않습니다.
존재한다면, 기본적으로 최소값 배열을 시작점으로 삼고, 부족하거나 남는 합치를 앞에서부터 순차적으로 보충해 나가면 됩니다. 이는 그리디한 접근 방식으로 항상 성공 가능한 조합을 찾을 수 있습니다.

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

struct TimeSlot {
    int minDuration, maxDuration;
};

int main() {
    int days, requiredSum;
    cin >> days >> requiredSum;

    vector<TimeSlot> slots(days);
    int minTotal = 0, maxTotal = 0;

    for (int i = 0; i < days; ++i) {
        cin >> slots[i].minDuration >> slots[i].maxDuration;
        minTotal += slots[i].minDuration;
        maxTotal += slots[i].maxDuration;
    }

    if (requiredSum < minTotal || requiredSum > maxTotal) {
        cout << "No Solution\n";
        return 0;
    }

    vector<int> result(days);
    int currentRemainder = requiredSum - minTotal;

    cout << "Valid Assignment:\n";
    for (int i = 0; i < days; ++i) {
        result[i] = slots[i].minDuration;
        int addable = slots[i].maxDuration - slots[i].minDuration;
        
        // 추가로 배분 가능한 만큼 넣거나 나머지가 떨어질 때까지 분배
        int give = min(currentRemainder, addable);
        result[i] += give;
        currentRemainder -= give;
        
        cout << result[i] << " ";
    }
    cout << "\n";

    return 0;
}

3. 문자열 등록 및 중복 방지 메커니즘

목표: 여러 번의 입력 문자열이 들어올 때, 처음 본다면 성공을 출력하고, 이미 등록된 문자열이라면 숫자 접미사를 붙여 구분하여 새로운 식별자로 등록합니다.

자료구조 활용:
문자열의 등장 빈도를 기록하기 위해 해시 맵 (Hash Map) 이나 트리 기반 맵 (Tree Map) 을 사용하는 것이 효율적입니다. 각 문자열이 몇 번째로 호출되었는지 인덱스를 관리하여 중복 시 자동으로 증가된 ID 를 생성합니다.

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

void processQueries(int queryCount) {
    // 문자열과 등장 횟수를 매핑
    unordered_map<string, int> occurrenceTracker;
    
    while (queryCount--) {
        string incomingText;
        cin >> incomingText;

        auto& countRef = occurrenceTracker[incomingText];
        if (countRef == 0) {
            // 첫 출현
            cout << "Accepted\n";
            countRef++;
        } else {
            // 중복 발생: 기존 문자열 + 현재 번호 출력
            cout << incomingText << countRef << "\n";
            countRef++;
        }
    }
}

int main() {
    // 입출력 속도 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    processQueries(n);

    return 0;
}

4. 2 차원 제한 조건 하의 최장 경로 탐색

목표: 주어진 항목들 중에서 제거 후에도 유지되는, 두 가지 속성이 모두 엄격하게 증가하는 최장 부분 수열의 길이를 찾고 실제 경로를 복원해야 합니다. 여기서 특정 기준치 이하의 값들은 유효하지 않은 것으로 간주됩니다.

구현 논리:
이는 긴 공통 부분 수열 (LCS) 의 변형인, 2 차원 증가 수열 문제로 볼 수 있습니다. $O(N^2)$ 에 해결 가능한 메모이제이션 된 깊이 우선 탐색 (Memoized DFS) 을 사용하도록 설계했습니다.
각 노드에서 다른 노드로 이동할 수 있는지는 해당 노드의 두 차원 값이 현재 노드보다 모두 커야 하며, 사전 필터링된 무효 노드는 제외합니다.

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

using namespace std;

const int MAX_N = 5005;

struct Element {
    int idx;
    int width, height;
    bool isValid;
};

Element data[MAX_N];
int memo[MAX_N];
int nextNodeIdx[MAX_N];
int totalItems, limitW, limitH;

// 현재 노드 x 에서 시작할 때의 최대 길이를 반환
int findLongestChain(int currentIdx) {
    int& res = memo[currentIdx];
    if (res != -1) return res;

    res = 1; // 자기 자신 포함한 기본 길이
    
    for (int i = 1; i <= totalItems; ++i) {
        if (!data[i].isValid) continue;

        // 두 차원 모두嚴格增加 해야 연결 가능
        if (data[i].width > data[currentIdx].width && 
            data[i].height > data[currentIdx].height) {
            
            int potentialLen = findLongestChain(i) + 1;
            if (potentialLen > res) {
                res = potentialLen;
                nextNodeIdx[currentIdx] = i;
            }
        }
    }
    return res;
}

int main() {
    cin >> totalItems >> limitW >> limitH;

    // 0 번 인덱스를 더미 루트로 설정 (값 0, 0)
    data[0] = {0, 0, 0, true};

    for (int i = 1; i <= totalItems; ++i) {
        int w, h;
        cin >> w >> h;
        data[i] = {i, w, h, true};
        
        // 제약 조건에 맞지 않으면 비활성화
        if (w <= limitW || h <= limitH) {
            data[i].isValid = false;
        }
    }

    // 메모이제이션 테이블 초기화
    fill(memo, memo + MAX_N, -1);
    fill(nextNodeIdx, nextNodeIdx + MAX_N, 0);

    int maxLength = findLongestChain(0) - 1; // 더미 노드 제외
    cout << maxLength << "\n";

    // 경로 복원
    int cursor = nextNodeIdx[0];
    while (cursor != 0) {
        cout << cursor << " ";
        cursor = nextNodeIdx[cursor];
    }
    cout << "\n";

    return 0;
}