Prologue

이번 스터디 그룹 모임의 주제는 "Brute Force Algorithm".

Python 언어를 이용해 [Baekjoon Online Judge] 사이트에 있는 브루트 포스 알고리즘 문제 5개를 풀고 함께 리뷰해 보는 시간을 가졌다.

이를 통해 브루트 포스 알고리즘이란 무엇인지, 왜 필요한지 새삼 깨닫게 되는 시간이 되었다.

브루트 포스 알고리즘의 정의

무식?

(컴퓨터) 억지 기법 ((무차별 대입해 억지로 문제를 푸는))
출처: 네이버 영어사전 "brute force"

처음 "브루트 포스"를 접했을 때는 이걸 알고리즘이라고 할 수 있나 싶었다.

단어를 검색했을 때 나오는 여러 블로그 글이나 네이버 영어사전에서조차 일종의 "억지"라고 소개하고 있었기 때문이다.

"알고리즘(Algorithm)"이라는 것은 원하는 출력을 유도하는 규칙이라고들 한다. 그런데 브루트 포스가 무지성으로 값을 대입해 보고 답을 찾아내는 것이라면 알고리즘이라 부를만한 규칙이 없는 것 아닌가 싶었다.

하지만 아니었다.

유식!

문제를 풀고 고민하고 사람들과 의견을 나눌수록 알게 됐다.

부루트 포스 알고리즘 (Brute Force Algorithm)이란,
가능한 모든 경우의 수를 찾아내는 규칙에 맞게 대입하여 답을 찾아내는 절차라고 표현하는 것이 타당하다.

세상 모든 것을 대입해 볼 수는 없으니 "가능한 모든 경우의 수"라는 범위로 좁혀나가는 여러 고민과 노력이 필요하기 때문이다.

문제 풀이

2798번 문제: 블랙잭 [문제 링크]

문제 요약

블랙잭은 제시된 카드덱에서 3장의 카드를 뽑아 그 합이 목표 숫자 이하이면서 가능한 가장 높은 수가 나올 때까지 계속 조합의 합을 구해야 한다.

풀이 요약

모든 카드 3장의 조합을 만들기 위해서는 for문을 세 번이나 중첩시켜야 하는데, itertools라는 고마운 모듈을 알게 되어 단 한 번의 for문에 combinations함수를 활용하여 모든 경우의 수를 간단하게 만들 수 있었다.

그렇게 만든 조합들 중 목표 점수 m 이하의 가장 큰 수를 찾아 return해준다.

2231번 문제: 분해합 [문제 링크]

문제 요약

분해합 공식: 어떤 수 $X$ + 어떤 수 $X$의 각 자릿수의 합 = $N$
[예시] $245 + 2 + 4 + 5 = 256$

위와 같은 식이 성립할 때, 임의의 자연수 $N$이 주어지면 $X$를 구해야 한다.

풀이 요약

$N$이 될 때까지 $1$부터 차례대로 분해합 공식에 대입해보고 $N$이 되는 순간에 대입한 숫자$X$를 return한다.

7568번 문제: 덩치 [문제 링크]

문제 요약

한 사람이 다른 사람보다 키도 크고, 동시에 몸무게도 더 많이 나가면 덩치가 크다고 한다.
단, 키만 크고 몸무게는 적거나 몸무게만 많이 나가고 키는 작은 경우는 우열을 가릴 수 없다고 한다.
$N$명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 즉, 자신보다 더 큰 덩치의 사람이 $k$명이라면 그 사람의 덩치 등수는 $k+1$이 된다.
$N$명의 몸무게와 키 수치가 있는 리스트가 주어진다. 이 $N$명의 집단에서 각 사람의 덩치 등수를 구해야 한다.

풀이 요약

주어진 리스트를 '덩치 리스트'라고 할 때, 덩치 리스트의 각 index에는 각 사람의 몸무게와 키 수치를 담은 list가 있으므로, 각 index번호를 그 사람의 번호라고 가정한다.

$1$이 $N$개인 리스트를 생성하고 '등수 리스트'라고 하고, 이 리스트의 각 index는 해당 번호의 사람 등수라고 가정한다.

모든 사람들의 덩치를 각각 비교하고, 그때마다 덩치가 작은 사람에게는 '등수 리스트'의 그 사람 번호에 대응하는 index의 값을 $1$ 더 해준다.

비교를 마치면 등수 리스트 안의 값이 곧 각 사람의 등수가 된다.

1018번 문제: 체스판 다시 칠하기 [문제 링크]

문제 요약

$N$과 $M$은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다.
높이가 $N$, 폭이 $M$인 보드가 있고, 보드는 $1 \times 1$ 사이즈의 검은색과, 흰색 타일들이 불규칙하게 배열되어 있다고 한다.
$8 \times 8$ 크기로 잘라 체스판을 만들려고 하면 흰색과 검은색 타일이 불규칙하여 색을 다시 칠해야 한다.
색을 다시 칠해야 하는 타일의 최소 개수를 구해야 한다.

풀이 요약

보드 가장 모서리의 위치를 $(0, 0)$ 좌표라고 가정한다.
보드 안에서 $8 \times 8$을 만들 수 있는 모든 좌푯값을 구한다.
각 좌표에서 검은색으로 시작하는 체스판을 만들 때와 흰색으로 시작하는 체스판을 만들 때 다시 칠해야 하는 타일 개수를 구한다.
이렇게 구한 타일 개수 중 가장 최솟값을 return한다.

1436번 문제: 영화감독 숌 [문제 링크]

문제 요약

괴짜 영화감독 숌이 자신이 만드는 모든 영화의 제목에 "666"을 넣을 생각이다.
발표하는 영화에 순서대로 "666, 1666, 2666, 3666, ..." 이런 식으로 제목을 짓는다고 한다.
187번째 영화 제목은 "66666"이고 500번째 영화 제목은 "166699"이다.
자연수 $N$이 주어지면 숌 감독의 $N$ 영화 제목을 구해야 한다.

풀이 요약

영화 제목에는 항상 숫자 "666"이 들어가고 첫 번째 영화 제목이 "666"이고 두 번째는 "1666"이다.
이는 1부터 숫자를 차례대로 세면 가장 먼저 만나는 "666"을 포함하는 숫자가 "666"인 것이고.
두 번째로 만나는 "666"을 포함하는 숫자가 "1666"인 것이다.

즉, "$1, 2, 3, ..., 665, [666], 667, ...$" 이렇게 처음 나온 "666"이 첫 영화 제목.$666, 667, 668, ... 1665, [1666]$ 이렇게 나온 두 번째 "666"을 포함하는 숫자 "1666"이 두 번째 영화 제목인 것이다.

그러므로, 숫자 666부터 순서대로 숫자를 세면서 해당 숫자 안에 숫자 666이 있는지 확인하고 있을 때마다 $n$의 숫자를 $+1$ 해준다. $n = N$이 되는 차례의 숫자가 $N$번째 영화 제목이 된다.

결론

브루트 포스 알고리즘이 가장 효율적인 방법일 때가 있다.

지난 글에서는 효율적인 문제 해결을 위해 사용하는 것들을 효율이 목적이 아닌 사용 그 자체에 목적을 두어 비효율적이 되지 말자고 다짐했었다.

브루트 포스 알고리즘을 공부하면서 같은 맥락의 느낌을 받았다.

때로는 하나씩 다 대입해 보는 브루트 포스 알고리즘이 가장 효율적인 방법일 때가 있다.

보다 효율적인 방법을 찾는 노력을 비하할 수는 없다. 하지만 그것 역시 효율이 목적이어야 할 것이다. 하나씩 해봐야 하면 하나씩 해보면 된다. 다른 방법을 찾느라 효율이 떨어지면 안 되겠다.

네이버 영어사전에서는 브루트 포스를 억지 기법이라고 표현했지만, 그래야만 하는 때에 다른 방법을 찾느라 시간과 노력을 쏟는 것이야말로 억지일 수 있다.

Epilogue (TMI)

그동안 버블 정렬 알고리즘, 재귀 알고리즘 등등 여러 기본적인 알고리즘 들을 공부해 봤다.

그리고 이것들은 일정 규칙을 따라 값을 구해주는 것들이었다.

그래서 처음 브루트 포스 알고리즘을 검색해 보고 마치 규칙 없이 무작위로 대입해서 결과를 찾는 것이라고 설명을 보고 알고리즘이라고 하기 수준 미달이라고 생각했다.

앞서 언급했듯 브루트 포스 알고리즘은 "가능한 모든 경우의 수"라는 범위로 좁히는 고민과 노력이 필요하다. 그리고 대입한 값이 원하는 값과 일치하는지 확인할 수 있는 규칙도 필요하다.

검색해서 나온 말들은 그저 "신체적인 힘에만 의존하는"이라는 뜻의 형용사 brute가 포함되었다는 이유와 모든 경우의 수를 대입해 본다는 말의 어감에서 비롯한 잘못된 개념이라는 생각이 들었다.

다른 알고리즘의 비해 덜 효율적이고 비교적 많은 양의 연산을 필요로 하는 방법이지만, 그런 방법 외에 달리 선택지가 없는 때에만 사용한다면 가장 효율적인 알고리즘일 테니까.

앞서 풀어본 분해합 문제를 풀 수 있는 다른 수학 공식을 나는 모른다. 결국 주어진 공식에 하나씩 대입해 보는 수밖에 없다. 물론 몇 자릿수인지에 따라 시작 값을 다르게 하여 범위를 좁힐 수는 있겠지만 결국 그 근처에서 하나씩 숫자를 대입해 봐야 한다는 점을 변함이 없다.
블랙잭과 덩치, 체스판 문제들 역시 직접 하나씩 경우의 수를 대입해 본 결과들을 비교하지 않고 답을 구할 수 없다.

영화감독 숌 문제도 얼핏 수열 문제 같지만, 등차도 등비도 계차도 아니다. 사람이야 직관적으로 다음에 나올 666이 포함된 숫자를 바로 생각해낼 수 있지만 컴퓨터에게는 어떻게 명령을 내려야 할지 나는 모르겠다. 사실, 그냥 컴퓨터에게 1씩 세라고 해도 직관적으로 다음 숫자를 유추해 내는 나보다 컴퓨터가 빠르니까 그럴 필요도 없다.

즉, 브루트 포스 방식이 적어도 나에게, 그리고 이 문제들에서는 가장 효율적인 방법이었던 것이다.