[Algorithm] 그리디(Greedy) : 탐욕법이란?

당장 좋은 것만 선택하는 그리디

그리디(Greedy) 알고리즘은 국내에서 단어 그대로 번역하여 탐욕법으로 소개된다.

이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

여기서 탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법 을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀수 있을 가능성이 높은 문제 유형이라는 특징이 있다. 자바코드와 새로 배우고 있는 파이썬 코드로 풀어보았다.

 

큰 수의 법칙

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰수를 만드는 법칙이다. 단, 배열의 특정한 인덱스 (번호) 에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 입력으로 주어지는 k는 항상 m 보다 작거나 같다. 처음에는 while 문을 사용하여 풀어보았다. 하지만 단위가 100억 이상 커진다면 시간초과 판정을 받을 것이다. 좀더 수학적으로 풀어보아 효율적으로 해결해보았다.

//자바 
import java.util.*;
class Main {
 public static void main(String[] args) {
 Scanner sc = new Scanner(System.in);
 // N, M, K를 공백을 기준으로 구분하여 입력 받기
 int n = sc.nextInt();
 int m = sc.nextInt();
 int k = sc.nextInt();

  // N개의 수를 공백을 기준으로 구분하여 입력 받기
 int []arr = new int[n];
 for(int i = 0; i < n; i++)
 {
   arr[i] = sc.nextInt();
 }
 Arrays.sort(arr); // 입력 받은 수들 정렬하기
 int first = arr[n - 1]; // 가장 큰 수
 int sec = arr[n - 2]; // 두 번째로 큰 수
 int j = k;
 int result = 0;
 
 // 가장 큰 수가 더해지는 횟수 계산
 int count = (m / (k + 1)) * k;
 count += m % (k + 1); 
 result = (first * count) + (sec * (m - count)); // 가장 큰 수 와 두번째로 큰 수 더하기
 System.out.print(result);  
 }
}
   

숫자 카드 게임

숫자 카드 게임은 n * m 형태로 놓어있고 여러 n 개의 행중에 가장작은 수가 가장 큰 행의 작은 수를 출력하는 문제이다. 각 숫자는 1이상 10000이하의 자연수 이다.

n, m = map(int, input().split())
k = []
result = 0

for i in range(n):
  data = list(map(int, input().split()))
  # 현재 줄에서 가장 작은 수 찾기
  min_value = min(data)
  # 가장 작은 수 들 중에서 가장 큰 수 찾기
  result = max(result, min_value)

print(result)

1이 될때까지

어떠한 수 N이 1이 될때까지 다음의 두과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

N과 K가 주어질때 N이 1이 될때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오. 이번에는 파이썬으로 두가지 방법으로 풀이 해 보았다. 아직 파이썬이 익숙하지 않아 답안예시 대로 풀이를 해보고 분석하고 약간의 수정을 거쳤다.

단순하게 이중 while로 푸는 방식

n, k = map(int, input().split())
result = 0;
# N이 K이상이라면 k로 계속 나누기
while n >= k:
   # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기
  while n % k != 0:
    n -= 1
    result += 1
  # K로 나누기
  n //= k
  result += 1

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
  n -= 1
  result += 1

print(result)

해당 문제에서는 범위가 10만 이하이므로 위에 처럼 일일히 체크를 해도 문제를 해결할 수 있지만 100억 이상의 큰 수가되는 경우를 가정했을 때에도 빠르게 동작하려면 배수가 되도록 효율적으로 한번에 빼는 방식으로도 코드를 작성할 수 있다.

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

while True:
# N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
  target = (n//k) * k
  result += (n - target)
  n = target
  # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
  if n < k:
    break
   # K로 나누기
  result += 1
  n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)