#1 부분 집합 풀기
#include<iostream>
using namespace std;
int main(void) {
int n = 4;
for (int mask = 0; mask < (1 << n); mask++) {
cout << "{ ";
for (int idx = 0; idx < n; ++idx) {
if ((mask >> idx) & 1) {
cout << idx + 1 << " ";
}
}
cout << "}\n";
}
}
부분집합
- 집합에서 고를 수 있는 모든 경우 (아무것도 안 고르는 것 포함)
- {1,2,3} 의 부분집합 → {}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} → 총 2^n개
조합
- n개 중에서 정확히 k개 고르는 경우
- {1,2,3} 에서 2개 고르는 조합 → {1,2}, {1,3}, {2,3} → 총 nCk개
관계로 보면:
부분집합 = k=0인 조합 + k=1인 조합 + k=2인 조합 + ... + k=n인 조합즉 부분집합이 조합을 전부 포함하는 더 큰 개념입니다.
https://junworld.tistory.com/2097
힌트스테이지 문제에서는 "번들을 살지 말지" 각각 독립적으로 결정하니까 부분집합 탐색이고, 만약 "n-1개 스테이지 중 정확히 3개만 번들을 산다"는 조건이 있었다면 조합 탐색이 됩니다.
두 원소의 합이 10이 나오는 부분 집합 개수 구하기
#include<iostream>
#include<string>
using namespace std;
int solve(int n, int arr[]) {
int count = 0;
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
int cnt = 0;
string subset = "{ ";
for (int idx = 0; idx < n; idx++) {
if ((mask >> idx) & 1) {
sum += arr[idx];
cnt++;
subset += to_string(arr[idx]) + " ";
}
}
if (cnt == 2 && sum == 7) {
cout << subset << "}\n";
count++;
}
}
return count;
}
int main() {
int n = 8;
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
cout << "개수: " << solve(n, arr) << "\n";
return 0;
}
비트마스킹 추가 예제
1단계 - 비트 연산 기본
#include <bits/stdc++.h>
using namespace std;
int main() {
int a = 5; // 0101
int b = 3; // 0011
cout << (a & b) << "\n"; // AND → 0001 = 1
cout << (a | b) << "\n"; // OR → 0111 = 7
cout << (a ^ b) << "\n"; // XOR → 0110 = 6
cout << (a << 1) << "\n"; // 왼쪽 시프트 → 1010 = 10
cout << (a >> 1) << "\n"; // 오른쪽 시프트 → 0010 = 2
}
2단계 - 특정 비트 켜기/끄기/확인
#include<iostream>
using namespace std;
void printBit(int mask, int size = 5) {
// 상위 비트부터 출력 (앞의 0도 포함)
for (int i = size - 1; i >= 0; i--) {
cout << ((mask >> i) & 1);
}
cout << "\n";
}
bool checkBit(int mask, int idx) {
if ((mask >> idx) & 1) {
cout << "true\n";
return true;
}
else {
cout << "false\n";
return false;
}
}
int main(void) {
int mask = 0;
// 0번째, 4번째 비트 켜기
mask |= (1 << 0);
mask |= (1 << 4);
printBit(mask); // 10001
// 0번째 비트 끄기
mask &= ~(1 << 0);
printBit(mask); // 10000
// 4번째 비트 확인
checkBit(mask, 4); // true
}3단계 - 부분집합 전체 출력
int main() {
vector<int> arr = {1, 2, 3, 4};
int n = arr.size();
for (int mask = 0; mask < (1 << n); mask++) {
cout << "{ ";
for (int i = 0; i < n; i++) {
if ((mask >> i) & 1) {
cout << arr[i] << " ";
}
}
cout << "}\n";
}
}출력:
{ }
{ 1 }
{ 2 }
{ 1 2 }
{ 3 }
...
{ 1 2 3 4 }4단계 - 부분집합 합이 특정 값인지 찾기
// {1, 2, 3, 4, 5} 중 합이 7인 부분집합 모두 출력
int main() {
vector<int> arr = {1, 2, 3, 4, 5};
int n = arr.size();
int target = 7;
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if ((mask >> i) & 1) {
sum += arr[i];
}
}
if (sum == target) {
cout << "{ ";
for (int i = 0; i < n; i++) {
if ((mask >> i) & 1) cout << arr[i] << " ";
}
cout << "}\n";
}
}
}
5단계 - 방문 체크 (visited 배열 대신 비트 사용)
// 일반적인 방법 (bool 배열)
int main() {
int n = 4;
vector<bool> visited(n, false);
visited[1] = true; // 1번 방문
visited[3] = true; // 3번 방문
cout << visited[1] << "\n"; // 1
cout << visited[2] << "\n"; // 0
}// 비트마스크로 똑같이 표현
int main() {
int n = 4;
int visited = 0; // 0000
visited |= (1 << 1); // 1번 방문 → 0010
visited |= (1 << 3); // 3번 방문 → 1010
cout << ((visited >> 1) & 1) << "\n"; // 1번 방문 확인 → 1
cout << ((visited >> 2) & 1) << "\n"; // 2번 방문 확인 → 0
}6단계 - 방문 체크 활용 (모든 노드 방문했는지 확인)
// 그래프에서 모든 노드를 방문했는지 확인하는 상황
int main() {
int n = 4;
int visited = 0;
int allVisited = (1 << n) - 1; // 1111 = 15 (모두 방문한 상태)
// 0, 1, 2, 3번 노드 순서대로 방문
for (int i = 0; i < n; i++) {
visited |= (1 << i);
cout << "현재 방문 상태: " << bitset<4>(visited) << "\n";
if (visited == allVisited) {
cout << "모든 노드 방문 완료!\n";
}
}
}현재 방문 상태: 0001
현재 방문 상태: 0011
현재 방문 상태: 0111
현재 방문 상태: 1111
모든 노드 방문 완료!7단계 - 비트마스크 DP (방문한 노드 집합을 상태로 저장)
// 4개 도시를 모두 방문하는 최소 비용 (외판원 순회 간단 버전)
// dist[i][j] = i번 도시에서 j번 도시로 가는 비용
int main() {
int n = 4;
vector<vector<int>> dist = {
{0, 10, 15, 20},
{10, 0, 35, 25},
{15, 35, 0, 30},
{20, 25, 30, 0}
};
// dp[visited][현재위치] = visited 상태에서 현재위치에 있을 때 최소 비용
// visited는 비트마스크로 표현 (어떤 도시를 방문했는지)
int allVisited = (1 << n) - 1; // 1111
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
dp[1][0] = 0; // 0번 도시에서 시작 (0번 방문 = 0001)
for (int visited = 1; visited < (1 << n); visited++) {
for (int cur = 0; cur < n; cur++) {
if (dp[visited][cur] == INT_MAX) continue;
// 아직 방문 안 한 도시로 이동
for (int next = 0; next < n; next++) {
if ((visited >> next) & 1) continue; // 이미 방문함
int nextVisited = visited | (1 << next);
dp[nextVisited][next] = min(dp[nextVisited][next],
dp[visited][cur] + dist[cur][next]);
}
}
}
// 모든 도시 방문 후 최소 비용
int ans = INT_MAX;
for (int cur = 0; cur < n; cur++) {
ans = min(ans, dp[allVisited][cur]);
}
cout << "최소 비용: " << ans << "\n"; // 60
}흐름을 정리하면:
1단계: & | ^ << >> 기본 연산
2단계: 켜기/끄기/확인 비트 조작
3단계: 부분집합 출력 완전탐색 활용
4단계: 부분집합 합 찾기 이번 문제랑 같은 구조
5단계: visited 비트로 표현 bool 배열 대체
6단계: 모든 노드 방문 확인 allVisited 패턴
7단계: 비트마스크 DP 외판원 순회7단계까지 직접 돌려보시면 웬만한 비트마스킹 문제는 다 풀 수 있을 거예요.
비트마스킹 핵심 패턴 6가지
cpp
// 1. idx번째 비트 켜기
S |= (1 << idx)
// 예) S=10000, idx=1 → 10010
// 2. idx번째 비트 끄기
S &= ~(1 << idx)
// 예) S=10010, idx=1 → 10000
// 3. idx번째 비트 반전 (0→1, 1→0)
S ^= (1 << idx)
// 예) S=10010, idx=1 → 10000
// S=10000, idx=1 → 10010
// 4. idx번째 비트 켜져있는지 확인
if (S & (1 << idx))
// 예) S=10010, idx=1 → true
// S=10010, idx=0 → false
// 5. n개 비트 전부 켜기
(1 << n) - 1
// 예) n=4 → 1111 = 15
// 6. 최하위 켜진 비트 찾기 (2의 보수 활용)
S & -S
// 예) S=10010 → 00010 = 2
연습 예제 (단계별)
예제 6개 + 연습문제 1개로 구성했습니다. 흐름은 이렇습니다:
| 예제 | 내용 | 핵심 패턴 |
| 1 | 비트 켜기/끄기/확인 | |= &= ~ & (1<<idx) |
| 2 | 부분집합 전체 출력 | mask=0 ~ (1<<n) |
| 3 | 합이 7인 부분집합 | 부분집합 + 조건 필터 |
| 4 | 방문 체크 | visited, allVisited |
| 5 | 최하위 켜진 비트 | S & -S (2의 보수) |
| 6 | XOR 비트 반전 | ^= 토글 |
| 연습 | 원소 2개인 부분집합 | __builtin_popcount |
printBits 함수로 이진수를 눈으로 보면서 확인할 수 있게 했으니, 각 예제 출력을 보면서 비트가 어떻게 바뀌는지 따라가보시면 빠르게 감이 잡힐 거예요.
#include <bits/stdc++.h>
using namespace std;
// 이진수로 출력해주는 헬퍼 함수 (이해하기 쉽게)
void printBits(int n, int size = 5) {
for (int i = size - 1; i >= 0; i--) {
cout << ((n >> i) & 1);
}
cout << " (" << n << ")";
}
// =============================================
// 예제 1. 비트 켜기 / 끄기 / 확인
// =============================================
void example1() {
cout << "===== 예제 1. 비트 켜기 / 끄기 / 확인 =====\n";
int S = 0b10000; // 16
cout << "초기값 S = "; printBits(S); cout << "\n";
// 1번째 비트 켜기
S |= (1 << 1);
cout << "1번째 비트 켜기 후: "; printBits(S); cout << "\n";
// 3번째 비트 켜기
S |= (1 << 3);
cout << "3번째 비트 켜기 후: "; printBits(S); cout << "\n";
// 1번째 비트 끄기
S &= ~(1 << 1);
cout << "1번째 비트 끄기 후: "; printBits(S); cout << "\n";
// 3번째 비트 켜져있는지 확인
if (S & (1 << 3)) cout << "3번째 비트 켜져 있음\n";
else cout << "3번째 비트 꺼져 있음\n";
// 1번째 비트 켜져있는지 확인
if (S & (1 << 1)) cout << "1번째 비트 켜져 있음\n";
else cout << "1번째 비트 꺼져 있음\n";
cout << "\n";
}
// =============================================
// 예제 2. 부분집합 전체 출력
// =============================================
void example2() {
cout << "===== 예제 2. 부분집합 전체 출력 =====\n";
vector<string> items = {"사과", "딸기", "포도", "배"};
int n = items.size();
// 0b0000 ~ 0b1111 (0 ~ 15) 순회 = 모든 부분집합
for (int mask = 0; mask < (1 << n); mask++) {
cout << "mask="; printBits(mask, 4); cout << " → { ";
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
cout << items[i] << " ";
}
}
cout << "}\n";
}
cout << "\n";
}
// =============================================
// 예제 3. 부분집합 합이 target인 경우 찾기
// =============================================
void example3() {
cout << "===== 예제 3. 합이 7인 부분집합 찾기 =====\n";
vector<int> arr = {1, 2, 3, 4, 5};
int n = arr.size();
int target = 7;
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) sum += arr[i];
}
if (sum == target) {
cout << "{ ";
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) cout << arr[i] << " ";
}
cout << "} = " << target << "\n";
}
}
cout << "\n";
}
// =============================================
// 예제 4. 비트로 방문 체크 (visited 대신)
// =============================================
void example4() {
cout << "===== 예제 4. 비트로 방문 체크 =====\n";
int n = 5;
int visited = 0;
int allVisited = (1 << n) - 1; // 11111
cout << "목표 상태(전부 방문): "; printBits(allVisited); cout << "\n\n";
// 0, 2, 4번 노드 방문
vector<int> order = {0, 2, 4};
for (int node : order) {
visited |= (1 << node);
cout << node << "번 노드 방문 후: "; printBits(visited); cout << "\n";
}
cout << "\n모든 노드 방문했나? ";
cout << (visited == allVisited ? "YES" : "NO") << "\n";
// 나머지도 방문
visited |= (1 << 1);
visited |= (1 << 3);
cout << "나머지 방문 후: "; printBits(visited); cout << "\n";
cout << "모든 노드 방문했나? ";
cout << (visited == allVisited ? "YES" : "NO") << "\n\n";
}
// =============================================
// 예제 5. 최하위 켜진 비트 찾기 (2의 보수 활용)
// =============================================
void example5() {
cout << "===== 예제 5. 최하위 켜진 비트 찾기 =====\n";
vector<int> tests = {0b10010, 0b10100, 0b11000};
for (int S : tests) {
int lowest = S & -S;
cout << "S = "; printBits(S);
cout << " → 최하위 켜진 비트 = "; printBits(lowest);
cout << "\n";
}
cout << "\n";
}
// =============================================
// 예제 6. XOR로 비트 반전
// =============================================
void example6() {
cout << "===== 예제 6. XOR로 비트 반전 =====\n";
int S = 0b10000;
cout << "초기값: "; printBits(S); cout << "\n";
// 토글처럼 사용 (켜져있으면 끄고, 꺼져있으면 켜고)
for (int i = 0; i < 3; i++) {
S ^= (1 << 1); // 1번째 비트 반전
cout << "1번째 비트 반전: "; printBits(S); cout << "\n";
}
cout << "\n";
}
// =============================================
// 연습 문제: 아래 TODO를 직접 채워보세요!
// =============================================
void practice() {
cout << "===== 연습 문제 =====\n";
cout << "{1, 2, 3, 4, 5} 중 원소 개수가 정확히 2개인 부분집합을 출력하세요.\n";
vector<int> arr = {1, 2, 3, 4, 5};
int n = arr.size();
for (int mask = 0; mask < (1 << n); mask++) {
// TODO: mask에서 켜진 비트 수를 세서 2개인 경우만 출력
int cnt = __builtin_popcount(mask); // 켜진 비트 수 세기
if (cnt == 2) {
cout << "{ ";
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) cout << arr[i] << " ";
}
cout << "}\n";
}
}
}
int main() {
example1();
example2();
example3();
example4();
example5();
example6();
practice();
return 0;
}
Extra
비트마스킹 핵심 패턴
n개 원소 집합의 모든 부분집합 순회
for (int mask = 0; mask < (1 << n); mask++)
// n=4이면 0000 ~ 1111, 총 16가지idx번째 원소 확인 (켜져있는지)
if ((mask >> idx) & 1)
// mask=0101, idx=2 → (0101 >> 2) & 1 = 0001 & 1 = 1 → 존재
// mask=0101, idx=1 → (0101 >> 1) & 1 = 0010 & 1 = 0 → 없음idx번째 원소 추가 (비트 켜기)
mask |= (1 << idx)
// mask=0101, idx=1 → 0101 | 0010 = 0111idx번째 원소 삭제 (비트 끄기)
mask &= ~(1 << idx)
// mask=0101, idx=2 → 0101 & ~0100 = 0101 & 1011 = 0001idx번째 원소 반전 (0→1, 1→0)
mask ^= (1 << idx)
// mask=0101, idx=1 → 0101 ^ 0010 = 0111 (켜짐)
// mask=0111, idx=1 → 0111 ^ 0010 = 0101 (꺼짐)n개 비트 전부 켜기 (모든 원소 포함)
(1 << n) - 1
// n=4 → 10000 - 1 = 01111최하위 켜진 비트 찾기
mask & -mask
// mask=10010 → 00010 (2의 보수 활용)'프로그래머스 > 코딩테스트' 카테고리의 다른 글
| lv2 ) 완전범죄(틀림) 그리디 vs DP (0) | 2026.06.19 |
|---|---|
| lv2) 멀리 뛰기 (0) | 2026.06.16 |
| lv3 ) 섬 연결하기 [다시] (0) | 2026.05.29 |
| lv3 ) 기지국 설치 [다시] (0) | 2026.05.28 |
| lv3 ) 야근 지수 (0) | 2026.05.27 |