코딩 테스트2 최단 경로 알고리즘이란 무엇일까?(2) - 다익스트라 알고리즘/플로이드 워셜 알고리즘 최단 경로 알고리즘 개선된 다익스트라 알고리즘 앞서서 기본적인 다익스트라 알고리즘에 대해서 살펴보았다. 이번에는 조금 더 개선된 다익스트라 알고리즘에 대하여 알아보도록 할 것 이다. 힙(Heap) 자료구조 개선된 다익스트라 알고리즘은 힙 자료구조를 사용한다. 힙 자료구조란 우선순위 큐(Priority Queue)를 구현하기 위해 사용하는 자료구조 중 하나로, 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다. 힙 자료구조는 코드상으로 heapq 를 사용하며, heapq는 원소로 튜플 입력 받으면 첫번째 원소를 기준으로 우선 순위 큐를 구성한다. 우선순위 값 표현에는 일반적으로 정수형 자료형의 변수 사용된다. 최소 힙 또는 최대 힙을 이용할 수 있는데, 파이썬 라이브러리는 기본적으로 최소 힙.. 2022. 4. 12. 최단 경로 알고리즘이란 무엇일까? 최단경로(Shortest Path)란 무엇인가? 최단 경로란 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 그래서 코딩테스트에서 길 찾기 문제로 자주 출제된다. 최단 경로 자체는 상황에 맞는 효율적인 알고리즘 정립되어 있기 때문에, 이 알고리즘만 숙지한다면 해당 유형의 문제를 푸는 방법을 떠올리는 데에는 큰 문제가 없을 것으로 보인다. 최단경로 문제는 노드와 간선으로 이루어진 그래프로 표현한다. 또한 실제 코딩 테스트에서는 단순히 최단 거리를 출력하는 문제가 자주 출제되기 때문에, 학부 수준에서는 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘만 알면된다. 오늘은 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용되는 다익스트라 최단 경로 알고리즘과 플로이드 워셜 알고리즘에.. 2022. 3. 29. 이전 1 다음