알고리즘 훈련 주간 리뷰 (2.17 ~ 2.23)

훈련 종료 및 소감

겨울 방학 동안 진행된 알고리즘 훈련이 이번 주를 끝으로 종료되었습니다. 전반적인 훈련 성과는 아쉬운 수준이었으며, 집중력 저하가 두드러졌습니다. 자택 환경에서는 자연스럽게 느슨해지는 경향이 있었고, 학교 내에서의 학습 효율성에 비하면 현저히 떨어졌습니다. 개학 이후에는 이러한 태도를 개선하고 꾸준한 학습 습관을 유지할 계획입니다.

미해결 문제 복습

1. [Lanqiao 2024 Provincial C] 숫자의 시적 표현 여부 판별

문제 설명: N개의 정수가 주어질 때, 각 수가 연속한 양의 정수들의 합으로 표현될 수 있는지 판단하고, 시적 특성을 갖지 않는 수의 개수를 출력합니다.

핵심 아이디어: 어떤 수 \( a \)가 연속한 정수의 합으로 표현되기 위해서는 다음 조건을 만족해야 합니다:

여기서 \( m+n \)과 \( m-n+1 \)은 반드시 서로 다른 홀짝성을 가져야 하며, 이들의 곱이 짝수가 되어야 합니다. 이를 분석하면, 2의 거듭제곱 형태인 수만이 연속 정수의 합으로 표현되지 못한다는 결론에 도달할 수 있습니다.

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

void solve() {
    int n;
    cin >> n;
    vector<long long> nums(n);
    int powerOfTwoCount = 0;

    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        double logVal = log2(nums[i]);
        if (logVal == floor(logVal)) {
            powerOfTwoCount++;
        }
    }

    cout << powerOfTwoCount << endl;
}

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

2. [Lanqiao 2023 Provincial A] 제곱차 판별

문제 설명: 구간 [L, R] 내의 정수 x 중, \( x = y^2 - z^2 \) 을 만족하는 정수 y, z가 존재하는 경우의 수를 세는 문제입니다.

풀이 전략: 항등식 \( y^2 - z^2 = (y+z)(y-z) \) 에서, 두 인수 \( y+z \)와 \( y-z \)는 항상 같은 홀짝성을 가집니다. 따라서 x는 반드시 홀수이거나 4의 배수여야 합니다. 이를 이용해 L부터 R까지의 수 중 홀수 또는 4의 배수의 개수를 세면 됩니다.

#include <iostream>
using namespace std;

void solve() {
    long long l, r;
    cin >> l >> r;
    long long count = 0;

    for (long long x = l; x <= r; ++x) {
        if (x % 2 == 1 || x % 4 == 0) {
            count++;
        }
    }

    cout << count << endl;
}

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

피드백: 이 문제를 풀 때 우변의 인수 분해 구조에 지나치게 집착하여 핵심 관찰(홀짝성 일치 조건)을 놓쳤습니다.

3. [Lanqiao 2019 National B] 퍼즐 게임 해법 가능성 판단

문제 설명: 세 개의 원형 레이어(내부, 중간, 외부)에 색상 막대가 배치되어 있으며, 모든 레이어를 동시에 회전할 수 있을 때, 내부는 모두 노란색(Y), 중간은 빨간색(R), 외부는 흰색(W)으로 맞출 수 있는지를 판단합니다.

해결 논리: 각 레이어는 4, 8, 12개의 막대로 구성되며, 회전은 전체에 동일하게 적용됩니다. 특정 내부 막대를 기준으로 그와 정렬되는 중간 및 외부 막대들은 고정된 패턴을 형성합니다. 각 위치 그룹(총 4그룹)에서 Y, R, W의 등장 횟수가 각각 1회, 2회, 3회를 초과하지 않아야 목표 상태로 변환할 수 있습니다.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

void solve() {
    string inner, middle, outer;
    cin >> inner >> middle >> outer;

    for (int i = 0; i < 4; ++i) {
        int colorCount[256] = {0};
        
        colorCount[inner[i]]++;
        colorCount[middle[i]]++;
        colorCount[middle[i + 4]]++;
        colorCount[outer[i]]++;
        colorCount[outer[i + 4]]++;
        colorCount[outer[i + 8]]++;

        if (colorCount['Y'] > 1 || colorCount['R'] > 2 || colorCount['W'] > 3) {
            cout << "NO" << endl;
            return;
        }
    }

    cout << "YES" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

데이터 타입 범위 참고 정보

실제 코딩 테스트에서는 가능한 한 long long을 사용하여 오버플로우 문제를 사전에 방지하는 것이 바람직합니다.