Gready

개요

알고리즘이라고 하면 공식이 떠오른다. 값을 딱 넣으면 알아서 답을 내주는 수학의 수식과 같은 느낌이다.
그러나 알고리즘을 공부하다보면 경험적인 문제 풀이도 존재한다는 걸 알 수 있다. 대표적으로 탐색 알고리즘이 있다.
그리디 알고리즘은 탐욕법이라고도 하며 문제를 단순무식하게 탐욕적으로 푼다고 해서 탐욕법이라는 이름이 붙었다.

현재 상황에서 최선의 선택을 한다.

설명

그리디 알고리즘을 가장 쉽게 설명할 수 있는 방법은 바로 거스름돈 문제다.

예를 들어 내가 500원, 100원, 50원, 10원짜리 동전을 가지고 있고 충분히 여유있는 갯수로 가지고 있다. 동전 갯수를 최소한으로 써서 넘치지도 않게 부족하지도 않게 정확히 일정 금액을 지불하려고 한다면 어떻게 하는 게 좋을까?

예를 들어 가게에서 3420원을 지불하려한다. 내가 가진 동전은 1원 10원 50원 100원 500원이 있다고 했을 때 동전 갯수를 최소한으로 쓰려면 일단 가장 큰 금액으로 지불할 수 있을 만큼 지불해야한다.

500원이 내가 가진 가장 큰 금액의 동전이므로 500원동전으로만 쓰는게 가장 적게 동전을 쓰는 방법일 것이다. 그러나 500원을 6개 쓰면 부족하고 7개를 쓰면 넘친다.

그러면 500원짜리 동전 6개를 쓰고 그 다음 작은 단위로 넘어가야한다. 그리고도 남으면 더 작은단위로.

이러한 방식을 그리디 알고리즘이라고 한다. 현재 상태에서 보는 선택지중 최선을 선택하고 그 다음 상황에서 또 최선을 선택한다. 그리고 각 상황에서의 최선이 전체의 최선이여야한다.(그리디 알고리즘을 사용할 수 있는 조건)

문제를 푸는 방법은 이렇다. 3420원을 내가 가진 가장 큰 금액의 동전으로 나눈다. 이 경우 6개가 되겠다. 남은 금액은 420원이다. 그 다음은 100원짜리 4개를 쓰고 그 다음은 10원짜리 동전 2개를 쓴다. 이렇게한다면 최소한의 동전만 쓸 수 있다.

의사코드로 표현한다면 다음과 같다.

for(오름차순으로 정렬된 동전 액수의 인덱스를 거꾸로 반복) {
    if(지불 금액보다 동전의 금액이 작으면) {
        동전 수 += 목표금액 / 현재 동전의 금액
        총 금액 = 목표금액 % 현재 동전의 금액.
    }
}

코드를 보면 반복문을 돌릴 때 1개의 반복문을 돌리고 있으니 시간복잡도는 O(n)이고 시간 복잡도에 영향을 주는 요소는 금액이 아니라 동전의 종류다.

주의점

효과적이고 강력한 알고리즘이지만 모든 문제에 그리디알고리즘을 적용할 수 있는 것은 아니다.
항상 지금 상황에서의 최선을 선택했지만 최적의 해를 찾을 수 없을 수 있다.
따라서 그리디 알고리즘을 사용할 수 있는 조건은 각 상황에서 최적의 해를 찾는 것이 결과적으로 최적의 해를 구하는 것이라는 보장이 있어야한다.

예를 들어 화폐단위가 500원, 400원, 100원이 있고 이를 이용해서 800원을 내야하는 문제가 있다고 해보자.
그리디 알고리즘을 적용한다면 500원을 지불할 것이고 남은 금액인 300원을 100원짜리 3개로 지불할 것이다. 이러면 매 상황에서 최선을 선택한 것이니 정답일 것 같지만 최적의 해는 400원짜리 동전 2개를 내는 것이다.

만약 알고리즘 문제를 푸는데 해결방법이 쉽게 떠오르지 않는다면 그리디알고리즘을 의심해보는 것이 좋다. 만약 이 것도 아니라면 동적 계획법이나 그래프 알고리즘일 확률이 높다.

문제풀이

수 묶기

문제
길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.

예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2*3)+(4*5) = 27이 되어 최대가 된다.

수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.

수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력
첫째 줄에 수열의 크기 N이 주어진다. N은 50보다 작은 자연수이다. 둘째 줄부터 N개의 줄에 수열의 각 수가 주어진다. 수열의 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력
수를 합이 최대가 나오게 묶었을 때 합을 출력한다. 정답은 항상 231보다 작다.

예제 입력 1 
4
-1
2
1
3
예제 출력 1 
6
예제 입력 2 
6
0
1
2
4
3
5
예제 출력 2 
27
예제 입력 3 
1
-1
예제 출력 3 
-1
예제 입력 4 
3
-1
0
1
예제 출력 4 
1
예제 입력 5 
2
1
1
예제 출력 5 
2

곱한 수가 최대가 되려면 가장 큰 수끼리 곱해야한다.
예를 들어 1, 2, 3, 4가 있다면 14 + 23을 하는 것보다 12 + 34를 하는 것이 크다.
문제는 0도 있고 음수도 있다는 점이다.
음수는 음수끼리 곱해야한다. 그럼 +로 부호가 바뀌면서 최대가 된다. 음수끼리일 경우에도 큰 수끼리 곱해야하고 0이 있는 경우 음수의 개수가 홀수인 경우 조커 카드로 사용하면 될 것이다.
또한 우선순위에 따라 큰 수부터 뽑아내어 곱했을 때 1*2와 같은 경우도 나올 수 있다. 그러나 이러면 최선이 아니기 때문에 1은 따로 빼서 1끼리 더한다.

from queue import PriorityQueue
n = int(input())

plus_queue = PriorityQueue()
minus_queue = PriorityQueue()
one = 0
zero = 0

for i in range(n):
    data = int(input())
    if data>1:
        plus_queue.put(data * -1)
    elif data == 1:
        one += 1
    elif data == 0:
        zero += 1
    else:
        minus_queue.put(data)
sum = 0

while plus_queue.qsize() > 1:
    first = plus_queue.get() * -1
    second = plus_queue.get() * -1
    sum += first * second

if plus_queue.qsize() > 0:
    sum += plus_queue.get() * -1

while minus_queue.qsize() > 1:
    first = minus_queue.get()
    second = minus_queue.get()
    sum += first * second

if minus_queue.qsize() > 0:
    if zero == 0:
        sum += minus_queue.get()
sum += one

print(sum)

기지국

```문제 설명 N개의 아파트가 일렬로 쭉 늘어서 있습니다. 이 중에서 일부 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 기술이 발전해 5g 수요가 높아져 4g 기지국을 5g 기지국으로 바꾸려 합니다. 그런데 5g 기지국은 4g 기지국보다 전달 범위가 좁아, 4g 기지국을 5g 기지국으로 바꾸면 어떤 아파트에는 전파가 도달하지 않습니다.

예를 들어 11개의 아파트가 쭉 늘어서 있고, [4, 11] 번째 아파트 옥상에는 4g 기지국이 설치되어 있습니다. 만약 이 4g 기지국이 전파 도달 거리가 1인 5g 기지국으로 바뀔 경우 모든 아파트에 전파를 전달할 수 없습니다. (전파의 도달 거리가 W일 땐, 기지국이 설치된 아파트를 기준으로 전파를 양쪽으로 W만큼 전달할 수 있습니다.)

```입출력 예
N	stations	W	answer
11	[4, 11]	1	3
16	[9]	2	3

감으로 만약 시간 복잡도 1로 해결할 수 없다면 경험적으로 찾아야한다는 느낌이 든다.
이 문제는 그리디 알고리즘 문제로, 스테이션을 순회하면서 전파 범위에 없다면 일단 기지국을 세운다. 전파범위를 최대로 효율적으로 쓰려면 전파 범위 만큼 이동하여 기지국을 세워야한다.

만약 1,2,3,4,5,6과 같이 스테이션이 주어졌다면 첫 번째 기지국은 2번에 세워야한다.
다음은 이전 전파 범위에서 벗어난 4번부터 확인한다. 만약 중간에 이미 설치된 곳이 있다면 전파범위 밖으로 벗어나서 다시 반복하면 된다.

예제 1번을 보자 1부터 순차적으로 돈다.

while position <= n:
    position += 1

만약 기지국이 없다면 범위가 최대로 되는 지점에 기지국을 설치한다.

while position <= n:
    answer += 1
    poisition += w + 1 + w

이미 다른 기지국의 영향을 받고있는 지점인지 확인해야한다.
만약 기지국이 설치된 지점이 4라면 4 - w와 현재 위치를 비교하여 만약 이 범위보다 위치가 크가나 같다면 이전 전파범위에 해당한다는 의미이다. 따라서 다음 기지국을 세울 지점은 오른쪽 전파 범위의 다음 위치인 4 + w + 1이 된다.
만약 아니라면 원래의 시나리오대로 전파범위가 최대가 되는 위치에 기지국을 하나 세운다.

from collections import deque

queue = deque(stations)
...
while position <= n:
    if len(queue) > 0 and queue[0] - w <= position:
        position = queue.popleft() + w + 1
    else:
        answer += 1
        position += w + 1 + w

전체코드

from collections import deque

def solution(n, stations, w):
    answer = 0
    queue = deque(stations)

    position = 1
    while position <= n:
        if len(queue) > 0 and queue[0] - w <= position: 
            position = queue.popleft() + w + 1
        else:
            answer += 1
            position += 2 * w + 1

    return answer

무지의 먹방 라이브

```문제 설명 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다.

무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음식을 말한다. 회전판이 다음 음식을 무지 앞으로 가져오는데 걸리는 시간은 없다고 가정한다. 무지가 먹방을 시작한 지 K 초 후에 네트워크 장애로 인해 방송이 잠시 중단되었다. 무지는 네트워크 정상화 후 다시 방송을 이어갈 때, 몇 번 음식부터 섭취해야 하는지를 알고자 한다. 각 음식을 모두 먹는데 필요한 시간이 담겨있는 배열 food_times, 네트워크 장애가 발생한 시간 K 초가 매개변수로 주어질 때 몇 번 음식부터 다시 섭취하면 되는지 return 하도록 solution 함수를 완성하라.

[3, 1, 2]와 같이 주어졌을 때 배열을 순회하며 1초에 음식을 하나씩 먹으므로  
5초에 남은 음식은 [1, 0, 0]으로 1번 음식을 먹어야할 때 방송이 중단되고 1번 음식부터 먹기 시작하면 된다.

이런 식으로 답을 구한다.  
생각해보면 모든 음식을 다 먹을 때까지 고려해야할 필요가 없고 결국 k초에 어떤 음식이 남아있는지 확인하면 되기 때문에 k초가 종료 시간이 된다.

예를 들어 예시의 경우 음식이 3개가 있고 종료 시간이 5이기 때문에 남은 시간은 `남은 음식 * 최소 시간`을 종료 시간에서 뺀다. `종료시간 - 남은 음식 * 최소 시간`을 구해보면 2가 된다.  이제 3번째 음식을 기준으로 계산한다. 남은 음식은 2개, 최소시간은 2로 4를 빼야하지만 남은 시간은 2초로 4초보다 작기때문에 빼지 않는다.  
[3, 2]에서 [2, 2], [2, 1], [1, 0]이므로 1번 음식을 먹을 차례가 된다.

위와 같은 동작과 맞는 자료구조는 우선순위 큐가 있다.

우선순위 큐는 담긴 데이터의 우선순위가 가장 높은 데이터를 가장 먼저 꺼내는구조로 최소 힙 또는 최대 힙을 이용한다. 최소 힙은 값이 가장 작은 데이터를, 최대 힙은 값이 가장 큰 데이터를 먼저 꺼낸다.

파이썬에서 우선순위 큐는 PriiorityQueue와 heapq를 사용하는데 일반적으로 heapq가 더 빠르게 동작해서 heapq를 사용한다.
```python
import heapq

q = []
for i in range(len(food_times)):
    heapq.heappush(q, (food_times[i], i+1))

시간이 가장 짧게 걸리는 음식을 꺼내고 sum_value를 갱신해야한다. 현재 꺼내온 음식의 시간을 now로 갱신하고 now * length를 하면 1 * 3으로 3초가 걸리니 지금까지 음식을 먹는데 소모한 시간인 sum_value는 3이 된다.
두 번째로 오래걸리는 음식은 2초로 (2-1) * 2 = 2가 나오고 sum_value를 5로 갱신한다.

while sum_value + (q[0][0] - previous) * length  <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1
        previous = now

그럼 반복문을 종료하고 음식의 인덱스를 출력하면 된다. 현재 큐는 시간을 기준으로 정렬되어있다. 이를 음식의 순서로 정렬해야한다.
그런 다음 (k - sum_value) % length식을 통해 인덱스를 계산한다.
예를 들어 k = 5, sum_value = 3이므로 남은 남은 음식의 갯수에서 0, 1, 0, 1과 같이 반복해야한다. 남은 음식의 갯수만큼의 주기를 갖기 때문에 [(3, 1), (2, 3)]에서 2 % 2는 0이므로 0번 인덱스의 음식을 먹을 차례라는 것을 의미한다.

result = sorted(q, key =lambda x: x[1])
return result[(k - sum_value) % length][1]

import heapq

def solution(food_times, k):
    if sum(food_times) <= k:
        return -1
    
    q = []
    for i in range(len(food_times)):
        heapq.heappush(q, (food_times[i], i+1))

    sum_value = 0
    previous = 0

    length = len(food_times)

    while sum_value + (q[0][0] - previous) * length  <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - previous) * length
        length -= 1
        previous = now

    result = sorted(q, key =lambda x: x[1])
    return result[(k - sum_value) % length][1]

코드 출처 : 이테코 - 동빈나