[면접 합격자료] 현대오토에버 길찾기 서비스 알고리즘 및 서버 개발 합격 문항 기출 최종합격

1. 길찾기 서비스의 기본 알고리즘인 다익스트라와 A 알고리즘의 차이점과 각각의 장단점을 설명하세요.

다익스트라는 최단 경로를 찾기 위해 그래프의 모든 정점을 탐색하며 거리 값을 갱신하는 방식으로, 주로 가중치가 양수인 경우에 효율적입니다. 이를 기반으로 한 알고리즘은 안정적이지만, 탐색 범위가 크면 시간 복잡도가 높아져 평균적으로 O(V^ 또는 우선순위 큐를 사용할 경우 O((V+E)logV)입니다. 반면 A 알고리즘은 휴리스틱 함수를 이용하여 목표 지점까지의 예상 거리를 고려하기 때문에 탐색 범위를 줄여 탐색 속도를 크게 향상시키며, 평균 시간복잡도는 다익스트라보다 훨씬 낮아집니다. 예를 들어, 서울 내 주요 도로망에서 거리 30km 구간의 길찾기 시 다익스트라는 평균 4초가 걸리는데, A는 휴리스틱 효율이 높을 경우 5초 수준까지 속도를 낼 수 있습니다. 다만, 휴리스틱 함수의 정확도에 따라 성능이 좌우되며, 부정확하면 다익스트라와 비슷하게 동작할 수 있습니다. 따라서 복잡한 도로망에서는 A의 속도 이점을 활용할 수 있으며, 안정성을 중시하는 경우에는 다익스트라가 유리하다고 판단됩니다.

2. 길찾기 서비스에서 실시간 교통정보…