최단 경로 알고리즘? 그래프에서 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘이다. 대표적인 최단 경로 알고리즘은 다음과 같다. DFS 다익스트라 벨만-포드 플로이드 와샬 목적에 따라 알고리즘을 선택할 수 있다. BFS, DFS 그래프의 간선 가중치가 모두 같을 때 적합하다. 2차원 배열로 구성된 지도에서 최단 거리를 찾아야 한다면 BFS, DFS로 푸는 경우가 많다. 다익스트라 알고리즘 그래프의 간선 가중치가 각각 다른 경우 적합하다. 우선 큐를 이용해서 만들 수 있으며, 시간 복잡도는 V가 정점의 수, E가 간선의 수라면 O(E log V) 이다. 작동 방법 1. 시작점을 제외한 모든 정점의 거리를 무한으로 설정한다. 시작은 0 2. 시작점을 선택한다. 3. 선택한 정점에서 갈 수 있는 정점의..

깊이 우선 탐색 : 탐색을 할 때 깊이를 우선으로 하여 탐색을 수행하는 탐색 알고리즘 ​ ' 맹목적으로 각 노드를 탐색 ' 할 경우 주로 사용하는 탐색 기법으로, 모든 노드를 방문하고자 하는 경우 ( 완전 탐색) 사용 너비 우선 탐색 ( BFS) 보다 지나온 경로를 쉽게 파악할 수 있다는 장점이 있다. 또 층별로 모든 자식 노드를 저장해야 할 필요가 없기 때문에 BFS에 비해 메모리 요구량이 훨씬 적다 ​ ※ 어느 방향으로 검색할지 확률에 따라 속도가 많이 빨라질 수도 있고 느려질 수도 있다.(확률 의존) ​ 깊이 우선 탐색을 수행하기 위해서 필요한 준비물은 Stack이다. 이다. ※컴퓨터는 구조적으로 스택의 원리를 사용하기 때문에 재귀 함수를 사용하여 구현이 가능하다. ​ 이제 어떤 식으로 정렬이 이루..