[이코테] 그리디 알고리즘

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 정당성 분석이 중요하다.
  • 반복적으로 그리디 알고리즘을 따라가도 최적의 해를 구할 수 있는지를 검증해야 한다.
• 암기한다고 풀 수 있는 유형이 아니며, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 줄 알아야 한다.

예제 <거스름돈>

문제
거슬러줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 갯수는?
Key
가장 큰 화폐부터 거슬러주자

n = 1260 
count = 0

array = [500, 100, 50, 10] # 큰 단위의 화폐부터 차례대로 확인한다. 

for coin in array:
    count += n// coin # 해당 화폐로 거슬러 줄 수 있는 동전의 갯수를 세자 
    n %= coin 

print(count)

• 화폐의 종류가 K라고 한다면, 소스코드의 시간 복잡도는 O(K)
• 이 알고리즘의 시간복잡도는 거슬러줘야 하는 금액과는 무관, 동전의 총 종류에만 영향을 받는다

• 같은 코드를 C++ 로 구현하면 다음과 같다.

  #include <iostream>
  using namespace std;

  int n = 1260;
  int cnt; // 0으로 초기화 되어 있음 

  int coinTypes[4] = {500, 100, 50, 10}; // 배열에 화폐의 종류를 담는다 

  int main(void){
    for (int i = 0; i<4; i++){
    // 모든 과정을 화폐 단위 갯수만큼 반복한다. 
      cnt += n / coinTypes[i]; 
      // 매번 현재의 동전을 확인하고 
      // 남아있는 돈을 현재의 동전으로 나눈 몫을 cnt에 넣어준다. 
      n %= coinTypes[i];
      // 거슬러 주는 것이 끝나고 남은 금액도 n에 넣어준다. 
    }

    cout << cnt << "\n";

  }

큰 수의 법칙

문제
다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙 (단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과해서 더해질 수 없다)

Key
반복되는 수열

가장 큰 수를 만들려면 주어진 수 중에서 가장 큰 수를 최대한 더하면 된다. 그러나 연속으로 더하는 것에 대한 횟수 제한이 있으므로 그 횟수를 소진했을 때는 두 번째로 큰 수를 사용하여야 한다.

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

# n개의 자연수 
# m은 숫자가 더해지는 횟수 
# k는 연속으로 더할 수 있는 횟수 (k번을 초과할 수 없다 )

data = list(map(int, input().split())) # n개의 자연수를 공백을 구분하여 입력받는다 
            
data.sort() # 입력받은 data들을 오름차순으로 정렬 
first = data[n-1] # 가장 큰 수 (배열 가장 오른쪽에 있는게 가장 크겠지)
second = data[n-2] # 두번째로 큰 수 (배열 오른쪽에서 하나 왼쪽에 있는게 가장 크겠지) 

result = 0 # result 값 초기화 

            
while True:
    for i in range(k): # k번 반복한다  
            
        if m == 0: # 0이면 멈춤 
            break
            
        result += first # 결과값에 가장 큰수를 더한다 
        m -= 1 # 더할때마다 m번 횟수에서 1씩 뺀다 
            
    if m == 0:
        break
    
    result += second
    m -= 1

print(result)

위와 같은 코드는 생각해내기는 쉽지만 M의 크기가 매우매우 큰 수 이상이 되면 시간 초과 판정을 받을 수 있다.
수열을 이용한 더 효율적인 코드를 고민해보자.

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

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

data.sort()

first = data[n-1]
second = data[n-2]

# 가장 큰수가 몇 번 더해지는가? 
count = int(m / (k+1)) * k 
count += m % (k+1) 

result = 0

result += (count) * first 
#가장 큰 수를 더해서 result에 넣는다. 
result += (m - count) * second 
# 두 번째로 큰 수 더해서 result에 넣는다 

print(result)

count = int(m / (k+1)) * k
: 가장 큰 수가 더해지는 횟수를 계산한다.
: 반복되는 수열의 길이는? -> m을 k+1로 나눈 몫!

그러나 나누어 떨어지지 않는 경우 남는 부분도 더해주어야 하므로
count += m % (k+1) 이 코드를 통해 나머지를 count에 더해준다.

숫자 카드 게임

문제
여러 개의 숫자 카드 중 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임

<룰>
1. 카드는 NXM 형태로 놓여있음
2. 행을 먼저 선택
3. 선택한 행에서 가장 작은 숫자가 있는 카드 선택
4. 각 행에서 가장 작은 숫자를 선택하더라도 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있어야 함

Key
각 행에서는 가장 작은 수 / 그 수 중에서 가장 큰 수 찾기

n, m = map(int, input().split()) 
#행렬을 입력받는다 

result = 0
# 결과값 초기화 

for i in range(n): # 행을 탐색 
    data = list(map(int, input().split()))
    # 각 행에 수를 입력해서 데이터 값에 넣는다 
    
    data_min = min(data)
    # 입력한 데이터 값 중에서 작은 값을 찾는다 
    
    result = max(result, data_min)
    # result 값과 위에서 찾은 최소값을 비교하여 큰 수를 result에 넣는다. 
    
print(result)

2 4
7 3 1 8
3 3 3 4
3

1이 될 때 까지 최소 연산 쵯수 구하기

문제
어떤 수 N이 1이 될 때까지 두 과정 중 하나를 반복적으로 선택해 수행 (두 번째 연산은 N이 K로 나누어떨어질 때만 가능)
1. N에서 1을 뺀다 :n-1
2. N을 K로 나눈다 : n // k
1번 혹은 2번 과정을 수행해야하는 최소 횟수를 출력

key
최대한 나누기를 많이 하면 n을 크게 줄일 수 있으므로 최소한의 횟수로 1로 만들 수 있다

• 단순한 코드

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

result = 0

# n이 k이상이면 k로 나눈다 
while n >= k:
    while n % k != 0:
        n -= 1
        result += 1 
        # 횟수를 구해야 하므로 연산을 할 때마다 result 값을 1씩 증가시켜준다 
        
    #k로 나눈다 
    n //= k
    result += 1 
    
while n>1:
    n -= 1
    result += 1

print(result) 

• 나누어 떨어지는 값을 바로 찾는 코드

n, k = map(int, input().split())
result = 0 # 횟수 

while True:
    target = (n//k) * k
    result += (n - target)
    
    n = target
    
    if n < k:
        break # n이 k보다 작다면 무한루프 탈출 
    
    result += 1
    n //= k
    # n이 k의 배수이므로 나누어준다 

# n이 1보다 크다면 남은 수에 대해서 1씩 빼는 연산을 한다 
result += (n-1)

print(result)

target = (n//k) * k

n을 k로 나눈 몫에 k를 곱해서 target에 넣게 되면 target은 k로 나누어 떨어지는 가장 가까운 값을 찾은 것이 된다.

result += (n - target)

이 부분에서 result에는 n이 target이 될 때 까지 (나누어 떨어지는 가장 가까운 값을 찾을 때 까지) 1을 빼는 연산을 하는 횟수가 담기게 된다.

• 시간복잡도
  두 번째 방법으로 풀게 되면 O(log n) 시간복잡도가 나온게 된다. (한 번 반복 할 때마다 바로 n이 k로 나눠지는 연산이 수행이 되므로 기하급수적으로 n이 빠르게 감소하여 1로 향하여 간다)
  : 매우 큰 수일 때도 쓸 수 있다

• 동일한 코드를 C++로 구현

#include <iostream>
using namespace std;

int n, k;
int result;

int main(void){
  cin >> n >> k;

  while(true){
    int target = (n/k) * k;
    result += (n - target);
    n = target;

    if (n<k) break;

    result++;
    n /= k;
  }

  result += (n-1);
  cout << result << '\n';
}