[알고리즘 일기] 9. 가까운 매장 찾기

 

 

문제 09. (2021-05-09)

 

가까운 매장 찾기

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

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

 

 

설명

튜플은 각 매장의 위치를 x, y 좌표로 나타낸 것입니다. 0번 매장은 (2, 3)에, 그리고 1번 매장은 (12, 30) 위치에 있는 거죠. 함수 closest_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):
    #Code

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

 

❧ 출력 예시

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

 

---

❧ 정답

from math import sqrt

def distance(store1, store2):
    return sqrt((store1[0] - store2[0]) ** 2 + (store1[1] - store2[1]) ** 2)

def closest_pair(coordinates):
    optimal_destination = [coordinates[0], coordinates[1]]
    for i in range(len(coordinates)-1):
        for j in range(i + 1, len(coordinates)):

            # 더 가까운 매장을 찾을 시, 업데이트
            if distance(optimal_destination[0], optimal_destination[1]) > distance(coordinates[i], coordinates[j]):
                optimal_destination = [coordinates[i], coordinates[j]]
    return optimal_destination

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

 

1️⃣ Brute-Force-Attack(무차별 대입 공격) 알고리즘 패러다임

2️⃣ 함수 cloesest_pair에는 반복문 두 개가 중첩되어 있는데, 둘 다 반복 횟수가 n에 비례한다.

└ 시간 복잡도 : O(n2)