코딩 테스트 문제를 풀다 보면 두 점 사이의 거리, 혹은 두 요소 사이의 거리를 구해야 될 때가 있다. 프로그래밍으로 두 점 사이의 거리를 계산하려면 좌표(coordinates
)와 아래 공식을 잘 활용해야 한다.
이 글에서는 두 점 사이의 거리를 구하는 대표적인 방법인 유클리드 거리, 맨해튼 거리의 개념과 계산 방법에 대해 말해보도록 하겠다.
유클리드 거리는 두 점 사이의 거리를 계산할 때 흔히 쓰는 방법이다. 이는 피타고라스 정리를 기반으로 하며, 공식은 다음과 같다.
import math
# 두 점의 좌표
x1, y1 = 1, 2
x2, y2 = 4, 6
# 유클리드 거리 계산
distance = math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
print(f"Euclidean distance: {distance}")
이 예제에서는 math.sqrt
함수를 사용하여 두 점 간의 유클리드 거리를 계산한다.
맨해튼 거리는 두 점 간의 수평 및 수직 거리의 합을 측정한다. 이는 격자형 도로망에서의 거리를 측정하는 데 유용하다.
# 두 점의 좌표
x1, y1 = 1, 2
x2, y2 = 4, 6
# 맨해튼 거리 계산
manhattan_distance = abs(x2 - x1) + abs(y2 - y1)
print(f"Manhattan distance: {manhattan_distance}")
이 예제에서는 abs
함수를 사용하여 두 점 간의 맨해튼 거리를 계산한다.
유클리드 거리와 맨해튼 거리는 각각의 특성에 맞게 다양한 상황에서 사용된다. 다음은 두 거리 계산 방법의 차이점과 각 방법이 적합한 사례를 비교한 것이다.
코딩 테스트 문제 예시:
2차원 평면에서의 최단 거리: 주어진 두 점 사이의 직선 거리를 계산하는 문제이다. 예를 들어, 점 A와 점 B 사이의 최단 거리 또는 여러 점 중에서 가장 가까운 점을 찾는 문제에 유용하다.
클러스터링: 여러 점이 주어졌을 때, 특정 점을 기준으로 가장 가까운 다른 점을 찾는 문제이다. K-최근접 이웃(KNN
) 알고리즘의 기본 아이디어를 구현하는 문제에서 유용하다.
코딩 테스트 문제 예시:
격자 기반 이동 문제: 격자 형태의 맵에서 시작 지점에서 목표 지점까지 이동할 때, 이동 거리의 합을 계산하는 문제이다. 예를 들어, 로봇이 격자 형태의 맵에서 이동할 때, 주어진 두 점 사이의 맨해튼 거리를 계산하는 문제이다.
경로 찾기: 특정 격자 맵에서 최소 이동 거리를 계산하는 문제에서 유용하다. A* 알고리즘 등의 경로 찾기 알고리즘에서 맨해튼 거리를 사용하여 최적 경로를 찾을 수 있다.
유클리드 거리는 연속적인 데이터와 기하학적인 문제에서 직선 거리 계산이 필요한 경우에 유용하다. 주로 점 사이의 직접적인 거리나 데이터 포인트 간의 유사성을 측정하는 문제에서 사용된다.
맨해튼 거리는 격자 기반 문제와 수직, 수평 이동만을 고려하는 문제에서 적합하다. 주로 도시 블록 거리 문제나 경로 최적화 문제에서 사용된다.
코딩 테스트 문제를 해결할 때, 문제의 특성을 잘 이해하고 적절한 거리 계산 방법을 선택하는 것은 매우 중요하다. 이 두 가지 거리 계산 방법의 차이점을 명확히 이해하면, 더 효율적이고 정확한 해결책을 찾는 데 도움이 될 것이다.
잘 기억해두었다가 거리 계산 문제에서 활용하자!