동빈나 2021 이코테_2-1. 그리디 알고리즘

그리디 알고리즘란, 현재상황에서 지금 당장 좋은것만 고르는 방법을 의미한다.

즉 단순히 가장 좋아보이는것을 반복적으로 선택해도 최적의 해을 구할수 있는지 검토하는것이 중요하다.

 

예제문제1) 거스름돈문제 _ 가장 적은 개수의 돈으로 거스름돈을 줄수있는 방법은?

거스름돈 문제를 그리디해법으로 풀었을때(가장 큰 화폐단위부터 돈을 거슬러주는것)이 최적의 해를 보장하는 이유는?

 

가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수이므로 작은단위의 동전들을 종합해 다른 해가 나올 수 없기 때문

만약 800원을 거슬러 주어야 하는데 화폐단위가 500, 400, 100원이라면 이때는 그리디해법을 적용할 수 없다

 

예제문제2) 1이 될때까지

정당성분석 : K가 2이상이기만 하면, K로 나누는것이 1을 빼는것보다 항상 빠르게 N을 줄일 수 있기때문에 가능하면 최대한 많이 나누는방법이 최적의 해를 보장할 수 있다.

내 코드:

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

while n != 1:
    remain = n % k
    if remain == 0:
        n = n // k
        count += 1
    else:
        n -= 1
        count += 1

print(count) 
        

동빈나님 코드

 예제문제3) 곱하기 혹은 더하기로 가장 큰 수를 만들기

문제해결 아이디어 : 연산되는 두 수중에서 하나라도 0이나 1인 경우에는 곱하기보다 더하기를 하는것이 더큰답을 만듬

내코드

num = input()

array = [int(i) for i in num]
result = 0

for i in array:
    if i <= 1 or result == 0:  # i가 0또는 1일때는 더하기 수행
        result += i
    else:
        result *= i

print(result)
    

동빈나님 코드

현재상태에서 A조건이 맞다면 A를 수행하고, 그렇지않다면 B를 수행하는 구조 : 전형적인 그리디 구조