목록그리디 (1)
minkylee
[Greedy] 거스름돈 문제
그리디 알고리즘 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자. 예를 들어 5개의 도시를 모두 한 번씩만 거쳐서 여행한다고 가정하자, 기름값을 아끼기 위해 가장 짧은 경로를 선택해야한다고 하면, 이 문제를 해결하기 위해 여러 방법을 사용할 수 있다. 모든 경로를 검사하는 브루트 포스를 이용해 답을 구하거나, 외판원 순회같은 복잡한 전략을 쓸 수도 있고 " 지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다 " 는 방법, 즉 그리디 알고리즘을 쓸 수도 있다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 전혀 없다. 그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될..
CSE/컴퓨터알고리즘
2024. 4. 22. 21:08