개요
이 튜토리얼에서는 주어진 숫자 n에 대해 비트 OR(bitwise OR) 연산의 결과가 n과 같아지는 가장 큰 집합을 찾는 프로그램을 작성해 보겠습니다.
여기서 '가장 큰 집합'이란 0부터 n 사이의 숫자 중, 각 숫자 i와 n을 비트 OR 연산했을 때 결과가 n이 되는 모든 숫자들을 모은 집합을 의미합니다.
문제 해결 접근 방법
문제를 해결하는 단계는 다음과 같습니다.
- 숫자 n을 초기화합니다.
- 0부터 n까지 반복하는 루프를 작성합니다.
- i | n의 결과가 n과 같다면 i를 결과 집합에 추가합니다.
- 완성된 결과 집합을 반환합니다.
동작 원리
비트 OR 연산의 특성상, 어떤 수 i와 n을 OR 연산한 결과가 n이 되려면 i에서 1인 비트들이 반드시 n에서 1인 비트들 안에 포함되어 있어야 합니다. 즉, i의 비트 패턴이 n의 부분 집합(subset)이어야 합니다.
예를 들어 n = 5(이진수 101)라면, 조건을 만족하는 값은 0(000), 1(001), 4(100), 5(101)뿐입니다. 이 네 숫자만 n과 OR 연산했을 때 결과가 그대로 5가 됩니다.
예제 코드
실제 동작하는 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void printBitWiseOrSet(int n) {
vector<int> v;
for (int i = 0; i <= n; i++) {
if ((i | n) == n) {
v.push_back(i);
}
}
for (int i = 0; i < v.size(); i++) {
cout << v[i] << ' ';
}
cout << endl;
}
int main() {
int n = 7;
printBitWiseOrSet(n);
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
0 1 2 3 4 5 6 7
n = 7(이진수 111)은 모든 비트가 1이므로, 0부터 7까지의 모든 숫자가 조건을 만족하게 됩니다. 따라서 결과로 전체 범위의 숫자가 출력됩니다.
시간 복잡도
이 알고리즘은 0부터 n까지 한 번씩 확인하므로 시간 복잡도는 O(n)입니다. 만약 n의 비트 패턴을 직접 순회하는 방식으로 구현하면, 1인 비트의 개수를 k라고 할 때 O(2^k)로 더 효율적으로 개선할 수도 있습니다.
결론
이 튜토리얼에서는 비트 OR 연산 결과가 주어진 수 n과 같아지는 가장 큰 집합을 찾는 방법을 알아보았습니다. 핵심은 'i의 1인 비트가 n의 1인 비트에 포함되는지'를 검사하는 것입니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.