_4_ 브루트포스 알고리즘

MJ Studio
알고리즘은 미친짓이다
7 min readApr 19, 2022

첫 알고리즘! 브루트포스 알고리즘에 대해서 다루어봅니다.

문제의 제한과 접근

알고리즘엔 정말 많은 종류들이 있습니다.

예를 들어, 우리가 값이 변화하지 않는 숫자들의 배열의 특정 구간 (L ≤ i ≤ R) 에서의 최대값을 찾고싶다고 해봅시다. 배열의 길이는 N입니다.

가장 쉬운방법부터 생각해봅시다. 단순히 [L, R] 구간의 모든 숫자들을 한 번씩 보면서 그 중 최대값을 찾으면 됩니다. 이 방법은 시간복잡도가 O(N) 입니다.

이제 문제가 Q(보통 쿼리, query 라고 하기 때문에 Q라는 변수명을 많이 씁니다.)번의 구간들에 대해서 최대값을 찾으라고 묻는다면 시간복잡도는 O(QN)이 될 것입니다.

우리가 좀 더 어려운 문제들을 푼다면 이걸 O(logN)이나 심지어 O(1)에 구해버리는 미친 알고리즘을 사용할 수도 있습니다. 하지만 먼저 문제의 입력 제한을 잘 살펴야 합니다.

[제한]

1 ≤ N ≤ 100, 1 ≤ Q ≤ 1000
시간 제한: 1s

만약 위와 같다고 한다면 이전 글에서 설명드렸듯이 들어올 수 있는 값중 가장 큰 값인 100과 1000으로 O(QN)을 토대로 삼아 Q*N을 해도 10만밖에 안됩니다.

10만이면 대략적인 언어에서 1초에 1억번의 연산을 한다고 가정하자고 했을 때 충분히 문제에서 요구하는 1초안에 연산이 되는 연산횟수입니다.

따라서 “아, 그냥 모든 입력에 대해 모든 값들을 하나하나 다 살펴봐도 문제를 풀 수 있겠구나!” 라고 판단할 수 있습니다.

브루트포스 알고리즘이란?

브루트포스 알고리즘이란 바로 이 “하나하나 다 살펴보는” 알고리즘을 통칭합니다.

특별한 구현방법이 정해져있는 것이 아니라 이런식으로 가능한 모든 경우를 살펴보고도 충분히 연산 횟수가 적을 때 사용할 수 있습니다.

그럼 충분히 연산 횟수가 적다는 것은 어떻게 알까요?

그래서 항상 중요하고 강조되는 것이 문제의 입력, 시간 제한을 파악하고 우리의 알고리즘의 시간복잡도를 판단하여 1억=1초 룰에 대입해보는 것입니다.

문제에서 확인해야 할 모든 경우가 100만번이라고 합시다. 그런데 한 경우에서 다른 한 경우를 검사하기 위해 넘어갈 때 쓰이는 연산이 대략 1,000 번이라면 어떻게될까요?

그럼 우리는 모든 경우를 검사하기위해 100만 * 1,000 = 10억이 걸리기 때문에 문제에서 요구하는 시간복잡도를 맞추지 못합니다.

다른 경우로 검사 자체에 1,000번의 연산이 걸리고 어떤 경우에서 다른 경우로 넘어갈 때 O(1)이 걸려도 시간 초과를 보게될 것입니다.

예시를 들어볼까요?

브루트포스 알고리즘은 어떤 특정 문제에서만 사용된다라고 할 수 없을 정도로 범용적입니다. 그냥 다 해봐도 시간복잡도가 입력에 비해 그리 크지않을 때 시도를 해볼 수 있는 알고리즘이기 때문입니다.

문제를 하나 가져와보겠습니다.

N개의 숫자 중 세 개를 골라 M에 최대한 카드 3장의 합을 구하는 문제입니다.

이 문제에서 M의 크기는 그렇게 중요하지 않습니다.

입력에는 문제의 시간복잡도를 결정하지 않는 입력도 당연히 존재한다는 것을 아셔야 합니다.

심지어 어떤 문제에서는 특정 수들의 값을 10⁹ 정도로 주기도 하는데, 이는 보통 문제의 알고리즘을 적절한 시간복잡도로 해결하는데 이 숫자의 크기는 중요하지 않다는 것을 의미합니다.

반대로 10³ 정도로 작게 준다면 뭔가 냄새가 나는데? 하고 킁킁거리면서 수가 작다는 특징을 이용한 문제풀이법도 염두해둘 수 있습니다.

어쨌든 이 문제는 N에서 숫자 세개를 골라서 모두 검사해보면 되는 문제이기 때문에 O(N³)에 해결이 되는 문제입니다.

서로 다른 3 장의 카드를 사용해야 하므로 정확히 말하면 N³ 번의 계산이 아닌 서로 다른 N개 중 3개의 원소를 순서에 상관없이 뽑는 조합의 개념으로 들어가지만 이전 글에서 설명했듯이 이 경우도 O(N³)이라고 표기합니다.

예시를 들어볼까요? — 순열

A 마을에 5명의 사람이 있고, B 마을에 5명의 사람이 있어서 각 마을에서 한 명씩 골라서 노래방 점수내기 대결을 5판 한다고 합시다.

그런데 각 마을의 사람들은 상대 마을의 각 사람들에게 서로 다른 호감도가 있어서 특정 사람과 하면 자신의 실력을 뽐낼 확률이 달라집니다.

A 마을의 촌장인 당신은 B 마을을 꼭 이기고 싶어서 B 마을의 1 ~ 5 번 사람에게 A 마을의 1 ~ 5 번 사람 중 원하는 순서대로 대결을 시킬 수 있습니다.

어떻게 순서를 짜서 대결을 시키는 것이 가장 효과적일까요?

일단 가능한 모든 대진표가 몇 가지인지 살펴봅시다.

<1 2 3 4 5> 라면 A마을의 1번이 B마을의 1번과 대결하고… 처럼 진행되는 것이라고 하겠습니다.

<1 2 3 4 5>, <1 2 3 5 4>, <1 2 4 3 5> … 처럼 쭉쭉 경우가 나오겠죠.

그리고 수학을 조금 기억하고 계신분들이라면 아시겠지만 가능한 경우는 모두 5!=120 가지입니다.

서로 다른 5명에게 순서를 할당하는 순열이기 때문입니다.

그러면 문제를 확장시켜 5명이 아닌 N명이라고 해보겠습니다.

A 마을의 어떤 사람과 B 마을의 어떤 사람 두 명이 맞붙을 때 A 마을이 이길 확률이 O(1)에 구해진다면 총 시간복잡도 O(N!)에 문제를 해결하게 되는 것일까요?

아닙니다. 두 가지 고려해야 할 것이 남았습니다.

우선, <1 2 3 4 5> 라는 경우에서 <1 2 3 5 4> 같은 경우로 이동하는 연산 횟수가 얼마나 드는지 확인해야 합니다.

보통 이는 Python의 itertools 나 C++의 next_permutation 같은 내장 함수를 이용한다면 O(1)에 해결되고 아니라면 재귀 함수를 직접 짜서 구현할 수도 있습니다.

안타깝게도 다른 언어들이 이걸 지원하는지 모르겠습니다. 하지만 순열을 직접 만드는 방법을 밑에서 설명하겠습니다.

(1, 2, 3, 4, 5)
(1, 2, 3, 5, 4)
...
(5, 4, 3, 2, 1)
120

그 다음은 순서를 정했으므로 모든 사람들을 매치시켜서 A 마을이 이길 확률의 총 합을 적절히 계산해야 합니다. 사람이 각 마을에 N명이니까 O(N)이 걸리겠죠.

그래서 종합적으로 판단했을 때 O(N * N!) 정도의 시간복잡도가 우리의 알고리즘에 쓰이게 될 것입니다.

따라서 N이 11만 되어도 연산량은 1억을 훌쩍 넘어 매우 느린 알고리즘이 되버립니다.

하지만 문제의 제한에서 N이 8정도라면 부담없이 사용할 수 있는 방법입니다.

강조드렸듯이 시간복잡도를 계산하고 문제에서 요구하는 알고리즘을 파악하는 것이 중요합니다.

순열을 직접 구현하는 법(Optional)

대부분의 브루트포스 문제에서 순열이 나오는 경우는 드물지만 중요하다고 생각되어 좀 더 다루어봅니다.

저희가 아직 배우지 않은 재귀함수를 이용해 구현할 수 있습니다.

잠시 자바 코드를 투척합니다. 그리 중요한 내용이 아니니 필요한 분들만 보셔도 됩니다.

order 라는 인자를 넘겨 순서의 배열을 채워가며 현재 몇 번째 인덱스에 있는지를 판단하고, 0부터 N — 1 까지 모든 수들을 순회하며 used 로 관리되는 숫자들 중 사용되지 않은 숫자를 사용합니다. 더 자세한 내용은 여기로 넘깁니다.

추천 문제

9명의 난쟁이 중 7명을 골라서 합이 100인지를 검사해볼 수 있습니다.

이처럼 브루트포스알고리즘은 가끔 X개중에 Y개를 뭐 어떻게 해서 찾는 순열과 조합같은 느낌이 나는 문제도 많습니다. 하지만 우린 이걸 조합론이라고 부르진 않죠.

블랙잭 문제와 비슷한 문제입니다.

N이 20밖에 안되므로 O(N²)에 모든 구간을 검사하고 그 구간안에 있는 수들을 O(N)에 모두 더한 값을 S와 비교해야 하므로 총 시간복잡도는 O(N³)가 됩니다.

문제 이름부터 “모든 순열” 입니다.

N이 8밖에 안된다면…?

--

--