알루 코딩

위 문제는 그리디 문제입니다. 리스트를 순회하면서 최적의 값을 찾아나가는 문제이죠. 맨 처음에 저는 O(n^2))의 복잡도로 문제를 풀었습니다. 그래서, 시간초과의 문제에 걸렸습니다. 제약조건을 보면 prices의 길이가 최대 100000이기 때문에, O(n^2)의 복잡도로 풀어버리면 10의 8승을 넘기 때문에 시간초과에 걸리는 것은 당연한 소리겠죠! 처음, 시간초과에 걸렸던 코드는 아래와 같습니다. class Solution: def maxProfit(self, prices: List[int]) -> int: is_reversed_sorted = all(prices[i] >= prices[i+1] for i in range(len(prices)-1)) if is_reversed_sorted: retur..

그리디(Greedy) 알고리즘 : 욕심쟁이 알고리즘이라고도 하는 탐욕 알고리즘은 단순하지만 강력한 문제 해결법이다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 그리디 알고리즘은 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 가장 좋은 것을 선택하는 알고리즘으로, 문제에서 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 와 같은 기준을 문제에서 알게 모르게 제공해준다. 정렬 알고리즘을 사용했을 때, 효과적으로 풀 수 있어, 보통 정렬 알고리즘과 짝을 이루어 출제되곤 한다. 대표적인 그리디 알고리즘 예제 - 1) 동전 거스름돈 문제 import sys input = sys.s..

전형적인 그리디 알고리즘 문제이다. 처음에는 계속 시간초과 문제를 해결하지 못했었다. 처음에 풀었던 코드는 이러했다. n = int(input()) roads = list(map(int, input().split())) prices = list(map(int, input().split())) total = prices[0] * roads[0] # 출발 도시의 기름가격 x 출발 도시와 두번째 도시 사이의 도로길이 previous_price = prices[0] # previous_price 에 우선 출발 도시의 가격 저장 # k 라는 변수를 1로 잡았다(두번째 도시와 세번째 도시 사이의 도로 길이 인덱스는 1 이므로) k = 1 # 도시 간격(도로 길이)를 나타내는 인덱스 for i in prices[1:..