그리디(greedy)알고리즘

• 단순하지만 강력한 문제 해결 방법
• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

예제 거스름돈

• 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정
  손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수
  단 거슬러 줘야 할 돈 N은 항상 10의 배수
  • '가장 큰 화폐 단위부터' 돈을 거슬러 준다.
  1. X원을 넘지 않는 범위에서 500원 동전을 가능한 많이 사용
  2. 남은 금액에서 100원 동전을 가능한 많이 사용
  3. 남은 금액에서 50원 동전을 가능한 많이 사용
  4. 마지막으로, 남은 금액을 10원 동전으로 지불

n = 1260
count = 0

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

for i in coin_types :
	count += n // i # 해당 화폐로 거슬러 줄 수 있는 동전의 개수
    n %= i
    
print(count)

• 화폐의 종류가 K개라고 할 때 위 소스코드의 시간 복잡도는 $O(K)$
• 이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야하는 금액,의 크기와는 무관하다는 것을 알 수 있다.

그리디 알고리즘의 정당성

• 그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
• 대부분의 그리디 알고리즘문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

그리디 패턴(1) : 교환해도 악화되지 않음

최적화 문제를 생 각하는 포인트
$x$의 대한 함수 $f(x)$의 최댓값을 구하고자 한다. 임의의 $x$에 대해 조금 변형을 가하면 어떤 성질 $P$를 만족하는, $x$와 유사한 별도의 해 $x'$를 얻을 수 있고, $f(x') \geq f(x)$ 이런 식이 성립한다고 하자. 이때 전체 $x$ 중에서 $P$를 만족하는 것만 대상으로 하더라도 그 안에 $f(x)$가 최대가 되는 $x$도 포함된다.

• 이 성질을 활용하면 탐색 범위가 확 줄어드는 경우가 많다.

구간 스케일링 문제
N개의 일이 있는데 $i(=0, 1, ..., N-1)$번째 일은 시간 $S_i$에 시작해서 시간 $t_i$에 끝난다. 가능한 한 많은 일을 처리하고 싶은데 시간이 겹치는 일은 선택할 수 없다. 최대 몇 개의 일을 할 수 있는지 구하라

• 탐욕법을 적용해서 생각하려면 우선 주어진 N개의 구간에 대해 어떤 순서로 구간을 선택할지가 무척 중요하다.
  구간 관련된 문제를 푸는데, 일단 구간 종료 시간을 기준으로 정렬해서 생각해 보면 쉬워질 때가 많다.
• 모든 구간 중에 가장 종료 시간이 빠른 구간을 $p$라고 가정
  이때 구간 $p$는 일단 선택해도 큰 문제가 없다.('최적화 문제를 생각하는 포인트'로 확인 가능)
  구체적으로 , 임의의 구간 선택법을 선택 구간의 개수를 변경하지 않고그 안에서 구간 $p$가 포함되도록 살짝 바꿀 수 있다는 것
• 임의의 구간 선택법 $x$에대해 그중 가장 왼쪽에 있는 구간을 $p'$라고 한다. 이때 $p$의 정의에서 다음을 만족한다.
  $구간 p 종료 시간 \leq 구간 p'종료 시간$
  $x$에 있어 $p'$ 이외의 임의의 구간 $q$는 다음을 만족한다.
  $구간 p'종료시간 \leq 구간 p'시작시간$
  따라서 정리하면 다음을 만족
  $구간 p 종료시간 \leq 구간 q시작시간$
• 이것으로 구간 선택법 x에 있어 $p'$를 $p$로 교환해도 선택 가능한 구간 개수가 줄어드는 일 없이 구간이 겹치지 않는 상태를 유지할 수 있다.
  따라서 구간 스케일링 문제의 답으로 구간 $p$를 포함하는 것만 탐색 후보에 넣어도 된다.
• 구간 $p$를 선택한 후에는 $p$와 겹치는 구간은 모두 제외하고 남은 구간에 대해 동일한 방법으로 선택을 반복
  A : 남은 구간 중 종료 시간이 가장 빠른 것을 고름(탐욕법)
  B : 이렇게 고른 구간과 겹치는 구간을 삭제
  이 작업을 더 이상 처리할 구간이 모두 없어질 때까지 반복
• 처음에 구간을 구간 종료 시간 순서로 정렬하는 부분은 $O(NlogN)$ 복잡도
  탐욕법으로 구간을 선택하는 처리는 $O(N)$ 복잡도
  전체로 보면, 시작할 때 정렬하는 부분에시간이 걸려서 복잡도는 $O(NlogN)$

그리디 패턴(2) : 현재가 좋으면 미래도 좋음

탐욕법이 성립하기 위한 단조성
N단계의 선택을 통해 최종 점수를 최대화하는 최적화 문제가 있다고 가정
이 문제는 최초 $i$단계까지의 시점에서 획득한 점수가 높으면 높을수록남은 단계를 최적화해서 얻는 최종적인 점수가 높아지는 구조
이때 각 단계마다 독립적으로 그 시점에 점수가 최대가 되는 탐욕법을 사용하면 모든 단계가 끝났을 때 점수가 최대화되는 걸 알 수 있다.

예제

AtCoder Grand Contest 009 A - Multiple Array
0 이상의 정수로 이뤄진 N항 수열 $A_0, A_1, ..., A_{n-1}$과 N개 버튼이 주어졌을때 $i(0,1,...,N-1)$번째 버튼을 누르면 $A_0, A_1, ..., A_i$값이 각각 1씩 증가한다. 그리고 11 이상의 정수로 이뤄진 N항 수열 $B_0, B_1, ..., B_{n-1}$이 주어졌을 때 몇 번인가 버튼을 눌러서 모든 $i$에 대해 $A_i$가 $B_i$의 배수가 되도록 만들려고 한다. 버튼을 누르는 최소 횟수를 구하라

• 버튼 0, 1, ... N - 1을 누른 횟수를 각각 $D_0, D_1,...,D_{n-1}$이라고 하면 다음 조건을 만족하는 $D_0, D_1,...,D_{n-1}$의 최솟값을 구하는 문제라고 할 수 있다.
  • $A_0 + (D_0, D_1,...,D_{n-1})$은 $B_0$의 배수
  • $A_1 + (D_1, D_1,...,D_{n-1})$은 $B_1$의 배수
    ...
  • $A_{n-1} + D_{n-1}$은 $B_{n-1}$의 배수
• $A_{n-1} + D_{n-1}$이 $B_{n-1}$의 배수라는 조건을 만족하는 $D_{n-1}$
  (편의상 $a=A_{n-1}, b = B_{n-1}, d = D_{n-1}$)
  $a + d$가 $b$의 배수가 되는 $d$로 가능한 값은 다음과 같다.
  • $a$가 $b$의 배수일 때 : $d = 0, b, 2b, ...$
  • 그렇지 않을 때 : $a$를 $b$로 나눈 나머지가 $r$이라면 $d=b-r,2b-r, 3b-r,...$
• $d=D_{n-1} 선택법은 다음과 같다
  • $A_{n-1}$이 $B_{n-1}$의 배수일 때 : $D_{n-1}=0$
  • 그렇지않을 때 : $A_{n-1}$을 $B_{n-1}$로 나눈 나머지가 $r$이라면 $D_{n-1}=B_{n-1}-r$
• $O(N)$ 복잡도

출처 : 문제해결력을 높이는 알고리즘과 자료구조
이것이 코딩테스트다 with 파이썬

실전문제 코드