브루트 포스(Brute Force)
📌 알고리즘 패러다임
자주 나타나는 알고리즘 접근법들을 묶어서 알고리즘 패러다임
이라고 부른다.
📌 Brute Force 소개
Brute-Force Attack
무차별 대입 공격이라고 한다.
예를 들어 비밀번호가 0000부터 9999까지 가능한 자물쇠가 있다고 가정하자.
0000, 0001, 0002, ..., 9999까지 가능한 모든 경우의 수를 다 시도하는 방법으로 비밀번호를 찾을 수 있다.
브루트 포스
는 어떤 문제에 대해 가능한 모든 경우의 수를 시도하는 가장 순진한 알고리즘 접근법이다.
카드 뭉치 두 개가 있다. 왼쪽에서 카드 한 장, 오른쪽에서 카드 한 장을 뽑아서 두 수의 곱이 가장 크게 나오게 만들고 싶다. 어떻게 접근해야 할까 ❓
브루트 포스
방법으로 접근해보자.
브루트 포스는 가능한 모든 경우의 수를 확인한다.
가능한 모든 조합들어 곱을 계산해보면 6 x 4 = 24가 가장 크다.
✅ 카드 뭉치 최대 조합
문제
카드 두 뭉치가 있다.
왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶다. 어떻게 하면 가장 큰 곱을 구할 수 있을까?
함수 max_product
는 리스트 left_cards
와 리스트 right_cards
를 파라미터로 받는다.
left_cards
는 왼쪽 카드 뭉치의 숫자들, right_cards
는 오른쪽 카드 뭉치 숫자들이 담겨 있고, max_product
는 left_cards
에서 카드 하나와 right_cards
에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴한다.
💻 풀이
def max_product(left_cards, right_cards):
result = []
for i in left_cards:
for j in right_cards:
result.append(i * j)
return(max(result))
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]))
👉 출력
24
32
28
🧭 시간 복잡도
len(left_cards)을 m
, len(right_cards)을 n
이라고 하자.
함수 max_product에는 left_cards를 도는 반복문 안에 right_cards를 도는 반복문이 중첩되어 있으므로 max_product의 시간 복잡도는 O(mn)이다.
📌 Brute Force 평가
브루트 포스 알고리즘은 input이 클수록 비효율적이다.
📝 브루트 포스 의 장점
- 직관적이고 명확하다.
- 답을 확실하게 찾을 수 있다.
- input이 크지 않응면 Brute Force를 사용해도 된다.
✅ 가까운 매장 찾기
줄어든 매출 때문에 지점 하나를 닫아야 하는 위기에 처해 있다. 어떤 지점을 닫는 게 회사에 타격이 적을지 고민이다. 서로 가까이 붙어 있는 매장이 있으면, 그 중 하나는 없어져도 괜찮지 않을까 싶다.
사장님은 비서에게, 직선 거리가 가장 가까운 두 매장을 찾아서 보고하라는 임무를 주었다.
영업팀에서 매장들 좌표 위치를 튜플 리스트로 받아온다.
튜플은 각 매장의 위치를 x, y 좌표로 나타낸 것이다.
0번 매장은 (2, 3)에 그리고 1번 매장은(12, 30) 위치에 있다.
함수 closetst_pair
는 이 좌표 리스트를 파라미터로 받고, 리스트 안에서 가장 가까운 두 매장을 [(x1, y1), (x2, y2)]
형식으로 리턴한다.
두 좌표 사이 거리를 계산해주는 함수 distance
는 인풋으로 두 튜플을 받아서 그 사이의 직선 거리를 리턴한다.
💻 풀이
from math import sqrt
def distance(store1, store2):
return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)
def closest_pair(coordinates):
pair = [coordinates[0], coordinates[1]]
for i in range(len(coordinates)):
for j in range(i + 1, len(coordinates)):
if distance(pair[0], pair[1]) > distance(coordinates[i], coordinates[j]):
pair = [coordinates[i], coordinates[j]]
return pair
test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(test_coordinates))
🧭 시간 복잡도
인풋 리스트 coordinates의 길이를 n
이라고 하자.
함수 cloesest_pair에는 반복문 두 개가 중첩되어 있는데, 둘 다 반복 횟수가 n에 비례한다. 따라서 함수의 시간 복잡도는 O(n^2)이다.
✅ 강남역 폭우
강남역에 엄청난 폭우가 쏟아진다고 가정하자. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도이다.
그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶다. 그것을 계산해 주는 함수 trapping_rain
을 작성해 보려고 한다.
함수 trapping_rain은 건물 높이 정보를 보관하는 리스트 buildings
를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 준다.
예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 하자. 그러면 0번 인덱스에 높이 33의 건물이, 3번 인덱스에 높이 22의 건물이, 5번 인덱스에 높이 44의 건물이 있다는 뜻이다. 1번, 2번, 4번 인덱스에는 건물이 없다.
그러면 아래의 사진에 따라 총 1010 만큼의 빗물이 담길 수 있다. 따라서 trapping_rain 함수는 10을 리턴한다.
💻 풀이
def trapping_rain(buildings):
rain = 0
for i in range(1, len(buildings)-1):
left = max(buildings[:i])
right = max(buildings[i + 1:])
min_floor = min(left, right)
if min_floor - buildings[i] < 0:
rain += 0
else:
rain += min_floor - buildings[i]
return rain
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))
🧭 시간 복잡도
인풋 buildings의 길이를 n이라고 하자.
우선 for문의 반복 횟수는 n에 비례한다. 그리고 반복문 안에서 가장 오래 걸리는 부분은 max(buildings[:i])
혹은 max(buildings[i:])
이다. 둘 중 하나만 보자.
우선 buildings[:i]
는 최악의 경우 O(n)이다. 그리고 나서 슬라이싱된 리스트에 대해서 max 함수로 최댓값을 찾는 건데, 그것 또한 O(n)이다. O(2n)이니까 결국 O(n)이 된다.
for문의 반복 횟수는 n에 비례하고 for 반복문 안에서 가장 오래 걸리는 부분은 O(n)이기 때문에, trapping_rain
함수의 시간 복잡도는 O(n^2)이다.
Author And Source
이 문제에 관하여(브루트 포스(Brute Force)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@revudn46/Brute-Force저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)