[알고리즘] 유클리드 거리 & 맨해튼 거리

알고리즘

취업 드가자잇 2024. 6. 3. 22:28

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

해당 문제를 풀며 키패드 간의 거리를 계산하기 위해서는 두 좌표(이전 키패트와 현재 키패드의 거리)의 거리를 계산해야한다고 생각해 유클리드 거리를 사용했지만 제대로 풀리지 않았다.

고려하지 못했던 것은 유클리드 거리는 대각선 이동을 포함한 직선 거리를 계산하기 때문에, 수평 및 수직 방향으로만 이동 가능한 키패트 문제에서는 실제 이동 거리와 맞지 않는다는 것이다.

그래서 맨해튼 거리를 사용했더니 문제없이 풀렸다.

어릴때 수학 공부를 소홀히 한 것이 지금 와서 많이 체감이 되고 있다...

맨해튼 거리는 두 점 사이의 거리 중 격자 형태의 도로망을 따라 이동해야 하는 경우 사용된다.

예를 들어, 뉴욕 시처럼 격자형 도로망, 혹은 키패트에서 두 위치 사이의 이동 거리를 계산할 때.

Math.abs(x2−x1)+ Math.abs(y2−y1);

두 점 사이의 실제 직선 거리를 구할 때 사용된다.

예를 들어, 지도에서 두 위치 사이의 직선 거리를 계산할 때.

Math.sqrt(Math.pow(x2−x1, 2) + Math.pow(y2−y1, 2);