2021-10-09 가장 가까운 거리 구하기 반영환

튜플 두개를 넘기면 거리 계산을 해주는 함수를 distance로 정의해서 참조하자.

일단 거리를 계산해서 최소거리를 구하는 것은 어렵지 않다.

그런데 그 최소거리가 누구의 것인지 알려면, 반드시 key-value 쌍의 데이터 구조여야 한다.

따라서 dict 구조를 사용했다.

 

from math import sqrt

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



def closest_pair(coordinates):
    container = {}
    def find_value(x):
        return container[x]
    for i in range(len(coordinates)):
        for j in range(i+1, len(coordinates)):
            dist = distance(coordinates[i], coordinates[j])
            container[f'{i},{j}'] = dist
            
    key_min = min(container.keys(), key = find_value)
    
    
    return [coordinates[int(key_min[0])],coordinates[int(key_min[-1])]]

 

 

 

그런데 dict쌍을 쓰지 않고 temp 리스트를 만들어 그 값을 업데이트 하는 방식도 존재했다..!

 

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

 

나의 방식 -> 일단 냅다 다 구해놓고, 나중에 min 함수를 이용

 

업데이트 방식 -> 일단 기준 값을 정해놓고, 그 값과 다른 값을 비교해가면서 업데이트

 

아래의 업데이트 방식이 좀 더 빠를 것같은데...? 아닌거같기도하고... 흠..

근데 둘다 어차피 O(n^2) 이니까 상관 없겠다!