[알고리즘 / 파이썬] 1. 그리디 (탐욕법) 알고리즘

1. 그리디(Greedy) 알고리즘

• 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달
• 탐욕 알고리즘은 최적해를 구하는데 사용되는 근사적인 방법이다.
• 자주 정렬 알고리즘과 짝을 이뤄 출제 된다.

   (!) 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만,

        그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서 최적이라는 보장은 없다.

 

1-1. 탐욕 알고리즘 문제 해결법

1. 선택 절차 (Selection Procedure)

→  현재 상태에서의 최적의 해답을 선택한다.

 

2. 적절성 검사 (Feasibility Check)

→ 선택의 해가 문제의 조건을 만족하는지 검사

 

3. 해답 검사 (Solution Check)

→  원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면

      선택 절차로 돌아가 위의 과정을 반복

1-2. 탐욕 알고리즘을 적용하기 위해 2가지 조건을 성립해야 한다.

1. 탐욕적 선택 속성 (Greedy Choice Property)

→ 현재의 선택이 나중에 미칠 영향에 대해서 고려하지 않는다.

 

2. 최적 부분 구조 (Optimal Substructure)

→ 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

• 이러한 조건이 성립하지 않는 경우에 탐욕 알고리즘은 최적해를 구하지 못한다.
• 위의 경우에도 근사 알고리즘으로 사용이 가능할 수 있으며, 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.
• 어떤 특별한 구조(매트로이드)가 있는 문제에 대해 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다.
• 매트로이드가 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에  활용도를 높여준다.

(!) 근사 알고리즘 (Approximation Algorithm)

• 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘
• 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며
  어느 정도 보장된 근사해를 계산할 수 있다.

e.g.1) 거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 
카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10짜리 동전이 무한히 존재한다고 가정한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하여라. 
(단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.)

문제 해설

• '가장 큰 화폐 단위'부터 돈을 거슬러 준다.
  즉, 500원 부터 거슬러 줄 수 있을 만큼 거슬러 준 후, 100원, 50원, 10원 차례대로 거슬러준다.

coins = [500, 100, 50, 10]

## 화폐의 종류가 K개라고 할때 아래 함수의 시간 복잡도는 O(K)이다.
## 아래 함수의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액의 크기와는 무관하다.

def change_count(change):
    cnt = 0

    for coin in coins:
        ## 거스름돈을 동전으로 나눈 몫만큼 카운트에 더해줌.
        cnt += change // coin

        ## 거스름돈을 동전으로 나눈 나머지만큼 남은 거스름돈으로 선언해줌.
        change %= coin

        print(f'coin : {coin}, change : {change} (cnt | {cnt})')

    return cnt

print(f'\ncount : {change_count(1260)}')

## 출력 결과
coin : 500, change : 260 (cnt | 2)
coin : 100, change : 60 (cnt | 4)
coin : 50, change : 10 (cnt | 5)
coin : 10, change : 0 (cnt | 6)

count : 6

• 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 배수이므로
  작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.
• 예를 들어 change = 800, coins = [500, 400, 100]인 경우그리디 알고리즘으로는
  (500 + 100 + 100 + 100)으로 4개의 동전이 필요하지만, 최적해는 (400 + 400)으로 2개의 동전만 필요하다.

coins = [400, 500, 200]

def change_count_fix(change, coins):
    ## coins를 내림차 순으로 정렬
    coins.sort(reverse = True)

    ## cnt 값들을 저장해줄 리스트 지정
    counts = []
    
    ## coins 리스트가 모두 비워질 때까지 반복 시켜줌.
    while len(coins) != 0:
        
        cnt, c = 0, change
        for coin in coins:
            cnt += c // coin
            c %= coin

            print(f'coin : {coin}, change : {c} (cnt | {cnt})')

        counts.append(cnt)
        
        ## 맨 첫번째 값 (가장 큰 값)을 coins 리스트에서 제거
        del coins[0]
        print()
    
    return min(counts)

print(f'count : {change_count_fix(700, coins)}')

## 출력 결과
coin : 500, change : 200 (cnt | 1)
coin : 400, change : 200 (cnt | 1)
coin : 200, change : 0 (cnt | 2)

coin : 400, change : 300 (cnt | 1)
coin : 200, change : 100 (cnt | 2)

coin : 200, change : 100 (cnt | 3)

count : 2

e.g.2) 거스름돈

나동빈 님의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다.  
단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.  

예를 들어 [2, 4, 5, 4, 6]으로 이루어진 배열이 있을 때 M: 8, K: 3이라 가정했을 때,  
특정한 인덱스의 수가 연속해서 3번 까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과 6+6+6+5+6+6+6+5인 46이 된다.

단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.
예를 들어 [3, 4, 3, 4, 3]으로 이루어진 배열이 있을 때 M : 7, K : 2라 가정했을 때,  
두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능하다.  
이 경우 큰 수의 법칙에 따른 결과 4+4+4+4+4+4+4인 28이 된다. 

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 나동빈 님의 큰 수의 법칙에 따른 결과를 출력하시오.

1. 입력 조건
(1) 첫째 줄에 N (2 <= N <= 1,000), M (1 <= M <= 1,000), K(1 <= K <= 10,1000)의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
(2) 둘째 줄에 N새의 자연수가 주어진다. 각 자연수는 공백으로 구분한다.  
    단, 각각의 자연수는 1이상 10,000이하의 수로 주어진다.
(3) 입력으로 주어지는 K는 항상 M보다 작거나 같다.

2. 출력 조건
(1) 첫째 줄에 나동빈 님의 큰 수의 법칙에 따라 더해진 답을 출력한다.

입력 예시            | 출력 예시
5   8   3           | 46  
2   4   5   4   6   |

%%time
def big_number(arr1, arr2):
    
    ## 입력받은 데이터들을 공백으로 나누어 정수형 리스트로 만듦.
    ## M | 숫자를 더해주는 횟수
    ## K | 인덱스 별로 연속으로 더해줄 수 있는 최대 횟수
    _, M, K= map(int, arr1.split(' '))
    arr2 = list(map(int, arr2.split(' ')))
    
    ## 입력받은 데이터를 내림차 순으로 정렬함.
    arr2 = sorted(arr2)[::-1]
    first, second = arr2[0], arr2[1]
    
    answer = 0
    while M != 0:
        ## 가장 큰 수 부터 K번 더해줌.
        for _ in range(K):
            answer += first
            M -= 1
        
        ## 가장 큰 수를 K번 더해준 후에 두번째로 큰 수를 더함
        answer += second
        M -= 1
    return answer

print(f"Answer : {big_number('5 8 3', '2 4 5 4 6')}\n")

## 출력 결과
Answer : 46

CPU times: user 1 ms, sys: 0 ns, total: 1 ms
Wall time: 246 µs

 

(!) 위 함수는 M의 크기가 100억 이상일 경우 시간 초과 판정을 받을 수 있다.

• 가장 큰 수와 두번째로 큰 수가 더해질 때 특정 수열 형태로 반복해서 더해지는 특징이 있다.
  위 예제의 경우 [6, 6, 6, 5]가 반복된다.
• 반복되는 수열의 길이는 K + 1이며, 가장 큰 수가 더해지는 횟수는 K*M / (K + 1)이다.

(!) M이 K + 1로 나누어지지 않는 경우, 가장 큰 수가 더해지는 횟수는

    int(M / (K + 1)) * K + M % (K+1)이다.

%%time
def big_number_fix(arr1, arr2):
    
    _, M, K = map(int, arr1.split(' '))
    arr2 = list(map(int, arr2.split(' ')))
    arr2 = sorted(arr2)[::-1]
    
    first, second = arr2[0], arr2[1]
    iter_nums = int(M / (K + 1))*K + M % (K + 1)
    
    answer = first*iter_nums
    answer += (M - iter_nums)*second
    
    return answer
    
print(f"Answer : {big_number_fix('5 8 3', '2 4 5 4 6')} \n")

## 출력 결과
Answer : 46 

CPU times: user 1e+03 µs, sys: 0 ns, total: 1e+03 µs
Wall time: 616 µs

e.g.3) 숫자 카드 게임

여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.
단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

(1) 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수, M은 열의 개수이다.
(2) 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
(3) 그 다음 선택된 행에 포함된 카드들 중 숫자가 가장 숫자가 낮은 카드를 뽑아야 한다.
(4) 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여
    최종적으로 가장 높은 숫자의 카드를 뽑을 수 있는 전략을 세워야 한다.

1. 입력 조건
첫째 줄에 숫자 카드들이 놓인 행의 갯수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1<=N, M<=100)
둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1이상 10,000이하의 자연수이다.

2. 출력 조건
첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.
입력 예시   |  출력 예시
3 3        |  2
3 1 2      |
4 1 4      |
2 2 2      |

%%time
def card_game(size, datas):
    
    h, w = map(int, size.split())
    datas = datas.split('\n')
    datas = [list(map(int, data.split())) for data in datas]
    
    answer = 0
    for data in datas:
        minimum = min(data)
        answer = max(answer, minimum)
    return answer

answer1 = card_game('3 3', '3 1 2\n4 1 4\n2 2 2')
answer2 = card_game('2 4', '7 3 1 8\n3 3 3 4')
                    
print(f'answer 1: {answer1}')
print(f'answer 2: {answer2}\n')

## 출력 결과
answer 1: 2
answer 2: 3

CPU times: user 1e+03 µs, sys: 0 ns, total: 1e+03 µs
Wall time: 350 µs

e.g.4) 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다.

(1) N이 K의 배수가 될 때까지 1씩 빼기
(2) N을 K로 나누기

단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

N과 K가 주어질 때 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는
최소 횟수를 구하는 프로그램을 작성하시오.

1. 입력 조건
(1)첫째 줄에 N(2 <= N <= 100,000)과 K(2 <= K <= 100,000)가 공백으로 구분되며 각각 자연수로 주어진다.
   이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.
   
2. 출력 조건
(1) 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

입력 예시  |  출력 예시
25 5      |  2

%%time
def until_one(string):
    n, k = map(int, string.split())
    answer = 0
    
    while 1:
        answer += 1
        
        if n % k == 0: n //= k
        else: n -=1
        
        if n == 1: break
        
    return answer

answer1 = until_one('17 4')
answer2 = until_one('25 5')
answer3 = until_one('25 3')

print(f'answer1 : {answer1}')
print(f'answer2 : {answer2}')
print(f'answer3 : {answer3}\n')

## 출력 결과
answer1 : 3
answer2 : 2
answer3 : 6

CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 257 µs

---

 

99. 자료 출처

99-1. 도서

• 한빛미디어 | 나동빈 저 - 이것이 취업을 위한 코딩 테스트다 with 파이썬

99-2.웹 사이트

• 하나몬 | [알고리즘] 탐욕 알고리즘 (Greedy Algorithm) [블로그 링크]

---

 

전체코드

GitHub - EvoDmiK/TIL: Today I Learn

---

내용 추가 이력

---

부탁 말씀

개인적으로 공부하는 과정에서 오류가 있을 수 있으니, 오류가 있는 부분은 댓글로 정정 부탁드립니다.

---