알고리즘 - 그리디 알고리즘

 

https://youtu.be/2zjoKjt97vQ?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 

 

그리디 - 탐욕적인 이라는 뜻을 가지고 있으며 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

그리디 해법 - 정당성 분석이 중요하다. (-> 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.)

 

[문제 상황]

실제 최대 값을 만드는 경로 

 

실제 그리디 알고리즘을 이용해서 최대값을 찾을 때의 경로

<그리디 알고리즘이 최적의 해를 보장하지 않는 이유는?>

그리디 알고리즘은 최적의 해를 보장할 수 없다고 하는 이유는 노드마다 가장 큰 값을 선택할 때 5->10->4 이런식으로 가게 되어서 19가 그리디로 찾은 값이고 진짜로 가장 큰 값인 5->7->9의 값인 21보다 작기 때문에 최적의 해를 보장할 수 없을 때가 많다고 설명한다.

 

 

<코테에서 그리디(탐욕법) 알고리즘이 나올 땐 최적의 해가 될 경우를 의도해서 출제한다.>

코딩테스트에서는 그리디를 사용해서 문제를 출제할 경우 최적의 해가 될 경우를 의도해서 출제자가 문제를 내는 경우가 많기 때문에 이를 염두해두어야 한다.

 

---

대표적인 그리디 알고리즘의 문제

1260원이 0원이 될 때까지 500원부터 거슬러 주어야 한다.

 

#거스름 돈: 답안 예시

n = 1260
count = 0

array = [500,100,50,10]

for coin in array:
    count += n//coin #해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin #나눈 값이 나머지 값으로 갈 수 있게 1260-1000 = 260인 경우를 반
print(count)

<문제의 시간 복잡도 분석>

• 화폐의 종류만큼만 반복을 수행하면 되기 때문에 시간 복잡도는 화폐의 개수인 O(K)이다.
• 이 알고리즘의 시간 복잡도는 거슬러주어야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.

---

<문제: 1이 될 때까지>

 

#1이 될 때까지

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

while True:
    #n이 k로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n//k)*k
    cnt += (n - target)
    n = target

    #n이 k보다 작을 때 (더이상 나눌 수 없을 때) 반복문을 탈출
    if n < k:
        break
    #k로 나누기
    cnt += 1
    n//=k
    
#마지막 남은 수를 1씩 빼주기
cnt += (n-1)
print(cnt)

---

<문제: 곱하기 혹은 더하기 >

data = input()

#첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)): #1부터 data 길이까지
    num = int(data[i])

    #두 수 중에서 하나라도 0또는 1인 경우는 곱하기보다는 더하기 수행을 해주는 것이 낫다.
    if num <= 1 or result <=1:
        result += num
    else:
        result *= num
print(result)

---