N개의 요소를 가진 배열이 주어졌습니다. 목표는 곱이 2의 거듭제곱(2ᵏ, k≥0)이 되는 모든 쌍(Arr[i], Arr[j])의 개수를 구하는 것입니다. 단, i≠j여야 하며, 같은 쌍이 중복해서 세어지지 않도록 일반적으로 i<j인 조합만 확인합니다.
이 문제는 각 쌍의 곱을 계산한 뒤, 해당 값이 2의 거듭제곱인지 판별하는 방식으로 해결할 수 있습니다. 가장 직관적인 판별 방법은 log₂를 활용하는 것입니다. 어떤 양수 x가 2의 거듭제곱일 때 log₂(x)는 항상 정수이므로, ceil(log₂(x))와 floor(log₂(x))의 값이 서로 같습니다. 반대로 2의 거듭제곱이 아니라면 두 값은 달라집니다.
예시로 이해하기
입력 − Arr[]= { 2, 5, 8, 16, 128 }, N=5
출력 − 곱이 2의 거듭제곱인 쌍의 개수 − 6
설명 −
Arr[0]×Arr[2]=2×8=16=2⁴ → 2의 거듭제곱 Arr[0]×Arr[3]=2×16=32=2⁵ → 2의 거듭제곱 Arr[0]×Arr[4]=2×128=256=2⁸ → 2의 거듭제곱 Arr[2]×Arr[3]=8×16=128=2⁷ → 2의 거듭제곱 Arr[2]×Arr[4]=8×128=1024=2¹⁰ → 2의 거듭제곱 Arr[3]×Arr[4]=16×128=2048=2¹¹ → 2의 거듭제곱 나머지 쌍들의 곱은 10, 40, 80, 640으로 2의 거듭제곱이 아닙니다.
입력 − Arr[]= { 3, 3, 3 }, N=3
출력 − 곱이 2의 거듭제곱인 쌍의 개수 − 0
설명 − 모든 쌍의 곱이 9이며, 이는 2의 거듭제곱이 아닙니다.
프로그램에 적용된 접근 방식
- 임의의 숫자로 초기화된 정수 배열 Arr[]를 준비합니다.
- 배열의 길이를 저장할 변수 n을 선언합니다.
- 함수 countPairs(int arr[], int n)는 배열과 그 길이를 입력받아, 곱이 2의 거듭제곱이 되는 쌍의 개수를 반환합니다.
- 두 개의 for 루프를 중첩하여 배열 내 모든 쌍을 탐색합니다.
- 바깥 루프는 0≤i<n-1, 안쪽 루프는 i<j<n 범위를 순회하므로 동일한 쌍이 중복 계산되지 않습니다.
- 각 쌍에 대해 prod = arr[i] * arr[j]를 계산합니다. 이때 prod는 양수여야 log₂를 적용할 수 있습니다.
- ceil(log₂(prod)) == floor(log₂(prod))인지 확인합니다. 참이라면 prod는 2의 거듭제곱이므로 count를 1 증가시킵니다.
- 모든 루프가 종료되면 count에는 조건을 만족하는 쌍의 총 개수가 저장됩니다.
- count를 결과값으로 반환합니다.
참고로, 부동소수점 연산 없이 더 빠르게 판별하고 싶다면 비트 연산을 활용할 수도 있습니다. 양수 prod에 대해 (prod & (prod-1)) == 0이면 prod는 2의 거듭제곱입니다. 다만 prod가 0일 경우 이 식이 항상 참이 되므로, 0 여부를 먼저 확인해야 한다는 점에 유의하세요.
예제
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int countPairs(int arr[], int n){
int count=0;
int prod=0;
for(int i=0;i<n-1;i++){
for(int j=i+1;j<n;j++){
prod=arr[i]*arr[j];
if( ceil(log2(prod))==floor(log2(prod)) ){
count++;
//cout<<endl<<"a :"<<arr[i]<<" b :"<<arr[j]; //to print
}
}
}
return count;
}
int main(){
int arr[] = { 2, 5, 8, 16, 128 };
int n = sizeof(arr) / sizeof(arr[0]);
cout <<endl<<"Pairs whose product is power of 2:"<<countPairs(arr, n);
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 생성됩니다 −
Pairs whose product is power of 2:6