[알고리즘] Brute Force

무차별 대입을 뜻하며 Attack을 붙이면 해킹 기법 중 하나인 무차별 대입 공격이 된다.

 

간단한 예시)

 

숫자카드가 왼쪽에 n장, 오른쪽에 n장이 있다. 

두 수를 곱해서 가장 큰 수를 도출해 내고 싶을 때 이 brute force를 이용하면 된다.

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


# 테스트
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]))

brute force는 직관적이고 명확하다. 또한 답을 확실하게 찾을 수 있는 장점이 있다.

하지만 인풋이 엄청 커질 경우에는 효율성이 떨어진다.

 

간단한 예시 2)

 

두 좌표간의 최소거리를 갖는 두 좌표를 출력하는 프로그램을 만들고 싶다.

두 좌표는 서로 최소거리를 구하는 공식을 사용하여 거리를 구하고 다음에 비교했을 때 값이 작으면 그 값을 가지고 가는 형식으로 코딩해보았다.

 

# 제곱근 사용을 위한 sqrt 함수
from math import sqrt

# 두 매장의 직선 거리를 계산해 주는 함수
def distance(store1, store2):
    return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)

# 가장 가까운 두 매장을 찾아주는 함수


def closest_pair(coordinates):
    comparing_target = distance(coordinates[0], coordinates[1])
    comparing_pair = [coordinates[0], coordinates[1]]
    for i in coordinates:
        for j in coordinates:
            distance(i, j)
            if distance(i, j) < comparing_target and distance(i, j) != 0:
                comparing_target = distance(i, j)
                comparing_pair = [i, j]

    return comparing_pair

# 테스트

test_coordinates = [(12, 30), (40, 50), (5, 1), (2, 3), (12, 10), (3, 4)]
print(closest_pair(test_coordinates))