알고리즘16 [알고리즘] 다익스트라 (Dijkstra) 목차 다익스트라 알고리즘이란? 다익스트라(Dijkstra) 알고리즘은 DP를 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘은 DP와 그리디 문제로도 분류되기도 한다. DP 문제로 분류되는 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. A에서 D로 가는 최단 경로를 예로 들어보겠다. A에서 B로 가고 B에서 C로 가고 C에서 D로 가는 게 A에서 D로 가는 최단 경로라면 그 과정 속에 있던 A에서 B로 가는 경로도 최단 경로이고, B에서 C로 가는 경로도 최단 경로이고 C에서 D로 가는 경로 또한 최단 경로여야 하기 때문이다. 그리고 다익스트라.. 2022. 5. 25. [알고리즘] DFS & BFS 목차 DFS (깊이 우선 탐색) DFS (Depth-First Search)는 깊이 우선 탐색이라고도 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 재귀나 스택을 이용해서 구현을 한다. DFS를 구현할 때 어떤 노드를 방문했었는지 꼭 검사를 해야 한다. 왜냐하면 이를 검사하지 않을 경우 무한루프에 빠질 수 있기 때문이다. 보통 모든 노드를 방문하고자 할 때, DFS를 이용한다. 하지만, 검색 속도는 보통 BFS보다 느리다. 구현 방법 : 1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 위의 1번.. 2022. 5. 23. [알고리즘] 플로이드 와샬 (Floyd Warshall) 목차 플로이드 와샬이란? 다익스트라 알고리즘은 하나의 노드에서 출발했을 때 다른 모든 노드로의 최단 경로를 구하는 알고리즘이다. 하지만 플로이드 와샬 알고리즘은 모든 노드에서 모든 노드로의 최단 경로를 구하는 알고리즘이다. 그리고 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택을 해서 그 적은 비용을 가지는 노드의 인접한 노드들로 가는 비용을 하나씩 계산하는 방식이었다면 플로이드 와샬 같은 경우는 거쳐가는 노드를 기준으로 알고리즘을 수행한다는 특징이 있다. 추가로 플로이드 와샬은 다이나믹 프로그래밍 기법을 사용한 알고리즘이고, 인접 행렬을 이용하여 각 노드 간 최소의 비용을 계산한다. 플로이드 와샬 예시 위와 같은 그래프가 있다고 가정해 보겠다. 그리고 각각의 노드에서 다른 노드로 가는 비용을 2차원.. 2022. 5. 21. [알고리즘] 배낭 문제 (Knapsack Problem) 목차 배낭 문제란? 배낭 문제란 담을 수 있는 최대 무게가 정해진 배낭이 있고 각각의 무게와 가치가 주어진 물건들이 주어졌을 때, 배낭에 담은 물건들의 가치가 최대가 되도록 하게 물건을 고르는 방법을 찾는 문제이다. 배낭 문제 예시 4가지의 물건 ABCD가 있고 배낭의 최대 무게는 5라고 가정하겠다. 무게가 1, 가치가 30인 물건을 A; 무게가 2, 가치가 20인 물건을 B; 무게가 3, 가치가 40인 물건을 C; 그리고 무게가 4, 가치가 10인 물건을 D라고 하겠다. 그리고 우리가 가진 가방의 최대 무게는 5이다. 이때 이 가방에 넣을 수 있는 최대 가치가 몇인지를 구하는 것이다. 예를 들어서 B와 C를 넣어서 총가치가 60이 되도록 가방에 넣을 수 있고, 아니면 A와 D를 넣어서 총가치가 40이 .. 2022. 4. 7. 이전 1 2 3 4 다음 반응형
