그리디2 백준 - 13305 주유소 이번 문제는 주유소 문제로 각 도시마다 기름 값이 다른 주유소가 존재하고 우리는 모든 도시를 이동하기 위한 최소 비용을 구해야 한다. 다른건 제쳐두고 기본적인 것만 생각해보면 결국 1. 당장 다른 도시로 가기 위해서는 기름이 필요 2. 도시를 거치며 더 싼 주유소가 나오기 전 까지는 가장 저렴한 주유소에서 왕창 주유하고 가면 된다. 이러한 로직은 결국 도시를 하나씩 거치면서 이제까지 만난 기름의 최소값 만을 저장하며 순차적으로 총 가격에 더해주면 된다. 이러한 풀이는 그리디 알고리즘으로 현재까지 만난 주유소 중 기름 값이 가장 싼 주유소에서 주유하면 전체 주유 비용의 최소 값을 구할 수 있다는 개념이다. 풀이 def run(): N = int(input()) length_lst = list(map(int.. 2021. 9. 15. [알고리즘] 그리디 알고리즘 그리디 알고리즘 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 그리디(Greedy)함? Greedy : 탐욕스러운 탐욕 알고리즘, 욕심쟁이 알고리즘이라고도 불리는 알고리즘 말 그대로 매 순간마다 미래를 생각하지 않고 가장 최선의 선택만을 하는 기법 하지만 그리디는 그 선택의 순간에서는 최선일지 몰라도 전체를 생각했을 때 최선의 수는 아닐 수 있다! '마시멜로 실험'을 예시로 들 수 있는데 당장 눈 앞의 마시멜로를 먹게 될 경우 추후 더 많은 양의 마시멜로를 포기하는 셈이 되어버린다! 따라서 그리디는 최적해들의 집합이 전체 문제의 답인 경우에만 적용할 수 있다. 혹은 정답이 아닌 정답에 가까운 근사치를 구할 때 사용하거나... 예제 그리디 알고리즘의 가장 유명한 예로는 먼.. 2021. 9. 6. 이전 1 다음 반응형
