[알고리즘] 탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘(Greedy Algorithm) 이란?

• 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.
• 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 을 의미한다.
• 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
• 최적해를 구하는 데에 사용되는 근사적인 방법이다.
• 그리디 알고리즘은 말 그대로 각 단계에서 미래를 생각하지 않고, 그 순간 가장 최선의 선택을 하는 기법이기 때문에 종합적인 결과에 대해서는 최적의 해를 보장할 수 없다. (지역적(local)으로는 최적의 선택이지만 이를 반복하더라도 전체적(global)으로는 최적의 해가 아닐 수 있음)

 

탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

성립해야할 2가지 조건

- 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.

1. greedy choice property: 현재 선택이 이 후의 선택에 영향을 주지 않음
2. optimal substructure: 매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 함

- 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다.

- 매트로이드 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다

- 매트로이드에 대한 설명은 아래 참고

https://dad-rock.tistory.com/673 

[Algorithms] Matroid Theory | 매트로이드 이론

 

- 매트로이드는 모든 문제에서 나타나는 것은 아니지만, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여준다

 

그리디 알고리즘의 예제 - 거스름돈

- 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정

- 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라

 

- 이 문제는 그리디 알고리즘을 이용해 풀 수 있는 가장 대표적인 문제!!

- '가장 큰 화폐 단위부터' 돈을 거슬러 주면 된다

# 시간복잡도는 화폐의 종류 k개에만 영향을 받음 O(k)

n = int(input())  
cnt = 0

coin = [500, 100, 50, 10]

for c in coin:
  cnt += n // c
  n %= c

print(cnt)

 

 

탐욕 알고리즘의 한계

• 탐욕 알고리즘은 근사치 추정에 활용
• 반드시 최적의 해를 구할 수 있는건 아니기 때문
• 최적의 해에 가까운 값을 구하는 방법 중 하나!!

출처 : https://devlog-wjdrbs96.tistory.com/104

시작 노드에서 시작해서 가장 작은 값을 찾아 leat 노드 까지 가는 경로 탐색

• 탐욕 알고리즘 : 시작 -> 7 -> 12 해서 19
• 실제 가장 작은 값 : 시작 -> 10 -> 5 해서 15

위의 동전문제 경우에도 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 가능

• 예를 들어 800원을 거슬러 줘야 하는데 화폐 단위가 500, 400 ,100원 인 경우
• 이 경우에 그리디 알고리즘으로는 4개(500+100+100+100)
• 실제 최적의 해는 2개(400+400)

 

대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다~!

 

 

 

---

이코테 실전문제

실전문제 1. 큰 수의 법칙

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

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

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

number.sort()  # 정렬
first = number[-1]
second = number[-2]

cnt = int(m / (k+1)) * k    # int(m / (k+1))은 수열이 반복되는 횟수. 그 안에 k개의 가장큰 수가 들어있으니까 곱한다
cnt += m % (k + 1)          # 나누어 떨어지지 않는 경우 나머지만큼 가장 큰수가 나열

result = 0
result += cnt * first
result += ( m - cnt) * second

print(result)

 

실전문제 2. 숫자 카드 게임

 

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

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

result = 0

for i in range(n):
  num = list(map(int, input().split()))

  min_num = min(num)

  result = max(result, min_num)

print(result)

 

실전문제 3. 1이 될 때까지

 

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

# 내가 푼 코드

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

while n >= k:

  while n % k != 0:              # N이 k로 나누어떨어지지 않으면
    n -= 1
    cnt += 1 
  
  n //= k
  cnt += 1

while n > 1:
  n -= 1
  cnt += 1

print(cnt)

# 이코테 답지

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

while True:
  target = (n//k) * k
  result += (n - target)
  n = target

  if n < k:
    break

  result += 1
  n //= k

result += (n-1)
print(result)

 

---

https://www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

 

 

 

https://it-college-diary.tistory.com/entry/21-Greedy-Algorithm%ED%83%90%EC%9A%95%EB%B2%95-%EC%9A%95%EC%8B%AC%EC%9F%81%EC%9D%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EB%85%90

Greedy Algorithm(그리디 알고리즘) 개념, 추천 문제