1. 부르트포스
브루트포스(Brute Force)란?
- 가능한 모든 경우의 수를 전부 시도해보는 "무식한" 문제 해결 방법.
- 최적화된 알고리즘을 떠올리기 어려울 때나 검증 과정에서 자주 활용됩니다.
브루트포스의 시간 복잡도
- 부분집합 탐색: 2^n
- 순열 탐색: n!
- 중첩 반복문을 통한 조합 탐색
n이 작다면 충분히 시도할 만하지만, 지수적 증가로 인해 크기에 주의 필요.
예: n=10 → 부분집합: 2^10=1024, 순열: 10! =3,628,800
2. 비트마스킹
비트마스킹(Bitmasking)이란?
- 이진수(0과 1)로 이루어진 비트를 활용하여 데이터를 표현하고 조작하는 기법
- 보통 정수형 변수의 각 비트를 ON(1) 또는 OFF(0)로 설정하여 특정 상태를 관리할 때 사용.
💡 왜 사용할까?
- 배열을 사용하지 않고도 빠르게 여러 상태를 저장할 수 있음
- 비트 연산을 활용하면 탐색, 계산 속도가 빠름
- 메모리를 절약할 수 있음
비트마스킹의 핵심 개념
- 각 비트는 특정 의미를 가질 수 있음
예를 들어, 101이라는 이진수를 보자.- 첫 번째(맨 오른쪽) 비트: 1 → 켜짐 (ON)
- 두 번째 비트: 0 → 꺼짐 (OFF)
- 세 번째 비트: 1 → 켜짐 (ON)
- 비트 연산을 이용한 조작 방법
연산 설명 예시 AND & 특정 비트가 켜져 있는지 확인 101 & 001 = 001 (세 번째 비트가 켜져 있음) OR | 특정 비트를 켜기 100 | 010 = 110 XOR ^ 특정 비트 토글(0 → 1, 1 → 0) 110 ^ 010 = 100 SHIFT <<, >> 비트 위치 이동 001 << 2 = 100
3. 브루트포스 구현 방법
3-1. 중첩 반복문
- 직관적이지만 범위가 크면 비효율적
- 예제: 1~3까지의 숫자 3개를 중복 선택하여 나열
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
for (int k = 1; k <= 3; k++) {
cout << i << " " << j << " " << k << "\n";
}
}
}
3-2. 비트마스킹을 활용한 부분집합 탐색
- 집합 {1,2,3}의 경우 총 2^3=개의 부분집합 존재
- 이진수 표현을 활용하여 부분집합을 탐색 가능
0 -> 000 -> 공집합
1 -> 001 -> {3}
2 -> 010 -> {2}
3 -> 011 -> {2,3}
4 -> 100 -> {1}
5 -> 101 -> {1,3}
6 -> 110 -> {1,2}
7 -> 111 -> {1,2,3}
#include <iostream>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {1, 2, 3};
int n = arr.size();
// 0부터 2^n - 1까지 부분집합의 모든 경우 탐색
for (int i = 0; i < (1 << n); i++) {
cout << "{ ";
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
// i번째 원소가 포함되었는지 확인
// bit는 정수지만, 2진수로 보면 비트의 집합
// (1 << j)의 역할: 특정 비트만 체크
// i & (1 << j) != 0 이면 True 이기 때문에 해당 자리 원소 출력
cout << arr[j] << " ";
}
}
cout << "}\n";
}
}
정수 n(1 ≤ n ≤ 100)이 주어질 때, 다음 식을 만족하는 (a, b, c)의 개수를 구하는 문제를 불필요한 중복 제거를 하여 풀어보세요. (제출 + 발표)
a + b^2 + c^3 = n#include <iostream>
using namespace std;
int main() {
int n = 10000; // 입력값
int count = 0;
for (int b = 1; b * b <= n; b++) { // b^2가 n을 초과하지 않는 범위까지만 탐색
for (int c = 1; b * b + c * c * c <= n; c++) { // b^2 + c^3이 n을 초과하지 않는 범위까지만 탐색
int a = n - (b * b + c * c * c);
if (a >= 1 && a <= 100) { // a가 자연수(1~100) 범위 내에 있어야 유효한 해
count++;
}
}
}
cout << count;
}