[자료구조] 6. Brute Force 이해하기(feat. codestates, self tutorial)

 

 

 

 

 

안녕하십니까 다제입니다. 

 

오늘은 Brute Force에 대해서 알아보도록 하겠습니다. 

 

Brute Force는 해킹쪽에서 Brute Force attack이라는 용어로 더 많이 알려진 단어입니다. 

 

실제로도 Brute Force를 검색해보니 온통 Brute Force attack에 대한 이야기만 하고 있더라고요

 

Brute Force attack은 무차별적으로 마구마구 공격을 한다라는 뜻입니다. 

 

공격이라는 의미만 뺀다면 알고리즘 측면에서 무차별적으로 생각없이 모든 경우의 수를 다 시도해본다고 생각하시면 됩니다. 

 

오늘은 이 Brute Force를 왜 사용하고 어떻게 사용하는지를 간단하게 다루어보도록 하겠습니다. 

 

 

 

---

 

 

 

1. Brute Force 정의 

무차별적으로 가능한 모든 경우의 수를 시도하는 가장 순진한 알고리즘 접근법

 

 

---

 

 

2. 왜 이게 사용할까요?

딥러닝과 머신러닝에서 기준모델이라는 것을 세웠던 기억이 있으실 겁니다. 

알고리즘에서 기준모델이 바로 Brute Force입니다. 이에, 효율적인 알고리즘을 찾을 때 대부분 Brute Force를 이용합니다.  

 

 

---

 

 

3. 장점

-. 직관적이고 명확합니다. 

-. 모든 경우의 수를 따지기 때문에 답을 확실하게 찾을 수 있습니다. 

 

 

---

 

 

4. 단점

-. input data가 크면 비효율적이다는 단점이 있습니다.  

-. 모든 경우의 수를 다 살펴보는 방법이기 때문에 결코 효율적인 방법은 아닙니다.

 

 

---

 

 

5. 예제코드 

여러 매장들 중에서 가장 가까운 매장을 찾는 함수를 구현해 보았습니다.

리턴은 여러 매장들 중 가장 가까운 매장의 위치 a,b를 리턴해줍니다. 살펴보시고 궁금하신 사항은 댓글 부탁드립니다. 

# 가까운 매장 찾기

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

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

# 가장 가까운 두 매장을 찾아주는 함수
def closest_pair(coordinates):
    
    for a in test_coordinates:
        for b in test_coordinates[1:]:
            min_value = 0
            best_min_value = between_distance(a, b)
            if best_min_value > min_value:
                best_min_value = min_value
        return a, b                
            
# 테스트
test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(test_coordinates))

 

# 두개의 리스트 중 하나씩 뽑아 가장 높은 숫자를 출력하는 함수
def max_product(left_cards, right_cards):

    temp_list = []
    for a in left_cards:
        for b in right_cards:
            if a and b > 0:
                temp_list.append(a*b)
            elif a and b < 0:
                temp_list.append(a*b)
    result = max(temp_list)
    return result
# # 테스트
print(max_product([1, 9, 5], [4, 3, 3]))
print(max_product([1, -9, 8, 4], [2, 8, 3, 4]))
print(max_product([-1, -7, 3], [-4, 3, 7]))

결과값 : 36, 64, 28

 

오늘은 Brute Force에 대해서 간단하게 살펴보았습니다. 

 

간단한 개념이니 쉽게 이해하실 수 있으실거라 생각합니다. 

 

궁금하신 사항은 언제든 댓글 부탁드리며, 오늘도 도움이 되셨다면 공감 부탁드립니다. 

 

방문해주셔서 감사드립니다.