Python - 그리디 알고리즘 정복하기 1탄

1. 그리디 알고리즘

greedy는 탐욕적이란 뜻이므로, 탐욕법이라고도 한다.

즉, 탐욕적으로 문제를 푸는 알고리즘이라는 뜻이다.

여기서 탐욕적이란게 문제를 풀때 현재 상황에서 가장 좋은 것만 고르는 방법을 말한다.

현재의 상황만 고려하고, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는게 큰 특징이다.

 

일단, 그리디 알고리즘이 유형은 다양하고, 많은 문제를 풀면서 사전 지식이 필요한 문제와 없는 문제를 구별해서 풀어야한다. 특히나, 창의력과 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 갖춰야 한다.

 

비슷한 알고리즘으로는 최단 경로를 빠르게 찾아야 하는 '플로이드 워셜 Floyd-Warshall' 혹은 '다익스트라Dijkstra' 알고리즘이 있다.

 

---

1. 그리디 - 거스름돈

1280원이라는 돈이 있다고 가정하자.

이 돈을 500원, 100원, 50원, 10원으로 거슬러 주려고 한다.

그럼 필요한 동전의 총 개수는?

 

n = 1280

count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin
    n %= coin

print(count)

500원 x 2 , 100원 x 2, 50원 x 1, 10원 x 3

 

2 + 2 + 1 + 3 = 8개

 

result =>

간단한 예 : 시간 복잡도 O(k)

시간 복잡도는 화폐의 종류만큼 반복해야 하기 때문에, 동전의 전체 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다.

 

---

2. 그리디 - 큰 수의 법칙

배열에서 주어진 수들을 m번 더하여, 가장 큰 수를 만드는 알고리즘이다.

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 k번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

 

예를 들어, 2 4 5 4 6 으로 이뤄져 있는 배열이 있다.

m이 8이고, k가 3이라고 하자.

 

가장 큰 수 : 6 , 두번째로 가장 큰 수 : 5

6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 6*6 + 5*2 = 46 이다

 

그리고 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

처음 이 조건을 받아들이는게 이해가 되지 않았다.

왜냐하면 같은 수가 나왔는데 제거하는게 맞나 싶었는데, 조건이 이렇다면 따르자.

 

즉, 4 5 4 5 4 로 이뤄져 있는 배열이 있을 때, m이 7이고, k가 2라고 가정하자.

 

이 경우, 두 번째 원소에 해당하는 5와 네 번째 원소에 해당하는 5를 번갈아 두 번씩 더하는 것이 가능하다.

 

결과적으로 5가 7번 더해지는, 5 + 5 + 5 + 5 + 5 + 5 + 5 인 35가 도출된다.

---

배열의 크기 N, 숫자가 더해지는 횟수인 M, 그리고 K가 주어질 때 , 큰 수의 법칙에 따른 결과를 출력해보는 문제를 풀어보자.

 

입력 조건 : 첫째 줄에 N( 2<= N <= 1,000) , M(1 <= M <= 1,000), K(1 <= K <= 10,000) 의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.

 

둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단 각각의 ㅏㅈ연수는 1 이상 10,000 이하의 수로 주어진다.

 

입력으로 주어지는 K는 항상 M보다 작거나 같다.

 

출력 조건 : 첫째 줄에 큰 수의 법칙에 따라 더해진 답을 출력한다.

 

입력 예시 :  

5 8 3

1 3 5 4 6

 

출력 예시 : 

46

---

* break, continue 문 차이점 :

 break 은 for 과 while과 같이, 제어 루프에서 벗어남, 완전히 벗어나는 것임. 

continue 는 제어(반복) 흐름을 유지한 상태에서 해당 코드의 실행만 건너뛰는 역할을 수행

 

break문을 쓰다보면, 어디에서 영향을 미치는지 헤깔렸는데 다음 예시를 보고 해결되었다.

k = 0

while True:
    for i in range(50):
    	k += 1
        
    	if i == 5: # i가 5일 때, 반복문을 끝냄, 여기서는 for문
        		break
            
            
    if k == 10:
        break # k가 10일때 while문을 끝냄

 

이제 문제를 푼 코드이다.

참고로 입력 값은 data와 data1 으로 구분해놓은 이유가, 초기에 받은 값이 정렬되는 과정을 보고 싶어서이다.

 

가독성을 위해서 리스트를 복사할때,

1번 : data2 = data1[:] 

2번 : data2 = data1.copy()

 

라는 방식이 있는데 2번을 써야한다는 것을 배웠다.

 

# n,m,k 공백으로 구분하여 받기
n,m,k = map(int, input().split())

# n개의 배열의 수들을 공백으로 구분하여 입력 받기
data = list(map(int, input().split()))


# 가장 큰 수와 작은 수를 나눠서 받기, sort 쓰면 리스트 형태 변환됨
# 기본이 reverse = False 이다
data1 = data.copy()
data1.sort()
first = data1[n-1] # 가장 큰 수
second = data1[n-2] # 두번째로 큰 수

result = 0

while True:
    for i in range(k): # 가장 큰 수를 k 번 더해주기
        if m == 0:
            break
        result += first
        m -= 1 # 더할때마다 m 은 1씩 감소
    if m == 0: # m이 0이라면 반복문 탈출
        break
    result += second # 두번째로 큰 수를 더해주기
    m -= 1 # 더할때마다 m은 1씩 감소
    
print(result)

 

사용된 변수들

 

물론 실제 코드에서는 data와 data1을 따로 구분할 필요는 없을 것이다

 

 

 

예를 들어, 8개의 연산에서 k가 3이기에

 

(~ + ~ + ~ + ~ ) + (~ + ~ + ~ + ~ ) 

 

이렇게 크게 두 덩어리로 4개의 합이 더해지는 모습이 나왔다.

 

 

하지만, m과 k가 한번에 떨어지지 않는 경우도 생길 수 있다. 

 

그럴땐 위의 코드가 작동하지 않을 것이다.

 

즉, m이 k+1 로 나누어 떨어지지 않는 경우에서는 k+1 로 나눈 나머지만큼 가장 큰 수가 추가로 더해지는 상황이 생긴다.

 

즉, 가장 큰 수가 더해지는 횟수를 구해야한다.

 

 

m이 8이고 k가 4라고 가정해보고, 가장 큰 수가 6이고 두번째로 큰 수가 5일때

 

( 6 + 6 + 6 + 6 + 5 )  + (6 + 6 + 6 ,..)

 

마지막에 가장 큰 수가 더해지는 경우가 3번인게 나와야 된다.

기존의 더해지는 횟수 4번에서 + 3번인게 나와야 하므로,

 

 

 

 

 

# n,m,k 를 공백으로 구분하여 받기
n,m,k = map(int, input().split())

# n개의 수를 공백으로 구분하여 받기
data = list(map(int, input().split()))

data.sort(reverse=True)

first = data[0] # 가장 큰 수
second = data[1] # 두번째로 큰 수

# 가장 큰 수가 더해지는 횟수 계산
count = int(m /(k+1)) * k
count += m % (k+1)

result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m-count) * second # 두번째로 큰 수 더하기

print(result)

 

결과는 46이다

 

---