안녕하세요, 계략입니다.

---

지난 번 알고리즘에 대해서 간략하게 설명을 해 봤습니다.
대부분 잘 읽어주셨다니 다행입니다 :)
분량이 짧다고 하시는 분도 계셨습니다. 아무래도 한 알고리즘에 대해 다루는 글이 아니라 짧게 쓰였던 것 같네요.

• 알고리즘에 대해서 간략하게만 다루는 게시글입니다.
• 비전공자들도 쉽게 이해할 수 있도록 작성해 보았습니다.
• 틀린 내용이 있으면 지적해주시면 감사하겠습니다. 틀린 내용에 대해서는 책임지지 않습니다.

그러면, 잘 부탁드리겠습니다!

---

저번 시간에 다뤘던 내용은,

'알고리즘' 이란?

이었습니다.
https://steemit.com/kr/@gyeryak/1

알고리즘에 대해서 다루기 전에, 알고리즘이 무엇인지에 대해 다뤄 보았죠.

• 알고리즘은 '문제를 해결하기 위해 사용하는 방식'이다.
• 같은 문제라도 여러가지 알고리즘이 존재할 수 있다.
• 알고리즘을 생각할 때는 효율도 같이 생각해야 한다.
  라고 요약을 할 수 있었습니다.

이번 시간에는 가장 간단한, 다시 말하다면 단순무식한 알고리즘을 다뤄 볼 예정입니다.
앞서 나왔던 '효율'의 측면에서 설명하자면,

• 구현 난이도: 문제에 따라 다르지만 대부분 쉬운 편
• 작동 시간: 거의 모든 문제에서 매우 김
• 메모리 사용량: 대부분의 문제에서 매우 큼

이라는 상당히 떨어지는 효율을 가지고 있습니다.

그런데도 왜 이런 알고리즘을 사용하는지, 디테일한 단점은 무엇이 있는지 등에 대해서 더 자세하게 알아봅시다.

---

이번 시간에 다룰 내용은,

브루트 포스(Brute Force)

입니다.

Brute: 짐승, 동물
Force: 힘
이름에서 느껴지듯, 매우 단순무식한 알고리즘입니다.

문제를 해결하기 위해서,
가능한 모든 경우에 대해 모두 직접 해 보는 방법입니다.

지난 시간의 예시를 가져 와 볼게요.

'1부터 100까지의 합을 구하라'

이 문제에 대해서

1부터 100까지 모두 직접 더한다

와 같은 풀이가 브루트 포스의 예시가 되는 것입니다.

그림에서 볼 수 있듯, 만드는 방법은 매우 간단할 것입니다.
1부터 100까지 차례대로 더해 나가면서 값을 바꾸면 되죠.
그리고, 컴퓨터는 사람들보다는 계산이 빠를 테고, 100까지 다 더하는 데는 시간도 얼마 안 걸릴 것입니다.

하지만, 브루트 포스의 문제점은 숫자가 커지면서 발생합니다.
만약 1부터 100까지가 아닌, 1부터 1000억까지 더한다고 해 봅시다.

숫자 하나를 더하면서 1번의 연산을 하는데, 1000억까지 다 일일이 더해준다면 1000억 번 계산을 하게 되겠죠.

일반적으로 컴퓨터는 1초에 약 1억 번의 연산이 가능합니다.

물론 컴퓨터마다, 프로그래밍 언어마다, 주어진 상황마다 크게 달라질 것입니다.
그래도 앞으로는 1초에 1억 번 연산이라고 가정하고 설명하겠습니다.

그렇다면, 저 문제를 브루트 포스로 해결한다면
1000초 = 약 17분이나 걸리게 됩니다.
단순 더하기 문제인데 말이죠.

브루트 포스를 뉴스 기사 같은 곳에서 접하신 분들도 있으실 겁니다.
*** 사이트, 브루트 포스 공격에 비밀번호 유출되어 같은 기사 말이죠.
그렇다면, 저 사이트가 얼마나 문제가 심각한 것인지 알아봅시다.

브루트 포스로 비밀번호를 알아낸다고 해 봅시다.
지금은 특수문자도 의무적으로 입력하는 사이트도 많지만, 소문자+숫자만 입력이 가능하다고 해 봅시다.
그러면 소문자 26글자(a~z)에 숫자 10글자(0~9) 해서 총 36글자가 될 것입니다.

만약에 암호가 1글자로 되어 있을 경우, 36번만 입력해 보면 되겠죠.
문제는 암호가 2글자가 넘어갈 경우입니다.

2가지가 넘어가면 약간 복잡해집니다.
앞의 글자가 되는 경우의 수가 36가지가 있고, 각각의 경우마다 뒤 글자가 나오는 경우가 36가지가 됩니다.

문자까지 들어가서 복잡하게 생각하실 수 있으니 단순하게 숫자(0~9)만 사용하는 것을 생각해 봅시다.
1자리의 경우는,
0,1,2,3,4,5,6,7,8,9
총 10가지가 되겠죠.

2자리가 되면
00,01,02,03,04,05,06,07,08,09,10,11,...,89,90,91,92,93,94,95,96,97,98,99
해서 총 100개가 나옵니다.
이 100이라는 수는 10*10을 해서 나온 숫자입니다.
3자리가 된다면? 1000개가 되겠죠.

다시 암호로 넘어간다면, 2자리가 됬을 때는 36*36 = 1296가지입니다.
3자리는 46656, 4자리는 1679616, 5자리는 60466176, 6자리는 2176782336.
이런 식으로 숫자가 기하급수적으로 커질 겁니다.

6자리의 경우는, 1초에 암호를 1억 번 확인한다고 했을 경우 22초 가량이 걸릴 것입니다.
6자리 비밀번호는 별다른 보안 장치가 없다면 22초만에 뚫리는 것이죠.
하지만 이런 문제점은 간단하게 막을 수 있습니다.

암호를 5번 틀리면 5분가량 암호를 입력할 수 없다고 해 보죠.
그러면 1분에 1개 꼴로 확인할 수 있는 셈이 됩니다.
이렇게 되면 6자리 암호를 뚫는 데 걸리는 시간은 69년이 됩니다.

저런 안전장치 하나만 있다면, 22초에서 69년이 되는 겁니다.
아마도, 브루트 포스에 해킹을 당한 사이트는 그런 안전장치가 없거나, 그 안전장치를 제거할 방법이 있었을 것입니다.

다시 브루트 포스 알고리즘의 얘기로 돌아와 봅시다.
암호의 예시에서 보았듯, 숫자(자릿수 등)이 커지면 대입해봐야 할 경우의 수가 매우 커집니다. 기하급수적으로요.
1초에 1억번 연산으로 6자리는 22초가 걸리지만, 10자리만 되어도 14개월이 걸립니다.
문제가 조금만 더 복잡해지면, 숫자가 조금 커질수록 엄청나게 많은 시간이 걸립니다.
그래서 브루트 포스 알고리즘은 시간 측면에서 매우 비효율적입니다.

하지만, 브루트 포스 알고리즘은 그만큼 만들기가 쉬운 편입니다.
모두 다 해보게 하면 되니깐요. (문제에 따라 어려운 경우도 있기는 합니다)

그것보다도 브루트 포스 알고리즘의 장점은 다른 데 있습니다.
다른 알고리즘을 생각하기에 앞서 도움이 됩니다.
가령, 브루트 포스 알고리즘으로 암호를 생각한다고 할 때,
몇몇 사전에 있는 단어나 iloveyou, password, 1234 등은 따로 해보도록 할 수 있겠죠.
이런식으로 조금 더 발전된 알고리즘을 생각하는 출발점이 됩니다.

---

정리
브루트 포스 알고리즘은 모든 경우를 직접 하는 알고리즘이다.
브루트 포스 알고리즘은 시간 면에서 매우 비효율적인 알고리즘이다.
다만 그만큼 만들기도 쉽고, 다른 알고리즘을 생각하는 출발점이 된다.

---

사실, 1부터 X까지 더하는 문제는 브루트 포스의 예시라고 보기 힘들긴 합니다.
다만 다 해본다는 측면에서 유사성이 있고, 쉬운 예시라서 넣었습니다.

보안 관련 기사에서 보셨을 법한 '브루트 포스' 알고리즘이었습니다.
읽기 불편하거나, 이해하기 어려운 점, 틀린 부분 등은 알려주시면 개선해보도록 하겠습니다.
읽어주셔서 감사합니다.

한 주의 주말이 다 끝나갑니다.
모두 행복한 새로운 한 주 되셨으면 합니다. :)