[내일배움캠프 Day56] 브루트포스 과제

브루트포스(Brute Force)는 말 그대로 무식하게 문제를 푸는 방법입니다. 가능한 모든 경우의 수를 전부 시도해 보는 것입니다.

 

과거 '프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략' 책에 나오는 브루트포스에 대해 정리한 글을 추가합니다.

https://dev0404.tistory.com/24

완전 탐색(Brute Force)

 

강의에서는 위와 같은 내용 이외에도 경우의 수를 ‘어떻게’ 만들어 낼지에 대해 여러 가지 전략을 알려주셨습니다.

1. 중첩 반복문을 활용한 직접 생성
2. bitmasking을 활용한 부분집합 생성
3. STL의 next_permutation 등을 활용한 순열 생성
4. 백트래킹

 

이 중 bitmasking에 대해 더 자세하게 설명하면 부분집합을 전부 순회하는 전형적인 방법 중 하나로

https://blog.encrypted.gg/1093

[실전 알고리즘] 부록 C - 비트마스킹

바킹독님 알고리즘 강의를 참고하면, 비트마스킹은 0과 1을 담고 있는 비트를 이용해서 연산을 효율적으로 하는 방법을 말합니다.

 

위 내용이 비트마스킹의 중요 내용입니다. 이제 챌린지반 과제로 넘어가면

 

숙제 1. 비트마스킹 기법을 C++로 구현하거나 혹은 아래와 같이 구현된 코드를 해석해서 정리해주세요.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {1, 2, 3};
    int n = arr.size();

    for (int i = 0; i < (1 << n); i++) {
        cout << "{ ";
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) {
                cout << arr[j] << " ";
            }
        }
        cout << "}\\n";
    }
}

첫 번째 과제는 바킹독님 강의에도 나온 내용으로 제 답안은 아래와 같습니다.

 

위 그림과 같이 0001, 0010, 0100, 1000과 AND 연산을 하면 각 비트가 0인지 1인지를 판단할 수 있다.

left shift를 이용해 1을 각각 0, 1, 2, 3칸 밀면 저 수들을 만들 수 있으므로 ( 1 << j )가 나옴.

즉, if (i & (1 << j)) 를 통해 i의 j번째 비트가 1이면 arr[j] 출력하는 코드다.

예를 들면, i = 5(101) 일 때는

• j=0 일 때, (101) & (001) = (001) 로 1 → arr[0] 출력
• j=1 일 때, (101) & (010) = (000) 로 0
• j=2 일때, (101) & (100) = (100) 로 4 → arr[2] 출력
• 출력 : { 1 3 }

 

숙제 2. 정수 n(1 ≤ n ≤ 100)이 주어질 때, 다음 식을 만족하는 (a, b, c)의 개수를 구하는 문제를 불필요한 중복 제거를 하여 풀어보세요.

a + b^2 + c^3 = n

 

강의에서 a, b, c가 중복될 수 있는 경우에 대한 답안은 제공해 주셨습니다. 

Q. 정수 n(1 ≤ n ≤ 100)이 주어질 때, 다음 식을 만족하는 (a, b, c)의 개수를 구하라. 단, a, b, c는 1 이상 100 이하인 자연수로 가정하고, a, b, c가 중복될 수 있음.

int count = 0;
for (int a = 1; a <= 100; a++) {
    for (int b = 1; b <= 100; b++) {
        for (int c = 1; c <= 100; c++) {
            if (a + b*b + c*c*c == n) {
                count++;
            }
        }
    }
}
cout << count;

위와 같이 단순 접근을 하면 시간 복잡도는 대략 O(100 * 100 * 100) = 10^6, 백만 번 정도의 연산입니다. n이 100 이상 더 큰 수라면 문제가 되지만 n이 100이라면 충분히 가능합니다.

 

하지만 저희 과제는 중복 제거를 고려해야 하는데 힌트는 아래와 같습니다.

 

위와 같은 2가지 방법을 참고하여 아래와 같이 코드를 짰습니다.

#include <iostream>
using namespace std;

int solution(int n) {
    int cnt = 0;
    for (int b = 1; b * b <= n; b++)
    {
        int b2 = b * b;
        for (int c = 1; c * c * c <= n; c++)
        {
            int c3 = c * c * c;
            if ((n - (b2 + c3)) > 0)
            {
                cnt++;
            }
        }
    }

    return cnt;
}

int main() {
    int n;
    cin >> n;
    cout << solution(n);

    return 0;
}