반응형 알고리즘/최단 경로 알고리즘5 카카오맵이 최적 경로를 결정하는 데까지 카카오맵에서 불편함을 느끼고, 궁금증을 해결하다. 안녕하세요! NewCodes입니다!! 우선 이전 포스팅에서제가 가졌던 궁금증에 대해 다시 살펴보겠습니다. 위 그림은 제가 사는 동네입니다. 보시다시피 1번 경로가 2번보다 훨씬 더 빠른 길입니다. 하지만, 카카오맵이 항상 2번 경로를 추천해줬습니다. 그래서 저는 카카오택시를 탈 때면 항상 시간과 돈을 불필요하게 소모하곤 했습니다. 이러한 현상이 1년 이상 반복되자저는 궁금해졌습니다. 카카오맵은 도대체 어떤 이유로2번 경로를 최적 경로로 추천할까? 길찾기 서비스는 어떤 원리로 동작할까? 드디어 이 궁금증에 대한 마침표를 찍고자 합니다!이를 위해 아래와 같은 과정을 거쳤습니다. 1단계: 가설 설정2단계: 다양한 길찾기 알고리즘 학습A* Al.. 2024. 2. 7. 카카오맵과 티맵이 사용하는 알고리즘 - Customizable Contraction Hierarchies CCH(Customizable Contraction Hierarchies) 안녕하세요! NewCodes입니다! 저번 포스팅에서는 최단 경로 알고리즘 중의 하나인 CH 알고리즘(Contraction Hierarcies)에 대해 다뤘습니다. 해당 알고리즘의 가장 큰 특징을 요약해드리자면요. 전처리 단계에서 '지름길'을 추가하여 쿼리에서 비약적인 속도를 향상시킬 수 있다는 것입니다. CH는 기존의 다익스트라, A* 알고리즘보다 비약적인 속도 향상을 가져온 건 사실입니다. 하지만, 실시간으로 빠르게 변하는 교통 상황 정보를 처리하는 데는 무리가 있었습니다. 그 이유는 다음과 같습니다. 특정 도로 구간의 정체, 기상 악화 등으로 인한 각종 이슈가 생기면 다시 전처리 작업을 해야 합니다. 그래프의 모양이 .. 2024. 2. 6. Contraction Hierarchies - 현실에서 쓰이는 길찾기 알고리즘 Contraction Hierarchies - 현실에서 쓰이는 길찾기 알고리즘 안녕하세요. NewCodes입니다! 이번 글에서는 현실에서 쓰이는 길찾기 알고리즘인CH(Contraction Hierarchies)에 대해 알아보겠습니다. 해당 글을 읽기 전에사전지식으로 다익스트라와 A* 알고리즘이 필요합니다! CH 알고리즘이란'적절한 지름길을 미리 만들어두고 효율적으로 탐색할 수 있게 하는 알고리즘'을 의미합니다. 그리고 CH 알고리즘은 현재 카카오맵, 티맵에서 쓰이는CCH 알고리즘의 근간이 됩니다. CH 알고리즘에 대해 학습하기 이전에학습할 필요성을 알아보기 위해우선 다익스트라와 A* 알고리즘에 대해 간단히 짚어보겠습니다. 괜찮은 다익스트라 알고리즘 있는데 왜 굳이 CH가 필요해?.. 2024. 2. 6. A* 알고리즘이 도대체 뭔데?? (with java) 🖥️ A* 알고리즘의 동작 과정과 특징 with java A* 알고리즘은 주로 게임에서 길을 찾는 데 활용됩니다!! A* 알고리즘이란 '출발 노드에서 목표 노드까지의 최단 거리를 구하는 알고리즘'을 의미합니다. '에이스타 알고리즘'이라고도 합니다. 이는 다익스트라 알고리즘에 기반을 두고 있습니다. 따라서, A*에 대해 본격적으로 알아보기 전에 다익스트라에 대한 기본적인 부분을 간략하게 짚어보겠습니다. ✅ 다익스트라 알고리즘에 대해 먼저 알아보자! 다익스트림 알고리즘이란 '출발 노드에서 다른 모든 노드까지의 최단 거리를 각각 구하는 알고리즘'을 의미합니다. 동작 과정동작과정을 간단히 추상화하자면 다음과 같습니다. 준비: 출발지와 최단 거리 테이블을 초기화합니다. 선택: 방문하지 않은 장소 .. 2024. 1. 20. 왜 카카오맵은 더 느린 길을 최적 경로라 판단할까? 왜 카카오맵은 더 느린 길을 최적 경로라 판단할까? 안녕하세요!NewCodes입니다! 평소에 카카오맵을 사용하면서 불편했던 점딱 한 가지에 대해서 깊게 파보는 시간을 가지려고 합니다. 해당 글을 쓰게 된 동기저는 평소에 카카오택시를 자주 이용하는 편입니다. 집으로 향할 때는 항상 즐거운 마음으로 택시를 타곤 하죠. 그런데 !! 집으로 가는 경로가 항상 뭔가 이상했습니다. 더 빠른 길이 있음에도 불구하고 항상 돌아가는 것이었죠. 제 집의 위치가 노출될 수도 있어 지도를 그림으로 대체하여 설명해보겠습니다. 1번 경로가 빠른 길이며 2번 경로가 느린 길입니다. 카카오맵에서는 항상 2번 경로로 추천됩니다. 반면에 네이버맵에서는 1번 경로로 추천됩니다. 1번 경로가 정상적인 길이 아니라고.. 2024. 1. 15. 이전 1 다음 반응형
