취미처럼

다익스트라(Dijkstra) 최단경로 알고리즘 그리디 알고리즘으로 분류 - 매번 가장 비용이 적은 노드를 선택해서 반복 DFS/BFS 의 경우 모든 노드간의 가중치가 같고, 얼마나 적은 수의 노드를 거쳤는지 탐색 다익스트라의 경우 노드간의 가중치가 달라서 얼마나 적은 가중치의 합으로 목적지에 도착했는지 탐색 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 3번 4번 반복 시간복잡도 : O(N²) 단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 리스트의 모든 원소를 확인(순차탐색)한다. 우선순위 큐 우선순위가 가장 높은 데이터를..

1. DFS(Depth - First Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 그래프는 노드와 간선으로 표현되며, 두 노드가 간선으로 연결되어 있다면 두 노드가 "인접하다"라고 표현한다. 스택이나 재귀함수로 구현 가능 모든 경우의 수를 탐색하고자 하는 미로 문제에 적합 1. 인접행렬 방식 2차원 배열로 그래프의 연결관계를 표현하는 방식 연결되지 않은 정보도 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비됨 노드 번호로 바로 접근 가능하므로 인접리스트에 비해 정보를 얻는 속도가 빠름 2. 인접리스트 방식 노드에 연결된 정보만을 리스트로 추가하는 방식 연결된 정보만 저장하기 때문에 메모리를 효율적으로 사용 인접행렬 방식에 비해 연결된 데이터..