목표 Greedy, Dijkstra, DP 알고리즘과 같이 대표적인 알고리즘 중 하나인 DFS 그래프 탐색 알고리즘에 대해 이해하고 학습한다. DFS(Depth First Search)란 DFS(Depth First Search) DFS란 초기 노드에서 시작하여 해를 찾을때까지 자식 노드를 계속해서 타고 들어가며 탐색하는 완전탐색 알고리즘이다. 깊이(Depth)의 노드를 우선적으로 탐색하는 BFS와 반대되는 개념이라고 생각하면 이해하기 쉽다. DFS는 Stack 또는 재귀를 이용해 구현할 수 있는데 재귀를 이용해 구현하는것이 일반적이다. BFS에 대한 개념이 부족하다면 아래 글을 읽고 오면 좋다. https://zzzzseong.tistory.com/22 [Algorithm] BFS - 넓이 우선 탐색 ..

목표 최소비용 경로문제로 대표되는 Dijkstra 알고리즘에 대해 이해하고 학습한다. Dijkstra 알고리즘을 활용할 수 있는 알고리즘 문제를 풀어보고 정형화된 템플릿을 만들어보자. Dijkstra란 Dijkstra Dijkstra란 V개의 정점과 각각의 가중치(W)를 가진 E개의 간선을 가진 그래프에서 i번 정점에서 j번 정점까지로의 최소 가중치를 가지는, 최단 경로를 찾는 알고리즘이다. 아래는 Dijkstra 알고리즘을 활용할 수 있는 그래프의 예시이다. Dijkstra 알고리즘을 활용하기 위해서는 앞서 설명한 그래프, 정점 별 최소 가중치를 저장하기 위한 1차원 배열, 그래프 탐색을 위한 자료구조가 필요하다. 그래프 탐색을 위한 자료구조는 인접행렬과 우선순위 큐를 사용할 수 있고, 인접행렬을 개선..