[WEEK04] DAY27, 28

DAY27

2021.11.27 SAT

일요일까지 다 훑기
월요일 문제 제대로 다 이해하기 (팀리뷰)
화요일 수요일 지금까지 알고리즘 주제 복습하기

• 그리디 : 문제를 풀어나가는 과정, 단계에 있어서 이 단계에서 가장 좋은게 뭔지 보고 가장 좋은 것을 선택하는 것
• 그리디 문제는 정렬 후 차근차근 선택해나감. 대부분의 그리디 문제는 정렬과 동반해서 풀어나감.

https://blog.naver.com/ndb796/221242106787
여기서 ‘그리디 알고리즘은 기본적으로 무조건 큰 경우대로, 무조건 작은 경우대로, 무조건 긴 경우대로, 무조건 짧은 경우대로 등 극단적으로 문제에 접근한다는 점에서 정렬(Sort)기법이 함께 사용되는 경우가 많습니다.’ 라는 글을 읽고 이해가 되었다. 아, 그래서 정렬이 함께 따른다는 거구나.

그리디 알고리즘 > 결국은 내가 생각하는 문제 해결 방법이 내 생각엔 최적의 해결법이 아닌가? 뭐가 최고로 좋은지 나 혼자서는 어떻게 판단할까 생각했는데

그리고 코치님께서 답변을 주셨다.

"그것이 최선이라고 말하고싶다면 다른 방법들이 최선이 아니라는 것을 증명해야 한다"

.
.

DAY28

2021.11.28 SUN

동전문제들 해결

9084 동전 (DP)

코드

import sys
input = sys.stdin.readline

testcase = int(input())
for _ in range(testcase):
    n = int(input())
    coins = list(map(int, input().split()))
    m = int(input())

    dp = [0] * (m + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(m + 1):
            # a_(i-k) 를 만드는 방법이 존재한다면 
            # 이전 경우의 수에 현재 동전으로 만들 수 있는 경우의 수를 더한다.
            if i >= coin:
                dp[i] += dp[i - coin]

    print(dp[m])

11047 동전0 (그리디)

이건 문제만 제대로 읽으니 쉬웠다

코드

import sys
n, money = map(int, sys.stdin.readline().split())

coins = []
for _ in range(n):
    coins.append(int(sys.stdin.readline()))
coins.sort(reverse=True)

count = 0
for coin in coins:
    if coin == 0:
        break
    count += money // coin
    money = money % coin # 남은 잔액

print(count)

정답은 나왔는데
K가 동전금액들보다 작은 경우 큰금액부터 도는게 비효율적이니
K가 동전보다 작을 경우 continue(패스 or pop)하는 조건을 걸어주면 더 좋을 것 같다