[이것이코딩테스트다] ch3 그리디 (Greedy)

 

✅ 그리디 Greedy

• 현재 상황에서 지금당장 좋은것만 고르는 방법
• 문제에서 ‘가장 큰 순서대로’, ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해줌
  • 자주 정렬 알고리즘과 짝을 이뤄 출제됨

 

---

 

✅ 예제 3-1 : 거스름돈

카운터에는 거스름돈으로 시용할 수 있는 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.

손님에게 거슬러 줘야할돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.

단, 거슬러 줘야 할 돈 N은 항상 10 의 배수이다.

 

✔️ 알고리즘만 떠올리기

가장 큰 동전의 값부터 최대한 거슬러 주면 동전의 최소개수를 구할 수 있다.

 

✔️ 파이썬에서 기억해야 할 점

/ : 결과를 float으로 반환

// : 결과를 int 로 반환

 

 

💻 CODE

n = 1260
moneys = [500,100,50,10]

result = 0
for money in moneys:
    result += (n // money) # 1260 // 500 = 2 
    n %= money# 1260 % 500 = 260

print(result)

 

• 찾은 해법이 정당한지 검토해야 한다
• 가지고 있는 화폐의 단위가 500 100 50 10이여서 가능한 코드
• 만약 800원을 거슬러줘야하는데 화폐의 단위가 500 400 100이면?
• 400 400 - 2개만으로 가능한데 위의 알고리즘으론 500 100 100 100 4의 결과가 나올수 있음.

 

 

✅ 실전예제 2 : 큰수의법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을
M번 더하여 가장큰수를만드는 법칙이다.
K번을 초과해 더할 수 없다.

2 4 5 4 6 배열에서 M이 8이고, K가 3이라고 가정
6 6 6 5 6 6 6 5 = 46

서로 인덱스가 다른 위치에 존재하면 수가 다른것으로 간주
3 4 3 4 3, M=7, K=2
4 4 4 4 4 4 4 = 28
>> 1,3 index에 위치하는 4를 두번씩반복

 

✔️ 알고리즘만 떠올리기

• 먼저 내림차순 정렬을 한다. 
• 6 5 4 4 2
• 최대 사용할 수 있는 K만큼 index-0번을 사용
• index-1(두번째로 큰수)를 한번 더해준다
• 만약 가장큰수와 두번째로 큰 수의 값이 같아도 결국 똑같은 결과가 나온다. 

 

💻 CODE 

책 정답코드를 안보고 일단 작성해본 코드이다.

import sys
input = sys.stdin.readline 

n, m, k = map(int, input().split())

numList = list(map(int,input().split()))

numList.sort(reverse=True)

firstBig = numList[0]
secondBig = numList[1]

sumValue = 0
count = m

while True:
    if(count <= 0):
        break

    if (count >= k+1):
        sumValue += (firstBig*k + secondBig) 
        count -= (k+1)
    else : # 1 <= count <= k 마무리 처리!
        sumValue += (firstBig*count)
        break


print(sumValue)

 

 

책에는 while문 조차를 개선하는 방법이 나와있다! 

• 반복문을 몇번 처리할것인가? 
• 결국 m 을 k+1로 나누어 떨어지는 횟수만큼 반복해주면 된다.  

 

💻 개선된 CODE 

반복문을 제거했다!

import sys
input = sys.stdin.readline 

n, m, k = map(int, input().split())

numList = list(map(int,input().split()))

numList.sort(reverse=True)

firstBig = numList[0]
secondBig = numList[1]

sumValue = 0
count = m // (k+1)
remind = m % (k+1)


sumValue += (firstBig*k + secondBig) * count
sumValue += (firstBig * remind )

print(sumValue)

 

 

✅ 실전예제 3 : 숫자 카드 게임

 

여러개의 숫자 카드 중 가장 높은 숫자가 쓰인 카드를 한장 뽑는 게임
1. 숫자는 N*M 형태
2. 뽑으려는 카드가 포함된 행선택
3. 선택된 행에 포함된 가장 숫자가 낮은 카드 선택
4. 처음에 카드 골라낼 행 선택시 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을것을 고려해서
 최종적으로 가장 높은 숫자의 카드를 뽑아보자.

 

💻 CODE 

import sys
input = sys.stdin.readline

n,m = map(int,input().split())

result = 0
for i in range(n):
    cards = list(map(int,input().split()))
    result = max(result,min(cards))

print(result)

 

✅ 실전예제 4 : 1이 될 때 까지

N이 1이 될 때까지 다음의 두과정중 하나를 반복적으로 선택해 수행하려고 함
단 2번째 연산은 N이 K로 나누어떨어질 때만 선택 가능

1) N에서 1을 뺀다
2) N을 K로 나눈다.

N이 1이 될때까지의 최소 횟수를 구하는 프로그램을 작성하라
2 <= N, M <= 100000

💻 정답 CODE

이건 문제 이해를 잘못해서 코드 이해하는데도 시간이 걸렸다 ㅠㅠ 다시 풀어보기! 

import sys
input = sys.stdin.readline

n, k = map(int,input().split())

result = 0

# n이 k의 배수가 될 때까지 1을 빼줘야함 

while True:
    target = (n//k)*k
    result += (n-target)
    n = target

    if n < k:
        break

    #k로 나누기
    result += 1
    n //= k

result += (n-1) 
print(result)​

 

 

 

원래 오늘 챕터4까지 하려고 했는데 못해서

 내일 좀더 시간을 투자해서 풀어봐야겠다.