그리디 알고리즘(탐욕법)

• 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.
• 그리디 해법은 정당성 분석이 중요하다 -> 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 보장 할 수 있는지 검토한다.
  탐욕적으로 현재 상황에서 가장 좋은 방법을 고르고 그 과정에서 최적의 해를 구할 수 잇는지 검토하는 과정이 필요

---

이 문제의 경우 최적의 값은 5 -> 7 -> 9로
21이 최적의 값이지만
매 상황에서 가장 큰 값만 고른다면(그리디)
5 -> 10 -> 4로 19가 나온다.
(결론)
일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장하지 않는다. 하지만 코딩테스트에서는 입력값과 출력값을 정하는 경우가 많아 그리디 알고리즘으로 분류되는 문제는 단순히 그리디 알고리즘으로 풀어도 최적의 해가 나오는 경우가 많다.

---

손님에게 1260원을 거슬러줘야한다고 하면
가장 큰 단위의 화폐부터 차례로 거슬러준다면 최적의 해이다.
왜 그런지 정당성 분석을 해보자.
-> 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 ( 500원 100원 50원 10원 ) 작은 단위의 동전을 종합해 다른 해가 나올수 없기 때문에다.

만약?
800원을 거슬러 줘야하는데 화폐 단위가 500,400,100이면?
500이 400원의 배수가 아니다 조합을 통해 다른 해가 나올 수 있다.
800원
500원 100원 100원 100원 -> 4개
400원 400원 -> 2개

따라서 이 문제는 그리디 알고리즘으로 풀 수 없는 문제이다 (왜? 최적의 해를 보장하지 않아서 <- 정당성 분석)

---

큰수의 법칙

코드

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

result = 0
data.sort(reverse=True)
a = m // (k + 1) * k + (m % (k + 1))
result += data[0] * a
result += data[1] * (m - a)

print(result)

과정

1. 처음 생각

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

result = 0
data.sort(reverse=True)
a = m // k
b = m % k

result += data[0] * k * a
result += data[1] * b

print(result)

입력값이
5 8 3
2 4 5 4 6
이라고 하면
6 6 6 5 6 6 6 5 이렇게 더해야한다.
k가 3이기 때문에 6 3번 반복 5 한번 또 6 3 반복 5
이렇게 나오는걸 보고 8을 3으로 나눈값의 몫만큼 가장 큰수를 반복하고 나머지만큼 두번째로 큰수가 더해지는구나 라고 생각했다

문제점

1)
하지만 만약
5 9 3
2 4 5 4 6
라면 m이 k에 나누어 떨어진다면 큰수만 9번 반복하게 된다.
위에 코드가 출력값을 잘 뱉은 이유는 그냥 운이였다....
(입력 출력 예시값이 더 있다면 좋았을텐데)

2)
5 8 5
2 4 5 4 6
이것도 8/5 는 1
6 6 6 6 6 5 5 5 이렇게 더해진다...
6 6 6 6 6 5 6 6 (원래라면)

2. 두번째 생각

위에 두 문제점을 고려해 다시 생각해봤다.
1)
5 8 3
2 4 5 4 6
6 6 6 5 // 이렇게 하나의 그룹으로 치환해서 생각해보자
6k(8/4) = 6 6 6 6 6 6
5*2= 5 5

2)
5 9 3
2 4 5 4 6
6 6 6 5 6 6 6 5 6
63(9/4) = 6 6 6 6 6 6 (6번)
5*(9/4)=5 5 (2번)

총 8번으로 6이 한번 더 반복되어야한다.
그렇다면 나머지를 이용하면 어떨까?
9%4=1 을 이용해
3(k)*(9/4)+(9%4) = 7

3)
5 8 5
2 4 5 4 6
6(5(k)(8/6)+(8%6))= 6 6 6 6 6 /5/ 6 6
5*(8/6)= 5

---

숫자 카드 게임

코드

n, m = map(int, input().split())
result = []
for i in range(n):
    result.append(min(list(map(int, input().split()))))

print(max(result))

과정

1. 각 행에서 가장 작은 숫자를 뽑고 그 중에서 가장 큰수를 찾는다.
   1)
   3 3
   3 1 2
   4 1 4
   2 2 2

각 행을 list로 받을때마다 최소값을 result에 보관
result중 가장 큰 값을 찾음

---

1이 될 때까지

코드

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

result = 0

while (n >= k):
    if (n // k > 0):
        result += n % k
        n = n // k
        result += 1

while n > 1:
    if n == 1:
        break
    n = n - 1
    result += 1

print(result)

1. N에서 1을 뺀다
2. N을 K로 나눈다(나누어 떨어지면)
   둘중 선택
   1이 되면 끝

과정

1)
25 5
25 -> 5 -> 1

2)
25 3
25 -> 24 -> 8 -> 7 -> 6 -> 2 -> 1

25/3 = 8 25%3 = 1
8/3=2 8%3=2
2-1=1

우선 나누고 나머지를 더한다
그리고 나눠야하는 값이 k 보다 작으면 1이 될때까지 1을 뺀다.

---

참고 문서
이것이 코딩테스트다 - 나동빈