우리 모두 나이가 어릴 때, 다음과 같은 생각을 해본 경험이 있을 것이다.
"이거 비밀번호 맞춰봐!"
"음... 그냥 0000부터 9999까지 다 눌러보면 되는거 아냐?"
무식하다.
정말 무식하지만...
반대로 정말 확실한 방법이다!
브루트 포스 (Brute Force)
바로 위에서 짤막하게 이야기한 비밀번호에 대한 이야기를 들었다면, 당신은 벌써 브루트포스 알고리즘에 대해 99%나 이해한 것과 마찬가지이다.
Brute(난폭한) + Force(힘, 폭력) 단어 조합으로 만들어진 이름의 이 알고리즘은,
정말 무식하게 무차별적으로 모든 값을 대입해보고 정답을 찾아내는 알고리즘이다.
이 알고리즘은 척 봤을 때, 누구나 치명적인 단점을 하나 생각할 수 있다.
바로, 매우 오래 걸리고 자원이 무지막지하게 든다는 점이다.
마치 수십만개의 데이터가 쌓인 DB에서 인덱스를 쓰지 않고, 정렬하지도 않은 채 원하는 값을 찾으려고 하는 것과 마찬가지다.
그러나, 이 알고리즘의 강점은 정말 확실하고 정확도를 100% 보장한다는 점에 있다.
바로 위에서 예시를 들은 0000~9999를 모두 눌러보는 작업도, 한 번 입력하는데 3초가 걸린다고 가정하면 3만초, 약 8~9시간이면 핸드폰을 뚫어버릴 수 있다는 것이다. 당연히 사람이 했다고 가정한 것이고, 만약 이 연산을 컴퓨터가 처리한다면 몇 초조차 걸리지 않을 것이다.
그리고 이 브루트포스는 정말로 해킹 기법 및 암호학에서 굉장히 자주 사용된다!
우선, 0000, 1111, 1234, 1a2b3c같은 사람들이 정말 많이 사용하는 패스워드를 우선 입력해본다. 이걸 사전 공격이라고 표현한다. 이후에 서술할 브루트포스 알고리즘 코드에서도 사전공격과 비슷한 형태가 나올 것이다.
사전공격이 끝났다면, 이제부턴 정말 무차별 대입으로 패스워드를 해킹하는 것이다.
다들 이런 화면을 봤던 경험이 있을 것이다.
네이버에서도 비밀번호 규칙에 8~16자 비밀번호에 영문 대소문자, 숫자, 특수문자를 사용하길 권고하고있다.
귀찮기만 했던 이 패스워드 규칙이 왜 존재하는지, 이제 여러분들 모두 알았을 것이다.
바로 브루트포스 해킹 때문이다!
영문 소문자 + 숫자의 조합만 해도 10자리를 넘게 되는 순간 36^10 이라는 경우의 수가 만들어지며,
이는 3,656,158,440,062,976 가지의 경우의 수가 생긴다는 것을 의미한다. 이렇게 될 경우 아무리 좋은 컴퓨터라고 해도 몇 달은 걸릴 수도 있다.
알고리즘 이론 설명에서 갑자기 해킹 기법과 암호학으로 이야기가 틀어져버렸는데...
사실은 저 이야기들만 알았다면 이제 브루트포스 알고리즘을 실제 코드에서 구현하는 것도 매우 간단하다.
알고리즘에서 브루트포스 알고리즘은 완전 탐색을 의미하기도 한다. 혹은 '고지식한 탐색' 이라는 이름으로 브루트포스 서치를 이야기하기도 한다.
브루트포스 서치를 할 땐 이진 탐색처럼 논리적인 탐색이 아닌, 맨 앞에서부터 끝까지 모두 탐색하는 것이 핵심이다.
이와 관련된 코딩 테스트 문제를 하나 준비했다.
1065번: 한수
어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나
www.acmicpc.net
1부터 1,000 이하의 정수 N까지 모든 정수들 중에서 등차수열을 이루는 정수가 몇 개인지 찾아보는 코딩 테스트이다.
당연히, 1 ~ N까지의 모든 정수를 for문으로 반복시킨 후 등차수열인지 확인하면 되겠다.
아래는 내가 간단하게 풀어본 코드이다.
# 1065. 한수 (실버 4)
# 알고리즘 분류 : 브루트포스
n = int(input())
if n < 100 : # n이 100보다 작다면 반드시 해당 숫자가 한수의 개수
print(n)
elif n == 1000 : # n이 1000이라면 반드시 한수의 개수는 144 고정
print(144)
else : # 사전 공격이 끝났으므로 111보다 큰 3자리 정수의 브루트포스 알고리즘 작동
ans = 99 # 우선 99개임을 기본으로 지정
for i in range(111, n + 1) : # 111부터 사용자가 입력한 정수까지 반복
num = []
for j in map(int, str(i)) : # 해당 숫자를 split으로 갈라 리스트에 추가
num.append(j)
if num[0] - num[1] == num[1] - num[2] : # 1번 ~ 3번의 자리가 등차수열이면, 한수
ans += 1
print(ans)
정수 n을 입력받는다.
이후, 1부터 99까지의 모든 정수는 전부 한수이므로 100 이하라면 그대로 n을 출력한다.
이 부분이, 위에서 말했던 사전 공격과 유사한 부분이다. (엄연히 말하면 당연히 다른거지만... 비슷한 맥락으로 이해하자)
이후 n이 1000일때만 별도로 처리해주고,
세자리수의 정수들에 대해선 1번과 2번 칸의 정수의 차와 2번과 3번 칸의 정수의 차를 비교해주면 되겠다.
두 정수의 차가 같다면 등차수열이며, 한수 되시겠다.
사실 브루트포스는 아무리 강력하다 하지만 결국 리소스 소모가 심하다는 치명적인 단점이 있는 알고리즘이다.
따라서, 논리적인 알고리즘을 만들어낸 뒤 동적 계획법(Dynamic Programming, DP)으로 많이 우회하는 편이다.
그럼에도 강력한 알고리즘인건 변함없으니, 반드시 숙지해두도록 하자.
다음 알고리즘 이론엔 탐욕법(그리디, Greedy) 알고리즘에 대해 얘기해보겠다.