브루트포스와 백트래킹의 차이점에 대해 공부해보자

문제 링크

분류

백트래킹 (Back Tracking), 브루트포스 알고리즘 (Bruteforce Algorithm)

풀이

수의 개수를 $N$이라고 하자. 그러면 우리는 $N-1$개의 연산자를 각각의 수 사이에 삽입하여 각각의 값을 구하고, 이것의 최대 최소를 살펴보면 된다.
순진하게 생각하여, 연산자가 덧셈, 뺄셈, 곱셈, 나눗셈 총 4개가 존재하고 이를 $N-1$번만큼 생각하면 되므로 총 경우의 수는 $4^{N-1}$이라는 것을 알 수 있다. 한편 문제에서 주어진 $N$의 범위는 $2\le N \le 11 $이고, 시간 제한이 2초이므로 지수 시간으로 문제를 풀이할 수 있다. 다음의 수식을 참고하자. \(\because 4^{N-1} \le 4^{10} \le 2^{20} \approx 10^6\)
또한, 백트래킹을 잉요하여 주어진 연산자의 개수에 대한 규칙에 의해 존재할 수 없는 경우는 탐색하지 않음으로써 연산 횟수를 더 줄일 수 있다. 예를 들어 다음 테스트케이스를 참고하자.

3
1 3 5
0 1 1 0

모든 경우의 수를 살펴보는 경우에는 $1 + 3 + 5$와 같이 존재할 수 없는 경우에 대해서도 탐색하여야 하고, 연산자의 개수가 위의 조건과 맞는지 판단하는 등 상대적으로 많은 연산을 필요로 한다.
하지만, 백트래킹을 이용하여 구현할 경우 다음의 경우만 고려하게 된다.

1 * 3 - 5
1 - 3 * 5

여담: 고려해야 하는 경우의 수 비교

브루트포스에서는 앞서 다룬 바와 같이 $4^{N-1}$만큼의 사건을 고려해야 한다. 반면, 백트래킹 방법에서는 덧셈, 뺄셈, 곱셈, 나눗셈의 개수를 각각 $a, b, c, d$라 하면, 다음과 같이 나타낼 수 있다. \(\frac{(N-1)!}{a!b!c!d!} \quad \text{where} \quad a+b+c+d=N-1\) 한편, $N=11$의 경우에서 $10! = 3628800$이고, $a!b!c!d! \geq 2!2!3!3!$임이 자명하므로 $10! \le 4^{10}$임이 자명하다. 따라서 백트래킹을 사용하는 것이 더 효율적이다.
임의의 자연수 $N$에 대하여 성립하는지 증명하는 방법은 좀 더 고민해봐야겠다.

수형도를 통한 증명

(2024.01.21. 추가) 사실 수형도를 통해 증명하면 백트래킹에서의 고려해야 하는 경우의 수가 브루트포스에서 고려해야 하는 경우의 수보다 작다는 것을 자명하게 보일 수 있다. 브루트포스 알고리즘에서 다루어야 하는 경우의 수를 수형도로 나타냈을 때, 여기서 나타나지는 사건은 백트래킹에서 다루는 사건을 포함하고 있다는 것이 자명하기 때문이다.
위와 같은 서술을 진행한 것은 단지 대수적으로 자명하게 보일 수 있는지 궁금하였기 때문이다.

소스코드

Github

// 14888 연산자 끼워 넣기
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using LL = unsigned long long;
using lll = __int128_t;
using LLL = __uint128_t;  // 128비트 정수는 cout, printf 등으로 출력할 수 없음에 유의

ll INF = 100'000'000'000;

// 3-pair
struct dt {
    ll a;
    ll b;
};

// vector<pair>
using vdt = vector<dt>;

vll v;
ll ans_max = -INF, ans_min = INF, n, a, b, c, d;

void back_tracking(ll depth, ll current) {
    if (depth == n) {
        if (current > ans_max) ans_max = current;
        if (current < ans_min) ans_min = current;
        return;
    }

    if (a != 0) {
        a--;
        back_tracking(depth + 1, current + v[depth]);
        a++;
    }
    if (b != 0) {
        b--;
        back_tracking(depth + 1, current - v[depth]);
        b++;
    }
    if (c != 0) {
        c--;
        back_tracking(depth + 1, current * v[depth]);
        c++;
    }
    if (d != 0) {
        d--;
        back_tracking(depth + 1, current / v[depth]);
        d++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    v.resize(n);
    for (auto& k : v) {
        cin >> k;
    }
    cin >> a >> b >> c >> d;

    back_tracking(1, v[0]);

    cout << ans_max << '\n' << ans_min;
}