Study Log/코딩테스트
[그리디] 당장 좋은 것만 선택하는 그리디 - 거스름돈 예제
그리디 알고리즘이란, 현재 상황에서 지금 당장 좋은 것만 고르는 방법. 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 최단경로문제는, 플로이드 워셜 혹은 다익스트라 알고리즘 과 같은 알고리즘을 미리 알고 있어야 가능하다. *플로이드 워셜(Floyd Warshall) : 변의 가중치가 음이거나 양인 가중 그래프에서 최단 경로들을 찾는 알고리즘이다. 알고리즘을 한 번 수행하면 모든 꼭짓점 쌍 간의 최단 경로의 길이을 찾는다 *다익스트라(Dijkstra) 알고리즘 : 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘 위 알고리즘에 대해서는 추후 더 공부해보겠다. 보통 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문..
