그리디 알고리즘

코테에서 나오는 그리디 문제들은 탐욕법으로 나오는 해가 답인 케이스라고 생각해야한다 !

그리디 알고리즘 예제

거스름 돈

최소개수를 구해야하니 가장 큰 단위의 동전부터 주는것이 최소의 수를 보장할것이라고 생각한다..!

그럼 영상에서 제시하는 해결아이디어를 보자

문제 해결 아이디어

이와같이 큰단위의 동전부터 전달해줘야한다 !

정당성 분석

이와같이 그리디알고리즘 문제에서는 정당성 분석이 중요하다.

답

n=1260 
cnt =0 
arr = [500,100,50,10]

for coin in arr:
    cnt+=n//coin
    n%=coin 
print(cnt)

1이 될 때까지

나누기를 하는 케이스가 빼기를 하는 케이스보다 더 최소의 cnt를 가지게 할것이니 k의 배수일때 나눌수 있으면 나누고 못나누면 빼기를 해줘서 k의 배수까지 가게하는 방법을 찾으면 될것이라 생각한다.

이제 영상의 문제 해결 아이디어를 확인하자.

문제 해결 아이디어

정당성 분석

답

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

result = 0
while True:
    target = (n//k)*k
    result += (n-target)
    n = target 
    if n<k:
        break 
    result+=1
    n//=k 
result+=(n-1)
print(result)

target을 찾아주는 테크닉으로 풀어줄 수 있는 문제이다.

곱하기 혹은 더하기

아마.. 더하기 보다는 곱하기가 큰데 0이나 1이 오는 경우에는 곱하기보다 더하기가 더 큰 값을 가지게 하니 0,1일때만을 예외로 더하기로 하고 그외에는 곱하기 과정을 해주면 될것같다.

문제 해결 아이디어

답

data = input()

result = int(data[0])
for i in range(1,len(data)):
    num = int(data[i])
    if num<=1 or result<=1:
        result+=num 
    else :
        result *= num 
print(result)

모험가 길드

정렬을 진행하고 앞에서부터 공포도를 체크하며 그룹을 만들어 나가면 될것이다.

문제 해결 아이디어

답

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

result = 0
cnt = 0
for i in data:
    cnt+=1
    if cnt>=i:
        result+=1
        cnt=0 
print(result)

이처럼 그리디 알고리즘은.. 아이디어가 좋아야할것같다..
최적의 해가 나올거라는 확신...참 어렵다..