탐욕 알고리즘2 [python] 13305번 - 주유소 문제 파이썬 풀이 기름 값의 최소 비용을 구하는 문제이다. 최소 비용을 저장해두는 변수를 하나 선언한 뒤 이보다 작은 기름 값이 나오면 최소 비용을 갱신한다. 따라서 최소 비용이 갱신되기 전까지는 이전까지의 최소 비용을 이용해 이동을 하고 새로운 최소 비용이 갱신되면 해당 비용으로 이동을 진행하면 된다. import sys from typing import Mapping input = sys.stdin.readline N = int(input().rstrip()) road_length = list(map(int, input().rstrip().split())) oil_price = list(map(int, input().rstrip().split())) result = 0 min_price = oil_p.. 2021. 11. 24. 그리디 알고리즘 내용 정리 그리디 알고리즘 그리디 알고리즘이란? 탐욕(그리디) 알고리즘이란 현재 상황에서 가장 최선의(좋은) 선택을 고르는 알고리즘을 의미한다. 그리디 알고리즘은 현재 상황의 가장 좋은 결과를 선택하는 것으로 최종 결과에 대한 최적의 해를 구하는 것과는 다르다. 위와 같은 예시에서 가장 합이 큰 경로를 찾는다고 할 때 최종적으로 가장 최적의 해는 노란색 루트를 따라 111을 구하는 경로이다. 그러나 그리디 알고리즘은 루트에서 가장 최적의 해인 20으로, 20에서 가장 최적의 해인 41로 가는 파란색 루트를 따라간다. 현재의 상황에서 가장 큰 수를 따라 최종적으로 62의 값을 얻게 된다. 이렇게 그리디 알고리즘이 최종적으로 가장 최적의 해를 구하는 것은 아니다. 그리디 알고리즘의 조건 그렇다면 그리디 알고리즘을 사용.. 2021. 11. 23. 이전 1 다음
