그리디 알고리즘
그리디 알고리즘이란 탐욕적인 방법으로 현재 상황에서 최선의 선택을 하는 것이다. 매 순간 가장 좋은 것을 택하며 나중에 미칠 영향은 생각하지 않는다. 이 유형의 문제는 암기를 떠나 창의력, 즉 문제를 풀기 위한 아이디어를 떠올릴 수 있는 능력을 요구한다.
대표적인 연습 문제로 '거스름돈' 문제가 있다. 이 문제는 가장 큰 화폐의 단위부터 거슬러 주며 최소의 동전만 사용하는 게 해결책이다.
그리디 알고리즘의 정당성
거스름돈 문제에서 그리디 알고리즘으로 최적의 해를 찾을 수 있는 이유는
✨큰 단위가 작은 단위의 배수이기 때문이다.
작은 단위를 여러번 반복하지 말고 큰 단위로 해결한 후 작은 단위를 이용하거나, 큰 단위로 해결할 수 있도록 작은 단위를 최소한으로 이용한 후 큰 단위를 이용하는 것이다.
대부분의 그리디 알고리즘 문제는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.
실전 문제
💡큰 수의 법칙
n, m, k = map(int, input().split())
numList = list(map(int, input().split()))
numList.sort(reverse=True)
#가장 큰 수가 더해지는 횟수
cnt = int(m/(k+1)) * k
cnt += m % (k+1) #m이 k+1로 로 나누어 떨어지지 않는다면
ans = 0
ans += cnt * numList[0] #큰 수 더하기
ans += (m-cnt) * numList[1] #두 번째로 큰 수 더하기
print(ans)이 문제는 합이 최대인 m길이의 리스트를 만들면 된다.
가장 큰 수 k번 + 두 번째로 큰 수 1번 -> 이 수열이 반복되는 게 중요하다.
✨(가장 큰 수가 더해지는 횟수 * 가장 큰 수) + ((m - 가장 큰 수가 더해지는 횟수) * 두 번째로 큰 수)를 구하면 정답이다.
88885888858 에서 마지막 1개의 8처럼 m이 k+1로 나누어 떨어지지 않을 때도 고려하여 cnt % (k+1)를 더하는 것이다.
💡숫자 카드 게임
n, m = map(int, input().split())
ans = 0
for _ in range(n):
cardList = list(map(int, input().split()))
minCard = min(cardList) # 입력 받으면서 최솟값 빼내기
ans = max(ans, minCard) # 둘 중 더 큰 값을 대입
print(ans)✨행을 입력 받을 때 최솟값을 뽑아 그 중 최댓값을 구하면 된다.
ans에 행의 최솟값을 대입하고, 다음 리스트를 입력 받으면 그 리스트의 최솟값과 비교하여 더 큰 값을 대입하는 방식이다.
💡1이 될 때까지
n, k = map(int, input().split())
cnt = 0
while True:
target = (n//k)*k #k의 배수로 만들기
cnt += (n-target) #target과 n의 차이만큼 카운트(1빼는 연산 카운트)
n = target #n을 k의 배수로 만들기 위해
if n < k: #더 이상 나눌 수 없을 때 탈출
break
cnt += 1 #나눌 수 있다면 나누고 카운트
n //= k #n값 변경
cnt += (n-1) #남은 수에서 1씩 빼기
print(cnt)💡거스름돈과 비슷하면서 다른 문제라고 느껴졌다. 이 문제는 n이 k의 배수가 될 때까지 1씩 빼는 과정을 반복해야 한다.
즉, 거스름 돈은 큰 금액만큼 빼고 작은 금액을 빼면 그만이지만 이 문제는 빼고 나누고 빼고 나누고를 반복하는 경우가 생기는 것이다.
(이 포인트에서 방황했거든 내가(￣y▽,￣)╭ )
위 코드는 배수로 만들기 위해 1을 빼는 과정을 반복하지 않고 한 번에 빼기 위해 나머지 연산자를 이용했다. 나머지만큼 1씩 뺀다면(카운트 한다면) 보다 효율적인 코드가 된다.
- 배수 만들기(1씩 빼는 연산)
- n < k라면 탈출
- 아니라면 k로 나누는 연산
이 과정을 반복한 후 2번에서 탈출한 수, 남은 수에서 1씩 빼는 연산을 1이 될 때까지 해주면 된다.
