브루트 포스 (Brute Force)

 Brute-Force Attack은 우리말로 무차별 대입 공격이란 뜻이다. 이 말은 정말 무차별적으로 모든 방법을 시도하는 것을 뜻한다. Brute-Force 알고리즘도 비슷하다.

 예를 들어 자물쇠 0~99까지 가능하다면 0부터 99까지 모든 경우의 수를 시도하는 것이다. 힘들긴 하겠지만 시간만 있다면 가능한 것이다. 브루트 포스는 말 그대로 가장 순진한 알고리즘 접근법이다. 가능한 모든 조합을 찾아서 계산하면 되는 것이다.

 

 브루트 포스 알고리즘은 모든 경우의 수를 봐서 확실한 답을 구한다는 장점이 있지만 알고리즘 자체는 비효율적이다. 특히, input이 클수록 더 비효율적이라는 생각이 들것이다. 

 

 브루트 포스는 직관적이고 명확하고 답을 확실하게 찾을 수 있다는 장점이 있다. 그래서 효율적인 알고리즘의 첫 시작은 브루트 포스이기때문에 알고리즘을 배울 필요가 있는 것이다.

 

아래에 있는 브루트 포스 알고리즘의 예시를 보자.

 

[문제 설명]

카드 두 뭉치가 있습니다.

왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶은데요. 어떻게 하면 가장 큰 곱을 구할 수 있을까요?

 

함수 max_product는 리스트 left_cards와 리스트 right_cards를 파라미터로 받습니다.

left_cards는 왼쪽 카드 뭉치의 숫자들, right_cards는 오른쪽 카드 뭉치 숫자들이 담겨 있고, max_product는 left_cards에서 카드 하나와 right_cards에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴합니다.

 

def max_product(left_cards, right_cards):
	print(max_product([1, 6, 5], [4, 2, 3]))
	print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
	print(max_product([-1, -7, 3], [-4, 3, 6])) 

[풀이과정]

 브루트 포스 방법으로 for문을 2개 사용하여 풀면 된다. 처음에 max를 사용하여 left_cards 와 right_cards에서 하나씩 최대값을 뽑아서 곱했는데 그러면 음수와 음수의 곱이 최대가 될 경우를 생각못할 수 있다. 

그래서 일일이 다 구해서 최대값을 구하면 된다.

[해답]

def max_product(left_cards, right_cards):
    bigg=0
    for left_card in left_cards:
        for right_card in right_cards:
            wow = left_card*right_card
            if wow>bigg:
                bigg=wow
    return bigg
# 테스트
print(max_product([1, 6, 5], [4, 2, 3]))
print(max_product([1, -9, 3, 4], [2, 8, 3, 1]))
print(max_product([-1, -7, 3], [-4, 3, 6]))

 

#Tip#

3중 반복문에서 3번째 반복문을 실행 후 2번째 반복문을 다시 실행하는 과정을 재귀로 구현한 코드에서 현재 실행 중인 함수를 호출한 곳으로 돌아가는 과정으로 비유하면 백트래킹 기법을 적용했다고 한다. 백트래킹을 브루트 포스를 수행하는 방법 중 하나로 본다.