BruteForce 알고리즘

우리가 알고리즘 문제를 만났을 때, 가장 먼저 해보아야 할 방식이 Brute force 접근 방식이다.

Brute = 무식한 , Force = 힘 으로, 무식하게 접근하는 알고리즘 문제 접근 방법이다.

 

해가 존재할 것이라 기대되는 영역의 처음부터 끝까지를 조사하는 방식으로, 알고리즘 설계 방식에서

가장 기초적인 방식이라 할 수 있다.

원하는 답을 설계시 영역을 잘 설정했다면 100% 얻어낼 수 있는 방식이지만 input이 매우 큰 경우에도 과연 그럴까?

 

이 알고리즘은 답을 찾을 확률이 상대적으로 높으나 반드시 찾을 수 있는 것은 아니다. 

input의 값이 매우 크거나 컴퓨터 성능이 좋지않다거나해서 모든 범위를 탐색하는 것이 유의미한 시간 범위를 넘어가는

순간에 답을 찾는 것이 의미가 없어지는 상황이 발생할 수 있다.

 

그러나... 위에서도 말했듯이 모든 알고리즘 문제해결 접근 방식에서 가장 처음 떠올려야 하고 설계시 가장 먼저 고려해야하는 방식이기에 반드시 알아두어야 할 접근 방식이다.

 

예시 1 - 두 카드 숫자의 곱 최댓값 찾기

왼쪽 카드뭉치와 오른쪽 카드뭉치가 있다고 해보자.

이 카드에는 정수가 올 수 있다. 이때 두 카드뭉치의 숫자의 곱중 최댓값을 구하려면 어떻게 접근해야할까?

당연히 가장 첫 접근 방식은 왼쪽의 카드 하나와 오른쪽 카드 하나를 일일이 모두 곱해서 값을 비교해보는 것이다.

 

def max_product(left_cards, right_cards):
    
    ans = []
    for i in range(len(left_cards)):
        for j in range(len(right_cards)):
            ans.append(left_cards[i]*right_cards[j])
    return max(ans)

 

예시 2 - 약수 찾기

리스트가 주어질 때, 그 리스트의 자료 중에서 원하는 자료의 약수가 될 수 있는 값만 찾아보고 싶다.

이럴 때도 가장 처음 접근할 수 있는 방법은 10을 모든 자료들로 한 번씩 나누어 보는 것이다.

def divisor(list_,n):
    container = []
    for i in range(len(list_)):
        if n % list_[i] == 0:
            container.append(list_[i])
        
    return container

 

예시 3 - 지불 경우의 수 구하기

예를들어 지불하는 화폐의 종류가 50원짜리와 10원짜리가 있다고 해보자.

이때 경우의 수를 구하려면 10원짜리모두 지불하는 경우부터 50원짜리 2개와 10원짜리 2개를 지불하는 경우까지 모두 확인해 보아야 한다.

 

def paymoney(n):
    change = n
    i = 0
    j = 0
    way = 0
    for i in range((n//50)+1):
        for j in range((n//10)+1):
            if (i*50) + (j*10) == change:
                way += 1
    return way