[Python] Greedy Algorithm

배수 관계에 놓여있는 동전이 주어졌을 때에는, 항상 큰 동전부터 이용하는 것이 좋음 -> greedy 알고리즘

 

동전더하기

1. coins 를 큰 수가 앞이 오도록 reverse

2. one of coins 으로 k 최대 몇 개 쓸 수 있는지 result에 추가 r +=  k // i 

3. 앞 코인이 k 가져갔으니까 k갱신 k % i

n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

# Please write your code here.
result = 0
coins.reverse()

for i in coins:
    result += k // i # 해당 동전 (i) 몇 개 쓸 수 있는지
    k = k % i# 남은 금액 갱신(기존 k 에서 i로 나눈 나머지)

print(result)

 

연속 부분 합의 최댓값 구하기 2

DP를 이용해야 할 것 같은데, 문제는 내가 DP를 모른다는 것..

1. 지금까지 최대 부분합과 현 위치 기준 연속된 부분합 명시 

• max_sum: 지금까지 찾은 최대 부분합
• current_sum: 현재 위치까지의 연속된 부분합

2. 현재 위치 i의 값(arr[i])을 이전까지 누적한 current_sum에 더할지, 아니면 끊고 여기서부터 새로 시작할지를 판단

3. 현재까지의 최대합을 갱신

 

n = int(input())
a = list(map(int, input().split()))

# Please write your code here.
# 이문제는 카데인 알고리즘으로 풀면 됨

max_sum = a[0] # 최댓값을 첫번째 원소로 지정
current_sum = a[0] # 누적합도 우선 첫번째 원소로 지정

for i in range(1,n):
    current_sum = max(a[i], current_sum + a[i])
    max_sum = max(max_sum, current_sum)

print(max_sum)