단순하지만 강력한 문제 해결 방법.
=> 현재 상황에서 지금 당장 좋은 것만 고르는 방법
<그리디 알고리즘 문제 출제 분석>
-
코테에서 만나게 될 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징
-
그리디 알고리즘의 유형의 문제는 매우 다양하기 때문에 암기한다고 해서 항상 잘 풀리는 것은 아님.
-
코테에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 다시 말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악해야 함.
-
그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 "가장 큰 순서대로", "가장 작은 순서대로"와 같은 기준을 알게 모르게 제시. => 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족 시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이룸
거스름돈
n = 2360
count = 0
#큰 단위의 화폐부터 차례대로 확인.
coin_types = [500, 100, 50, 10]
# // : 나누기 연산후 소수점 이하의 수를 버리고, 정수 부분의 수만 구함
for coin in coin_types:
count += n // coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)
<그리디 알고리즘의 정당성>
그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 것은 아님. 대부분이 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분하다.
따라서 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 함. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수 이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.
즉, 큰 단위가 작은 단위의 배수 형태이므로, "가장 큰 단위의 화폐부터 가장 작은 단위의 화폐까지 차례대로 확인하여 거슬러 주는 작업만을 수행하면 된다"는 아이디어는 정당하다.
어떤 코테 문제를 만났을때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민. 그 이후에 다이나믹 / 그래프 알고리즘을 생각
<큰수의 법칙>
일일이 다 하는 것보단 원리를 생각해 수열을 나열하여 해결
#n, m, k를 공백으로 구분하여 입력받기
n, m, k = map(int,input().split())
#N개의 수를 공백으로 구분하여 입력받기
data = list(map(int, input().split()))
data.sort() #인덱스 번호가 큰게 큰 값이 정렬되는구나 입력받은 수들 정렬하기
first = data[n-1]
second = data[n-2]
result = 0
while True:
for i in range(k): #가장 큰수를 k번 더하기
if m == 0: # m이 0이라면 반복문 탈출
break
result += first
m -= 1 # 더할 때마다 1씩 빼기
if m == 0 :
break
result += second # 두 번째로 큰 수를 한 번 더하기
m -= 1
print(result)<숫자 카드 게임>
n, m = map(int, input().split())
result = 0
for i in range(n):
data = list(map(int, input().split()))
#현재 줄에서 '가장 작은 수' 찾기
min_value = min(data)
'가장 작은 수'들 중에서 가장 큰 수 찾기
result = max(result, min_value)
print(result)<1이 될때 까지>
n, k = map(int, input().split())
result = 0
#n이 k 이상이라면 k로 계속 나누기
while n >= k :
#n이 k로 나누어 떨어지지 않는다면 n에서 1씩 빼기
while n % k !=0 :
n -= 1
result += 1
n //= k
result += 1
#마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
n -= 1
result += 1
print(result)
