문제 이해하기
이 문제에서는 N개의 정수로 이루어진 배열이 주어지며, 각 원소를 곱했을 때 그 결과가 2의 거듭제곱이 되는 부분수열(subsequence)의 개수를 구해야 합니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
- 입력 − arr = [2, 5, 4]
- 출력 − 3
- 설명 − 부분수열 [2], [4], [2, 4]가 조건을 만족합니다.
해결 접근 방법
이 문제를 해결하려면 거듭제곱의 기본적인 성질을 이해해야 합니다.
여러 수를 곱한 결과가 2의 거듭제곱이 되려면, 곱해지는 모든 수가 반드시 2의 거듭제곱이어야 합니다. 만약 배열에 5처럼 2의 거듭제곱이 아닌 수가 포함되면, 그 수가 곱해지는 순간 결과에 2 이외의 소인수가 생기기 때문에 더 이상 2의 거듭제곱이 될 수 없습니다.
따라서 우리는 배열에서 2의 거듭제곱에 해당하는 원소들만 고려하면 됩니다. 참고로 1은 2⁰이므로 2의 거듭제곱으로 취급합니다.
배열에 2의 거듭제곱인 원소가 M개 있다면, 이들로 만들 수 있는 부분수열의 개수는 2M − 1입니다. 각 원소마다 '부분수열에 포함한다 / 포함하지 않는다'라는 두 가지 선택지가 있으므로 총 2M가지의 조합이 가능하고, 여기서 어떤 원소도 선택하지 않는 공집합 1가지를 빼주면 됩니다.
구현 예제
위에서 설명한 해결 방법을 구현한 프로그램은 다음과 같습니다.
#include <iostream>
#include <math.h>
using namespace std;
bool isPowerTwo(int num) {
if (num == 0)
return false;
if (num == 1)
return true;
if (num & (num - 1))
return false;
return true;
}
int SubsequenceWithPowerTwo(int arr[], int N) {
int count = 0;
for (int i = 0; i < N; i++)
if (isPowerTwo(arr[i]))
count++;
return (int)(pow(2, count)) - 1;
}
int main() {
int arr[] = {5, 4, 8, 12, 32, 9 };
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"2의 거듭제곱이 되는 곱을 갖는 부분수열의 개수 : ";
cout<<SubsequenceWithPowerTwo(arr, N)<<endl;
return 0;
}실행 결과
2의 거듭제곱이 되는 곱을 갖는 부분수열의 개수 : 7
코드 설명
코드의 핵심인 isPowerTwo 함수는 비트 연산을 활용하여 매우 효율적으로 동작합니다. 2의 거듭제곱인 수는 이진수로 표현했을 때 단 하나의 비트만 1이므로, num & (num - 1)의 결과가 0이라면 해당 수는 2의 거듭제곱임을 알 수 있습니다.
예제 배열 {5, 4, 8, 12, 32, 9}에서 2의 거듭제곱에 해당하는 원소는 4, 8, 32로 총 3개(M = 3)입니다. 따라서 정답은 2³ − 1 = 7이 됩니다. 전체 시간 복잡도는 배열을 한 번만 순회하므로 O(N)입니다.