Algorithm(pt.2)

Posted on Disqus:

최단 경로 알고리즘

  • 가장 짧은 경로를 찾는 것
    • 한 지점 → 한 지점
    • 한 지점 → 모든 지점
    • 모든 지점 → 모든 지점
  • 지점 = 노드 (예. 마을, 국가 등..)
  • 이동 가능함 = 간선으로 표시

다익스트라 최단 경로 알고리즘

  • 특정 한 노드 → 다른 모든 노드 계산
  • 그리디 알고리즘으로 가장 비용이 적은 노드 선택
  • 동작 과정
    • 출발 노드 설정
    • 최단 거리 테이블 초기화 (자신의 노드 = 0, 그 외 노드 거리 = $\infty$)
    • 방문하지 않은 노드에서 최단 거리가 가장 짧은 노드 선택하고 다른 노드로 가는 비용 계산하는 과정 반복
      • 동일 비용을 갖는 경우 더 작은 수를 갖는 노드부터 우선 계산
      • 마지막 노드 정보를 처리하지 않아도 상관없음 (이전의 정보를 활용하여 이미 가장 짧은 노드의 거리를 갱신했기 때문)
  • 처리 과정 중 더 짧은 노드가 존재하면 해당 노드를 최단 거리 노드로 갱신
  • 한 번 처리된 노드의 최단 거리는 고정 → 변화 없음
  • 노드 탐색 시 BFS 이용하는 알고리즘

우선순위 큐

  • 우선순위가 높은 데이터를 먼저 삭제
  • 힙 (최소 힙, 최대 힙)
  • 다익스트라 알고리즘에서 사용됨. (시간을 개선시키기 위함)
  • 파이썬: heapq 라이브러리 사용 가능 (min heap 사용) ⇒ 다익스트라 알고리즘에서 사용됨.

— 참고: 파이썬 알고리즘 인터뷰 책 & 이코테 2021 강의