[알고리즘] Brute Force : 카드 뭉치 최대 조합, 가까운 매장 찾기

Brute Force : 모든 경우의수 알고리즘 접근법(비효율적임)

장점 : 직관적이고 명확하다. 답을 확실하게 찾을 수 있다.(인풋값이 작다면 괜찮음)

 

실습설명

카드 두 뭉치가 있습니다.

왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶은데요. 어떻게 하면 가장 큰 곱을 구할 수 있을까요?

 

함수 max_product는 리스트 left_cards와 리스트 right_cards를파라미터로 받습니다.

left_cards는 왼쪽 카드 뭉치의 숫자들, right_cards는 오른쪽 카드 뭉치 숫자들이 담겨있고,

max_product는 left_cards에서 카드 하나와 right_cards에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴합니다.

 

문제

def max_product(left_cards, right_cards):
    # 여기에 코드를 작성하세요

# 테스트 코드
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

답안

def max_product(left_cards, right_cards):
    # 현재까지 최댓값을 담기 위한 변수
    # 처음에는 임시로 각 리스트의 첫 번째 요소의 곱으로 설정
    max_product = left_cards[0] * right_cards[0]
    
    # 가능한 모든 조합을 보기 위한 중첩 반복문
    for left in left_cards:
        for right in right_cards:
            # 현재까지의 최댓값 값과 지금 보고 있는 곱을 비교해서 더 큰 값을 최댓값 변수에 담아준다
            max_product = max(max_product, left * right)

    # 찾은 최댓값을 리턴한다            
    return max_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]))

 

 

실습설명

스타벅스는 줄어든 매출 때문에 지점 하나를 닫아야 하는 위기에 처해 있습니다. 어떤 지점을 닫는 게 회사에 타격이 적을지 고민이 되는데요. 서로 가까이 붙어 있는 매장이 있으면, 그중 하나는 없어져도 괜찮지 않을까 싶습니다.

 

사장님은 비서 태호에게, 직선거리가 가장 가까운 두매장을 찾아서 보고하라는 임무를 주셨습니다.

 

태호는 영업팀에서 매장들 좌표 위치를 튜플 리스트로 받아 왔습니다.

# 예시 tuple 리스트
test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]

튜플은 각 매장의 위치를 x,y 좌표로 나타낸 것입니다. 0번 매장은 (2,3)에 그리고 1번 매장은(12, 30)위치에 있는거죠. 

 

태호가 사용하려는 함수 closest_pair 는 이좌표 리스트를 파라미터로 받고, 리스트 안에서 가장 가까운 두 매장을 [(x1, y1), (x2, y2)]형식으로 리턴합니다.

 

참고로 태호는 이미 두 좌표 사이의 거리를 계산해 주는 함수 distance를 써 놨는데요. 함수 distance는 인풋으로 두 튜플을 받아서 그 사이의 직선거리를 리턴합니다.

print(distance((2, 5), (5, 9))) # => 두 지점 사이의 거리 5.0이 출력됨

 

문제

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

실행결과

[(2, 3), (3, 4)]

답안

# 제곱근 사용을 위한 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):
    # 현재까지 본 가장 가까운 두 매장
    pair = [coordinates[0], coordinates[1]]
  
    for i in range(len(coordinates) - 1):
        for j in range(i + 1, len(coordinates)):
            store1, store2 = coordinates[i], coordinates[j]

            # 더 가까운 두 매장을 찾으면 pair 업데이트
            if distance(pair[0], pair[1]) > distance(store1, store2):
                pair = [store1, store2]

    return pair

# 테스트 코드
test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)]
print(closest_pair(test_coordinates))