[Algorithm] 무차별 대입법

무차별 대입법 (Brute Force)

무차별 대입법은 모든 가능한 값을 다 시도해보는 형태의 전략을 의미한다.

그 중에서도 알고리즘 분야에서는 중첩 루프를 이용하여 표현하는 전략을 의미한다.

무차별 대입을 하는데 있어 필요한 개념들을 정리해보자.

 

순서쌍

다음과 같은 문제를 생각해보자.

두 자연수 n과 k에 대해 (1 <= n, k < 1000),
다음 식을 만족시키는 모든 순서쌍을 구하여라

2 * n * n - (k * k + 2) * n + (3 * k - 2) = 0

이 문제에는 n, k의 범위가 충분히 컴퓨팅 파워로 커버가능한 범위 안에 있기 때문에,

중첩 루프를 이용하여 쉽게 모든 순서쌍을 테스트해볼 수 있다.

(이런 형태의 순서쌍 문제는 단순 완전탐색에서 자주 등장하는 유형이다.)

void OrderedPair()
{
    for (int n = 1; n < 1000; ++n)
    {
        for (int k = 1; k < 1000; ++k)
        {
            if (2 * n * n - (k * k + 2) * n + (3 * k - 2) == 0)
            {
                cout << n << " " << k << endl;
            }
        }
    }
}

 

 

또 다른 예로, 다음 문제를 생각해보자.

7개의 원소 중 4개를 선택하는 모든 조합을 출력하시오

이 또한 {1, 2, 3, 4, 5, 6, 7} 의 모든 순서쌍 (x, y, z, w)를 중복 없이 구하는 문제이고,

모든 미지수 x, y, z, w이 가능한 모든 범위를 4중 중첩 루프를 순회하는 형태로 구현이 가능하다.

    for (int x = 1; x <= n; ++x)
    {
        for (int y = x + 1; y <= n; ++y)
        {
            for (int z = y + 1; z <= n; ++z)
            {
                for (int w = z + 1; w <= n; ++w)
                {
                    cout << x << " " << y << " " << z << " " << w << endl;
                }
            }
        }
    }

 

또 다른 예로, 다음 문제를 생각해보자.

N개의 물체가 있을 때, 어떤 두 물체가 서로 충돌을 했는지 감지하는 알고리즘을 작성하시오.
각 물체는 현재 위치와 충돌영역에 대한 반지름 r1, r2를 갖고 있고,
서로의 반지름이 겹치는 경우 충돌했다고 판단한다.

 

객체의 수가 적다면, 서로 다른 두 객체에 대한 모든 순서쌍을 만들고,

두 객체의 위치 사이의 거리가 두 객체의 반지름의 합보다 작다면 충돌했다고 판단할 수 있을 것이다.

 

 

코드는 다음과 같다.

struct Object
{
    Object(int x, int y, int r) : x(x), y(y), r(r) {}
    int x, y, r;
};

bool HasCollide(Object a, Object b)
{
    int distanceSq = (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
    int radsumSq = (a.r + b.r) * (a.r + b.r);
    return distanceSq < radsumSq;
}

void CollideTest()
{
    vector<Object> objects =
    {
        Object(0, 0, 2),
        Object(4, 6, 5),
        Object(7, 3, 4),
        Object(15, 11, 3),
    };

    for (int i = 0; i < objects.size(); ++i)
    {
        for (int j = i + 1; j < objects.size(); ++j)
        {
            Object a = objects[i];
            Object b = objects[j];
            if (HasCollide(a, b))
            {
                cout <<"("<< a.x << " " << a.y << ")  (" << b.x << " " << b.y << ")" << endl;
            }
        }
    }
}

 

이처럼, 찾아야하는 순서쌍 (x, y, z ...) 이 있을 때,

혹은 찾아야 하는 답을 순서쌍의 형태로 표현할 수 있을 때,

모든 미지수들에 대하여, 모든 가능한 범위에 대하여, 순회하며 나열해보는 것이다.

만약 문제에서 최적해를 요구한다면, 모든 나열된 경우의 수 중, 가장 최선의 답을 선택하면 될 것이다.

 

 

한정명제

루프를 이용한 완전탐색 과정에서는 한정명제가 자주 이용된다.

한정명제에는 전칭명제(Universal Proposition)와 존재명제가 있다.

 

전칭명제

전칭명제는 명제 P(x)가 정의되어 있을 때,

모든 x에 대해 P(x)가 참인 명제를 의미한다.

기호 : ∀xP(x)

영어 : for all x, P(x)

형태로 표현한다.

 

예시를 위한 명제를 정의해보자.

P(x) = (x > 0) 이면 참, 아닌경우 거짓.

 

다음과 같은 원소들이 x의 후보로 있을 때,

1, 3, 7, 8

1 > 0	true
3 > 0	true
7 > 0	true
8 > 0	true

모든 원소에 대해 참이므로,

∀xP(x) 는 참이다.

 

전칭명제를 코드로 구현하는 경우 일반적으로 다음과 같이 작성한다.

전칭명제는 단 한번이라도 거짓인 경우가 있다면 전체 명제가 거짓이기 때문에, 코드를 작성할때는 이를 활용한다.

vector<int> elements = {1, 3, 7, 8};
bool flag = true;

for (int x : elements)
{
    if (x <= 0)
    {
        flag = false;
        break;
    }
}

// flag를 확인한다.

 

하지만 실제 알고리즘 작성을 하는 경우 중첩된 루프 속에서 여러 한정명제들이 섞여있기 때문에 코드 작성이 어려워질 수 있다. 그러므로 한정명제가 나오는 상황은 따로 함수로 분리하는것이 좋은 전략이 될 것이다.

int All(vector<int> elements)
{
    for (int x : elements)
    {
        if (x <= 0)
            return false;
    }
    return true;
}

 

존재명제

존재명제는 명제 P(x)가 정의되어 있을 때,

적어도 하나의 x에 대해 P(x)가 참인 명제를 의미한다.

기호 : ∃xP(x)

영어 : there exists x, P(x)

형태로 표현한다.

 

예시를 위한 명제를 정의해보자.

P(x) = (x == 1) 이면 참, 아닌경우 거짓.

 

다음과 같은 원소들이 x의 후보로 있을 때,

1, 3, 7, 8

1 == 1	true
3 == 1	false
7 == 1	false
8 == 1	false

참인 경우가 존재하므로,

∃xP(x) 는 참이다.

 

존재명제의 경우 논리 그대로 코드 작성이 가능하여, 전칭명제보다 훨씬 직관적이다.

int Exists(vector<int> elements)
{
    for (int x : elements)
    {
        if (x == 1)
            return true;
    }
    return false;
}

 

 

실제 사용 예제

한정명제가 실제 알고리즘에서 어떤 형태로 나타나는지 예제를 통해 확인해보자.

 

소수 판별 예제

어떤 숫자 N이 소수인지 판별하는 알고리즘도 한정명제를 이용하여 표현할 수 있다.

소수는 2부터 N-1의 모든 자연수로 나누어지지 않는 수를 의미한다.

 

P(x) = (N % x != 0) 이면 참, 아니면 거짓

(2 <= x < N)

∀xP(x) : 모든 x에 대해 N을 x로 나눈 나머지는 0이 아니다.

// 전칭명제
int IsPrime(int n)
{
    for (int i = 2; i < n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

 

 

문자열 찾기 예제

문자열 S에 문자열 T가 있는지 찾는 예제를 생각해보자.

이 알고리즘은 결국 어떤 특정 위치에서부터 T의 모든 문자들이 S의 모든 문자들과 매칭되는지 확인하여야한다.

또한 문자열이 있는지만 확인하면 되는 것이기 때문에, 이 T는 최소 한번만 나타나는지 확인하면 된다.

그러므로 이 알고리즘은 한정명제를 이용하여 다음과 같이 표현될 수 있다.

 

P(x, y) = (S[x + y] == T[y]) 이면 참, 아니면 거짓

(0 <= x < S.size())

(0 <= y < T.size())

 

∃x∀yP(x, y) : 모든 y에 대해 (S[x + y] == T[y])인 어떤 x가 존재한다.

 

x가 1인 경우, 모든 y [0, 1, 2, 3]에 대해 성립한다.

i : 0 1 2 3 4 5 6
S : b t t a s a a

i : 0 1 2 3
T : t t a s

// 전칭명제
bool Match(const string& s, const string& t, int x)
{
    if (x + t.size() > s.size())
        return false;

    for (int y = 0; y < t.size(); ++y)
    {
        if (t[y] != s[x + y])
            return false;
    }
    return true;
}

// 존재명제
bool FindString(const string& s, const string& t)
{
    for (int x = 0; x < s.size(); ++x)
    {
        if (Match(s, t, x))
            return true;
    }
    return false;
}

 

 

정사각형 찾기 예제

2차원 배열이 주어졌을 때, 이 배열에서 2 x 2 정사각형이 있는지 판별하는 알고리즘을 생각해보자.

다음과 같이 배열이 주어지면 왼쪽 윗 부분에 2 x 2 정사각형이 존재한다.

반면 오른쪽 아래에는 한 칸이 0이기 때문에 정사각형이 아니다.

1 1 0 0 0
1 1 0 0 0
1 0 0 1 0
0 1 0 0 1
0 0 0 1 1

이 알고리즘은 전체 배열에서 최소 하나의 정사각형만 존재하면 된다.

그러므로 존재명제를 이용하면 된다.

그리고 정사각형임을 확인하기 위해서 특정 위치부터 2 x 2 만큼의 모든 원소값이 1이어야 하므로,

원소값에 대한 전칭명제를 이용하면 된다.

 

그러므로 대략 다음과 같이 표현될 것이다.

x : 탐색시작 위치 (i, j)

y : 정사각형 표현 위치 (i, j)

P(x, y) : 2차원 배열의 x + y 위치가 1이면 참, 아니면 거짓

∃x∀yP(x, y) : 모든 y에 대해 배열의 x + y 위치가 1인, 어떤 x가 존재한다.

 

#include <iostream>
#include <vector>

using namespace std;

struct Pos
{
    Pos(int i, int j) : i(i), j(j) {}
    int i, j;
};

// 전칭명제
bool CheckRect(int board[5][5], Pos x)
{
    vector<Pos> v = { Pos(0, 0), Pos(0, 1), Pos(1, 0), Pos(1, 1) };

    for (Pos y : v)
    {
        int i = x.i + y.i;
        int j = x.j + y.j;

        if (board[i][j] != 1)
            return false;
    }
    return true;
}

// 존재명제
bool CheckRectExists(int board[5][5])
{
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 5; ++j)
            if (CheckRect(board, Pos(i, j)))
                return true;
    return false;
}

int main()
{
    int board[5][5] =
    {
        1, 1, 0, 0, 0,
        1, 1, 0, 0, 0,
        1, 0, 0, 1, 0,
        0, 1, 0, 0, 1,
        0, 0, 0, 1, 1,
    };

    cout << CheckRectExists(board);
    return 0;
}

 

순열 & 조합 예제

순열과 조합을 사용하는 경우에도 한정명제는 자주 이용된다.

ex)
생성된 모든 조합들 중, 적어도 하나의 조합에 대해,
원소의 모든 값이 같은 경우가 존재한다.

생성된 모든 순열들 중, 적어도 하나의 순열에 대해,
원소의 값 중 적어도 하나가 같은 경우가 존재한다.