📌 알고리즘 패러다임
자주 나타나는 알고리즘 접근법들을 묶어서 알고리즘 패러다임이라고 부른다.
📌 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)이다.
