C++로 특정 합을 만드는 2의 거듭제곱 찾기

문제 개요

이 문제에서는 하나의 정수 N이 주어집니다. 우리가 해야 할 일은 N을 만들 수 있는 2의 거듭제곱들의 지수(거듭제곱 횟수)를 출력하는 것입니다.

예시를 통해 문제를 더 쉽게 이해해 보겠습니다.

입력 − 17

출력 − 0, 4

설명 − 17 = 2⁴ + 2⁰ = 16 + 1

즉, 17은 2의 4제곱과 2의 0제곱을 더한 값이므로 지수인 0과 4를 출력하면 됩니다.

해결 접근 방법

이 문제는 숫자를 반복적으로 2로 나누는 방식으로 해결할 수 있습니다. 어떤 수든 2로 계속 나누면서 나머지를 기록하면, 그 수를 2의 거듭제곱들의 합으로 표현할 수 있습니다. 사실 이 방법은 우리가 잘 아는 10진수를 2진수로 변환하는 과정과 동일합니다.

예를 들어 23342를 2진수로 변환하면 각 비트 위치에서 값이 1인 자리의 지수가 바로 답이 됩니다. 23342의 경우 지수 1, 2, 3, 5, 8, 9, 11, 12, 14에 해당하는 2의 거듭제곱들을 모두 더하면 23342가 됩니다.

예제 코드

위에서 설명한 솔루션을 구현한 C++ 프로그램입니다.

#include <bits/stdc++.h>
using namespace std;
void sumPower(long int x) {
    vector<long int> powers;
    while (x > 0){
        powers.push_back(x % 2);
        x = x / 2;
    }
    for (int i = 0; i < powers.size(); i++){
        if (powers[i] == 1){
            cout << i;
            if (i != powers.size() - 1)
                cout<<", ";
        }
    }
    cout<<endl;
}
int main() {
    int number = 23342;
    cout<<"Powers of 2 that sum upto "<<number<<"are : ";
    sumPower(number);
    return 0;
}

코드 설명

sumPower 함수는 다음과 같은 순서로 동작합니다.

1. 주어진 수 x를 2로 나눈 나머지(x % 2)를 벡터에 저장하고, x를 2로 나눈 몫으로 갱신합니다. 이 과정을 x가 0이 될 때까지 반복합니다.
2. 이렇게 저장된 값들은 2진수의 각 자릿수를 낮은 자리부터 순서대로 담고 있습니다.
3. 벡터를 순회하면서 값이 1인 인덱스를 출력합니다. 해당 인덱스 i는 곧 2ⁱ가 합에 포함된다는 의미입니다.

실행 결과

Powers of 2 that sum upto 23342 are : 1, 2, 3, 5, 8, 9, 11, 12, 14

마무리

이 알고리즘의 시간 복잡도는 O(log N)으로 매우 효율적입니다. 숫자를 2로 나누는 횟수가 곧 연산 횟수이기 때문에, 입력값이 커져도 빠르게 결과를 얻을 수 있습니다. 이진수 변환의 원리만 이해하면 누구나 쉽게 구현할 수 있는 문제이므로, 비트 연산이나 진법 변환 개념을 익히는 좋은 연습 예제가 됩니다.