알고리즘
-
[알고리즘] Floyd Warshall알고리즘 2021. 12. 4. 21:21
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. floyd warshall 알고리즘이란? 음의 사이클이 없는 그래프에서 모든 정점에서 다른 모든 정점으로의 최단 거리를 구하는 알고리즘 이며 음의 간선이 존재하여도 최단 거리를 구할 수 있습니다. 또한 floyd warshall 알고리즘은 경유하는 정점을 기준으로 최단거리를 구해나가는 알고리즘 입니다. 2. Dijkstra VS floyd warshall floyd warshall알고리즘과 Dijkstra 알고리즘은 유사 하지만 조금씩의 차이점이 있습니다. Dijkstra는 특정 정점에서의 최단 거리를 구하는 알고리즘이고 floyd warshall은 모든 정점의 ..
-
[알고리즘] Dijkstra 알고리즘알고리즘 2021. 12. 4. 03:02
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. Dijkstra 알고리즘이란? 음의 가중치(비용)이 없는 그래프에서 특정 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘을 말합니다. 다익스트라 알고리즘은 그리디와 다이나믹 프로그래밍 방법을 사용하여 구현합니다. 다익스트라는 시작 노드에서 아직 방문하지 않은 노드들 중 최단거리 노드를 선택 합니다. (그리디 기법) 다익스트라는 시작 노드에서 갈 수 있는 노드들을 방문하면서 비용이 최소면 갱신합니다. (다이나믹 프로그래밍 기법) 위 2가지 방법을 반복하여 특정 노드에서 나머지 모든 노드로 가는 최단거리를 구하는 알고리즘 입니다. 2. 알고리즘 방법 그래..
-
[알고리즘] Kruskal 알고리즘알고리즘 2021. 12. 2. 14:53
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. Kruskal 알고리즘이란 그래프의 간선에 비용이 있는 경우 해당 그래프이 모든 정점을 연결하는 최소 비용으로 연결하는 최소비용 신장트리를 찾는 알고리즘 입니다. 신장트리 그래프의 모든 정점을 포함하고 정점들은 간선으로 연결되어 있으면서 사이클이 존재하지 않는 그래프를 말합니다. 위 이미지의 그래프가 그래프의 신장트리가 됩니다. 수많은 신장트리 중에서 연결된 간선의 비용이 최소가 되는 신장트리를 바로 최소비용 신장트리라고 하며 Kruskal 알고리즘을 통해 해당 그래프를 찾을 수 있습니다. 2. Kruskal 알고리즘 고려사항 최소 비용의 간선을 선택하는 과정을 ..
-
[알고리즘] Binary Search 알고리즘알고리즘 2021. 11. 18. 17:58
이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다. 틀리거나 잘못된 정보가 있을 수 있습니다. 댓글로 알려주시면 수정하도록 하겠습니다. 1. 이진 탐색이란? 이진 탐색은 알고리즘 명칭 그대로 탐색을 위한 알고리즘이다. 이진 탐색은 배열 또는 List에서 가운데 값을 기준으로 찾고자 하는 값이 큰지 작은지 판단 후 가운데 값이 찾고자 하는 값보다 작은 경우 왼쪽의 그룹을 반대로 가운데 값이 찾고자 하는 값보다 큰 경우는 오른쪽 그룹을 이용하여 다시 중간 값과 비교하는 방법으로 값을 찾는 방법입니다. ※단 이진 탐색은 가운데 값을 기준으로 작으면 왼쪽, 크면 오른쪽을 구분해야 되므로 정렬된 데이터에만 적용이 가능합니다. 2. 이진 탐색 방법 정렬된 값 {1, 4, 6, 8, 10, 15, 27, 29, 3..