알고리즘 | 다익스트라

백트래킹에 이어서,,
다익스트라 알고리즘(Dijkstra's Algorithm)을 공부했었다.
코테 준비할 때 그래프 문제가 그렇게 싫었었지.

다익스트라 알고리즘

한 지점에서 다른 지점까지 가는 최단 경로를 찾는 알고리즘.

네이버 지도나 구글 지도가 길 안내할 때 여러 개의 경로를 보여주는데,
그 밑바탕에 깔린 기본 알고리즘이 바로 이 다익스트라 알고리즘이라고 한다.

핵심 아이디어

가장 짧은 길을 하나씩 확정시키며 탐색해 나간다.

처음 시작 지점에서
"현재까지 가장 가까운 지점"을 하나씩 확정해 나가는 구조다.

• '지금 당장 최적'인 선택을 하고
• 그 선택이 전체적으로도 최적이라는 성질을 이용하는 것

일명 그리디(Greedy) 방식이다.

한 스텝씩, 한 노드 씩,
"지금 계산된 것 중에 제일 짧은 길"을 선택하고 확정하고,
그 확정된 노드를 바탕으로 또 다른 노드를 업데이트한다.

이걸 반복하면
어느 순간 "모든 최단 거리"가 구해진다.

백트래킹은 조합을 찾는 데 좋고,
다익스트라는 '최적의 한 경로'를 찾는 데 강하다.

근래 데이터 파이프라인과 AI 작업의 시간 단축에 대해서 고민하고 있는데,
"가장 효율적인 수집 경로",,,, 이게 곧 다익스트라 아닌가?

백트래킹도 그렇고 알고리즘을 다시 보다 보니
괜히 이름 붙은 알고리즘이 아니다.
하나의 코딩 테스트 문제를 해결하려고 만들어진 게 아니라
여러 실생활 문제에 응용될 수 있도록 설계되어 있다는 게 확 체감되는,,

"가장 빠른 길"을 찾아주는 알고리즘이 있다면
개발자에게도 셀러에게도 너무 좋쟈나..

끊임 없이 고민하는 직원 되기.