알루 코딩

위 문제는 그리디 문제입니다. 리스트를 순회하면서 최적의 값을 찾아나가는 문제이죠. 맨 처음에 저는 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..

단순한 그리디 문제였다. 맨 처음에는 그리디가 아니라 dp문제인가 싶었다. 이전에도 풀었던 기록이 있어서 단순한 그리디로도 풀릴 듯해서 바로 푼 문제였다. 코드는 아래와 같다. import sys input = sys.stdin.readline height = [] for _ in range(9): height.append(int(input())) diff = sum(height)-100 # 9명의 난쟁이 키의 합과 100의 차이를 구한다 find_two_false = False # find_two_false라는 초기변수를 False로 설정한다. for i in height: for j in height[1:]: if i + j == diff: # height를 돌면서 두 난쟁이의 합이 diff와 같으면..

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

최소값을 구하려면 우선, 시간을 오름차순으로 나열하는 것이 관건이다. 처음에는 map 함수를 통해서 여러개의 값을 받는 것을 list화 시켜서 정렬(sort)을 해야 하는데, 사용자에게 여러개의 값을 입력받을 때 number 값을 이용하는 줄 알고 애를 먹었다. 자바같은 언어에서는 보통 number 같은 변수를 입력 받아 for문을 돌면서 배열에 값을 넣어주기 때문이다. 하지만, 사용자에게 입력 받은 number는 나중에 값을 하나씩 더할 때 사용되는 것이고, 사용자에게 차례로 입력받은 값을 리스트에 넣으려면 그냥 map함수를 list() 해주면 됐다. 그리고 정렬을 할 때는 맨 처음에 애를 먹었던 것이 number = int(input()) time_list = map(int, input().split..