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