탐욕 알고리즘

• 매 순간 최적인 값을 고르는 방식
• 문제를 이해하고 단순히 현재 상황에서 가장 좋아보이는 것만을 선택해도 문제를 풀 수 있는지 파악해야한다.
• '가장 큰 순서대로', '가장 작은 순서대로'라는 기준이 숨어있다. 대체로 정렬알고리즘과 함께 사용된다.

문제1. 거스름돈

내 풀이

# 손님에게 거슬러줘야 할 돈이 n원일 때 거슬러줘야할 동전의 최소 개수를 구하시오 (500원, 100원, 50원, 10원 짜리 동전 사용)

def change(coin_list, price, pay):
    coin_list = [10, 50, 100, 500]
    coin_list.sort(reverse=True) #원본리스트를 역순정렬

    check_list = {}
    change = pay - price
    coin_count = 0

    for coin in coin_list:
        num = change // coin # 4700/500의 몫이 num에 저장
        change -= num * coin
        coin_count += num
        check_list[coin] = num

    return coin_count

print(change([10,50,100,500], 740, 2000))

더 나은 풀이

n = 1260
count = 0

# 큰 단위 화폐부터 차례대로 확인
list = [500,100,50,10]

for coin in list:
count += n // coin # 해당 화폐로 거슬러줄 수 있는 동전의 개수 세기
n %= coin

print(count)

---

문제2. 큰 수의 법칙

내 풀이

첫 번째 접근

# 큰 수의 법칙
# 아이디어 : 입력값 중에 가장 큰 수와 두 번째로 큰 수만 저장해서, 가장 큰 수를 k번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복하면 된다


# 최대숫자 구하기
def the_biggest(m, k, nums):
    # nums를 정렬해서 가장 큰 수와 두 번째로 큰 수를 저장
    nums.sort()
    max_num = nums[-1]
    second_num = nums[-2]


    # 결과값을 저장할 total, 조건문의 기준이 되는 count 변수 선언
    total = 0
    count = True

    # m이 0이 될때까지 반복
    while m:
        #count가 True면 max_num * k를 더하기
        if count:
            total += max_num * k
            count = False
            m -= k
        #count가 False면 second를 한 번 더하기
        if not count:
            total += second_num
            count = True
            m -= 1

    return total


n, m, k = 5, 8, 3

nums = [2, 4, 5, 4, 6]

print(the_biggest(m, k, nums))

m이 0이 될 때까지 반복하면서, count를 True와 False로 나누면서 True일 때는 가장 큰 수를 k 곱한 값을 더하고 False일 때는 두번째 값을 한 번 씩 더해주었다.
이렇게 코드를 짤 경우 m이 k+1로 나누어떨어지지 않을 때는 올바른 값이 리턴되지 않는다.

두 번째 접근

다시풀어보세요

더 나은 풀이

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

data.sort()
first = data[n-1] # 첫 번째로 큰 수
second = data[n-2] # 두 번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산 (4442444244)
count = int(m//(k+1))*k #444가 2번 더해짐
count += m % (k+1) # 나머지 4를 더해서 총 6+2

result = 0
result += (count) * first # 가장 큰 수 * count
result += (m-count) * second # 두 번째로 큰 수 * 전체-count

print(result)

k가 총 출력되어야 할 횟수를 먼저 계산해주고 result를 따로 구하는 방식으로 코드를 짰다. 코드가 더 간결해지는 것 같다.

---

문제3. 숫자 카드 게임

내 풀이

# 숫자 카드 게임
# 주어진 행 중에 한 개의 행을 선택하면 자동적으로 해당 행에서 가장 작은 숫자를 얻게 된다. 가장 큰 수를 얻도록 알고리즘을 짜로 얻은 수를 리턴해라
# 아이디어 : 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것

# n은 행의 개수, m은 열의 개수
n, m = 2, 4
cards = [[7, 3, 1, 8], [3, 3, 3, 4]]

def cards_game(n, cards):
    min_cards = []

    for i in range(n):
        min_num = min(cards[i])
        min_cards.append(min_num)

    return max(min_cards)

print(cards_game(2, cards))

더 나은 풀이

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

result = 0

for i in range(n):
	data = list(mpa(int, input().split()))
	min_value = min(data)
	result = max(result, min_value)

print(result)

한 줄 씩 입력을 받는다는 부분이 내 코드와 다르긴 하지만 각 행의 최소값을 찾고 그것들의 최대값을 찾는 방법은 똑같다.

---

문제4. 1이 될 때까지

내 풀이

# 1일 될 때 까지
# 최대한 많이 나누는 것이 최적해를 보장한다.

n, k = 25, 3
count = 0

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

n이 k로 나누어질 때까지 -1해주고 나누어떨어지면 1일 될 때까지 k로 나눔

더 나은 풀이

n, k = mpa(int, input().split())
result = 0

while True:
	# (n == k로 나누어떨어지는 수가 될 때까지 1씩 빼기)
	target = (n // k) * k
	result += (n - target) # 1씩 빼야하는 횟수를 result에 저장
	n = target
    
	# n이 k보다 작아지면 탈출
	if n < k:
	break
	
    #횟수 1씩 늘리고 k로 나눈 몴을 다시 n에 저장
	result += 1
	n //= k

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

코드가 잘 이해가 안됨... target을 k의 배수로 만들어서 n-target을 횟수에 추가하고 target을 k로 반복해서 나누면서 횟수를 카운트한 것 같은데 마지막에 왜 n-1을 result에 더하는지 모르겠다..!

✍문제 출처 (자세한 문제는 아래 서적에서 확인하실 수 있습니다.)
이것이 코딩테스트다, 나동빈, 한빛미디어