그리디 알고리즘

출처:
- 이것이 취업을 위한 코딩테스트다 with Python
- https://youtu.be/5OYlS2QQMPA

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방식
• 지금 당장 좋은 것만 골라도 최적해가 나올 수 있는 문제를 풀 때 적합
• 전체 경우의 수를 고려해서 최적해를 구해야하는 문제를 풀 때는 부적합

그리디 알고리즘이 부적합 문제

• 문제: 루트 노드부터 시작하여 거쳐가는 노드의 합을 최대로 만들고자 할 때, 최대의 값은 무엇인가?
• 최적해는 21 (5 -> 7 -> 9) 인 데, 그리디 알고리즘을 적용하면 19 (5 -> 10 -> 4)가 나와 최적해를 구할 수 없음
• 지금 당장 좋은 것을 골라도, 다음 단계에서 역전 가능성이 있으므로 그리디 알고리즘에는 부적합

최적해: 21 (5 -> 7 -> 9)	그리디 알고리즘을 적용한 경우: 21 (5 -> 10 -> 4)

문제

예제1. 거스름돈(하)

• 문제: 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야할 돈이 N원일 때 거슬러 주어야할 동전의 최소 갯수를 구하시오. 단, 거슬러 줘야할 돈 N은 항상 10의 배수입니다.
• 그리디 알고리즘으로 답을 구할 수 있는 이유: 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
• 만약 800원을 거슬러 줘야 하는 데, 동전의 단위가 500, 400, 100이라면 그리디 알고리즘으로 해를 구할 수 없음

n = 1260
count = 0

coins = [500, 100, 50, 10]

for coin in coins:
    count += n // coin
    n %= coin
    
print(count)

실전1. 큰 수의 법칙(하)

출처: 이것이 취업을 위한 코딩테스트다 with Python p92

# n = 5
# m = 8
# k = 3
# arr = [2, 4, 5, 4, 6]
n = 5
m = 7
k = 2
arr = [3, 4, 3, 4, 3]

arr.sort(reverse=True)

answer = 0
if arr[0] == arr[1]:
    answer = arr[0] * m
else:
    answer = arr[0] * k * (m // k) + arr[1] * (m % k)
print(answer)

실전2. 숫자 카드 게임(하)

출처: 이것이 취업을 위한 코딩테스트다 with Python p96

# arr = [[3, 1, 2], [4, 1, 4], [2, 2, 2]]
arr = [[7, 3, 1, 8], [3, 3, 3, 4]]

answer = list(map(min, arr))
answer.sort(reverse=True)
print(answer[0])  

실전3. 1이 될 때까지(하)

출처: 이것이 취업을 위한 코딩테스트다 with Python p99

# n = 17
# k = 4
n = 25
k = 5
count = 0

while n > 1:
    if n % k == 0:
        count += 1
        n //= k
    else:
        count += (n % k)
        n -= (n % k)

print(count)

기타

python 문법 알게 된 것

• 몫 구하기 연산자는 /이 아니라 //이다. 
  /을 할 경우 소숫점까지 반환하고, //을 해야 몫이 나온다
• 오름차순 정렬을 할 경우, [1, 2, 3].sort(reverse=True)로 하면 된다.
  python 함수 호출 시 쓰고 싶은 옵션을 키 값으로 넣으면 되는 것 같다. (굳이 더미 파라미터 넣을 필요없음)
• map을 한 리스트를 얻으려면 list(map(func = 실제함수, arr = 리스트))하면 된다.