백준 문제풀이(파이썬)/그리디 알고리즘

도시로 이동하는 동안 비용의 최솟값을 구하는 문제이다. 그리디 알고리즘의 기본적인 특성을 가지고 풀면 된다. 각 도시로 이동할 때의 최소 비용은 (기름 가격이 싼 도시의 기름 가격 * 다음 도시로 이동할 때까지의 거리의 합)이다. 그러므로 매번 도시를 이동할 때마다 가격이 싼 도시에서 기름을 최대한 넣어주면 될 것이다. 그러므로 처음부터 시작해서 기름 가격이 쌀 때마다 최솟값으로 갱신해주고 거리를 곱해서 합을 구해주면 된다. ##변수 선언 부분## road = [] price = [] road_sum = 0 sum = 0 ##메인 함수 부분## if __name__ == "__main__": N = int(input()) road = [int(x) for x in input().split()] price..

괄호를 넣어 식의 답을 최소로 만드는 문제이다. 풀이는 생각보다 간단하다. 식이 55-50+40이라하면, -를 기준으로 뒤의 값들은 그 다음 -가 나올 때 까지 모두 더해주면 된다. 다른 식들도 -를 기준으로 더해주기만 하면 되기 때문에, 나는 수를 더해주는 함수를 만들고, 첫번째 시행일 때는 sum에 더해주고, 두번째 시행부터는 -가 나오기 때문에 빼주는 식으로 코드를 짰다. 그러다보니 코드도 길고 복잡했다. ##함수 선언 부분## def Plus_calculation(e): #덧셈 식을 계산해주는 함수 num = [] sum_num = 0 length = 0 for i in range(len(e)): #받은 배열의 길이만큼 if e[i] != '+': #+가 아닐 때는 num.append(e[i]) ..

문제를 풀기 전에 이번 단계의 주제인 그리디 알고리즘에 대해 알아보자. Greedy Algorithm이란 문제를 해결하는 과정에서 그 순간마다 최적이라고 생각되는 결정을 하여 최종 해답에 도달하는 문제 해결 방식이다. 위 그림은 가장 큰 수를 찾는 문제인데, 매 순간순간마다 큰 값을 찾아나가면 엉뚱한 결과가 나온다. 다시말해, 그리디 알고리즘이 항상 전체 문제해결에서 최적의 해답을 찾지는 못한다는 것이다. 그렇다면 왜 이 알고리즘을 사용할까? 그리디 알고리즘은의 가장 큰 장점은 계산 속도에 있다. DP는 모든 경우를 탐색하지만 계산 속도가 느리고 그리디는 모든 경우를 탐색하지는 못하지만 계산 속도가 무척 빠르다. 그래서 DP와 그리디는 상호 보완하는 개념으로 알려져 있다. 또한 그리디 알고리즘은 Gree..