C++ 코딩테스트 강좌, 효율적으로 해킹하기

문제 설명

주어진 정수 배열이 있을 때, 이를 두 개의 부분집합으로 나누어 각각의 합이 동일하게 만들 수 있는지 여부를 확인하는 프로그램을 작성하시오.

이 문제는 ‘부분 집합 합 문제'(Subset Sum Problem)에 해당합니다. 이 문제는 동적 프로그래밍(Dynamic Programming)을 사용하여 해결할 수 있습니다.

입력 형식

첫 번째 줄에 배열의 크기 N (1 ≤ N ≤ 20)이 주어진다.
두 번째 줄에 배열의 N개의 정수 (각각의 정수는 0 이상 10000 이하)가 주어진다.

출력 형식

부분집합을 나눌 수 있으면 “YES”를, 불가능하면 “NO”를 출력한다.

예제 입력

        4
        1 5 11 5

예제 출력

YES

문제 해결 접근법

이 문제를 해결하기 위해서는 먼저 다음 단계를 따라야 합니다:

입력 배열의 합을 계산합니다.
합이 홀수인 경우, 두 부분집합의 합이 같을 수 없으므로 “NO”를 반환합니다.
합이 짝수인 경우, 목표값을 합의 절반으로 설정하고 이를 달성할 수 있는지 판단하기 위해 동적 프로그래밍을 사용할 수 있습니다.
상태 테이블을 설정하고, 각 숫자가 목표값을 만드는 데 사용될 수 있는지 확인합니다.

C++ 코드

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

bool canPartition(vector<int>& arr) {
    int sum = 0;
    for (int num : arr) sum += num;
    if (sum % 2 != 0) return false;

    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;

    for (int num : arr) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }

    return dp[target];
}

int main() {
    int N;
    cin >> N;
    vector<int> arr(N);
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    
    cout << (canPartition(arr) ? "YES" : "NO") << endl;
    return 0;
}

코드 설명

위의 코드는 다음과 같은 방식으로 작동합니다:

먼저 숫자 배열의 총합을 계산합니다.
합이 홀수인지 확인합니다. 홀수라면 “NO”를 반환합니다.
합이 짝수이면, 목표값을 합의 절반으로 설정하고 동적 프로그래밍 배열을 초기화합니다.
각 숫자를 반복하면서 목표값에 이를 만들 수 있는지 확인합니다.
결과적으로 목표값을 만들 수 있으면 “YES”, 그렇지 않으면 “NO”를 출력합니다.

시간 복잡도

이 알고리즘의 시간 복잡도는 O(N * target)입니다. 여기서 N은 입력 숫자의 개수이고, target은 입력 배열의 총합의 절반입니다. 이로 인해 서로 다른 부분집합을 생성하기 위해 사용될 수 있는 연산의 수가 결정됩니다.

마무리

여기까지가 부분 집합 합 문제의 코드와 설명입니다. 이와 같은 알고리즘 문제는 코딩 테스트에서 자주 출제되는 유형이므로, 자주 연습해 보는 것이 좋습니다. 다음 강좌에서는 좀 더 복잡한 문제들과 그 해결 방법에 대해 다루어 보겠습니다.

질문과 피드백

작성한 코드나 이해가 어려운 부분에 대해 궁금한 점이 있으면 언제든지 댓글로 남겨주세요!