[Algorithm] Brute Force - 가까운 좌표 찾기

hyo_·2021년 4월 28일

Codeit algorithm brute force 알고리즘

알고리즘

목록 보기

2/3

Brute Force 알고리즘 예제

가장 가까운 두 개의 좌표 찾기

문제

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

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

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

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

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

접근

모든 각각의 좌표끼리의 비교가 필요하니 이중 for문을 사용한다.
distance의 약자인 dis라는 변수를 만들어 임시 값을 -1로 초기화 한다.(거리는 음수x -> for문이 처음 돌때의 값인 것을 표시하기 위해 음수 값을 넣었다.)
두 좌표의 계산 값이 dis 보다 작은 값이면 dis = result 하고 그때의 x1, x2, y1, y2 값을 변수에 저장
for문이 다 돌고 난 뒤, [(x1, y1), (x2, y2)] 리스트 반환

code

# 제곱근 사용을 위한 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):
    dis = -1 
    x1, x2, y1, y2 = 0, 0, 0, 0
    for i in range(len(coordinates)):
        for j in range(i+1, len(coordinates)):
            result = distance(coordinates[i], coordinates[j])
            if dis == -1 or result < dis:
                dis = result
                x1, x2, y1, y2 = coordinates[i][0], coordinates[j][0], coordinates[i][1], coordinates[j][1] 
    return [(x1, y1), (x2, y2)]             


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

결과 값

답

# 제곱근 사용을 위한 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))

내 코드 리뷰

x1, x2, y1, y2 변수를 하나씩 만들어서 저장 -> pair 리스트 변수 처럼 한번에 저장 하도록 하자!(코드가 더 간결해진다.)
dis, result 변수 결과 값 저장 -> 굳이 변수로 만들어 저장하기 보단 if distance(pair[0], pair[1]) > distance(store1, store2):이렇게 함수 return 값을 직접 비교해도 됐을 듯하다.