다익스트라2 [Algorithm] 다익스트라 알고리즘(Dijkstra Algorithm) 다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘이며 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 두 노드 간의 최단경로를 찾는 알고리즘이기도 하다. (무방향/ 방향그래프 둘다 상관없이 사용가능하다) 해당 알고리즘은 DP(다이나믹 프로그래밍)와 Greedy Algorithm(탐욕 알고리즘)을 복합적으로 사용하는 알고리즘이다. 최단거리는 여러개의 최단거리로 나눠져있고 이전까지 구한 최단 거리는 그대로 사용한다 → DP 눈앞에 보이는 최적의 선택을 한다 → Greedy 예시를 들면서 한번 다익스트라로 어떻게 풀어나가는지 확인해보고 마무리 지어보겠습니다. 예시 네비게이션 1번에서 6번을 최단 경로로 찾아가야하는 상황에서 모든 노드까지의 최단거리.. 2024. 4. 8. [Algorithm] Greedy Algorithm 목차 1. Greedy Algorithm? 2. 대표적인 Greedy 3. 코드모음 _링크_ Greedy Algorithm이란? Greedy Algorithm(이하 Greedy) 말 그대로 탐욕스럽게 현재 '가장 좋아 보이는' 답(최선의 선택)을 선택하는 알고리즘 Greedy는 DP(동적프로그래밍)을 간단한 문제 해결에도 지나치게 많은 일을 하는 문제점을 해결하고자 고안되었다. 최선의 선택은 선택할 당시에 가장 좋은 것을 선택하는 것을 의미합니다 간단하게 예시를 들면 눈앞에 12만원과 18만원이 있다면 18만원을 선택하는 것과 동일합니다. 뒤에 뭐가 있든 최선을 선택하는 것은 좋은 결과물을 보장해줄까요? 한번 예시를 들어보죠 거스름돈 예시입니다. 기존 화폐단위에서 10만원을 큰 화폐부터 거슬러 줘서 적은.. 2024. 4. 7. 이전 1 다음 728x90
