[Algorithm] Week 2. 그리디

알고리즘 스터디 코드와 규칙 정리:

https://github.com/5jisoo/Algorithm-Study

GitHub - 5jisoo/Algorithm-Study: [2023 Winter ~ ] Algorithm Study ✏️ 알고리즘 스터디를 위한 저장소입니다.

 

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

 

---

그리디 알고리즘

탐욕법.

현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘.

 

• 매 순간 가장 좋아보이는 것을 선택함.
  • '기준'에 따라 좋은 것을 선택해야 함. --> 문제에서 기준을 알게 모르게 제시해줌.
• 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.

 

---

예제 - 거스름돈

문제

카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정한다.
거슬러줘야 할 동전의 최소 개수를 구하라.
단, 거슬러 줘야할 돈 N은 항상 10의 배수이다.

 

---

아이디어

'가장 큰 화폐 단위부터' 돈을 거슬러 주는 것

 

N = 1260
count = 0   # 코인의 개수

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

for coin in coins:
    count += N // coin		# 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    N %= coin

print(count)

• 화폐의 종류가 K일때, 시간 복잡도는 O(K)

 

---

그리디 알고리즘의 정당성

그리디 알고리즘은 매우 효과적이고 직관적이지만,

이 알고리즘을 통해 문제의 해법을 찾은 뒤엔 해법이 정당한지 검토하는 과정이 필요함.

 

 

위의 예제를 그리디 알고리즘으로 해결할 수 있는 이유?

• 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문!

 

이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고

이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다!

 

---

교재 예제 정리

만들 수 없는 금액

문제

편의점의 주인은 N개의 동전을 가지고 있습니다.
이때, N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요.

- input
첫째 줄에는 동전의 개수 N이 주어집니다.
둘째 줄에는 각 동전의 화폐 단위를 나타내는 N개의 자연수가 주어집니다.

- output
첫째 줄에 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값을 출력합니다.

입력 예시
5
3 2 1 1 9

출력 예시
8

 

---

풀이 과정

 

먼저, 입력으로 주어지는 동전들의 리스트를 sort() 함수를 통해 정렬해준다.

 

result 변수는 만들어야 하는 숫자의 크기를 의미하며, (그러므로 처음엔 1로 초기화 되어있다.)

동전 리스트의 원소를 하나씩 반복한다고 생각하자.

 

 

만약 동전 리스트의 원소를 하나씩 돌면서,

• 현재 원소가 현재 만들어야 하는 숫자(result)보다 크다면, result를 만들 수 없다는 의미가 되므로 반복문을 종료하면 된다.
• 그 외의 경우엔, 만들어야 하는 숫자 result 까지를 만들 수 있다는 의미가 되므로, result에 현재 원소를 더해주면 된다.
  • 여기서 이 점이 이해가 직관적으로 되지 않았다. (아래에서 이어서 설명하도록 하겠다.)

 

 

만약 result가 2이고, 현재 반복문이 가리키고 있는 원소가 2라면

result 값이 2라는 의미는 정확히 양의 정수 2까지 만들 수 있는 방법이 존재한다는 것을 의미한다.

그러므로 result를 토대로 현재는 1과 2를 만들 수 있으며, 

각각의 방법에 현재 원소인 2를 더해서 3, 4를 만들어 낼 수 있게 된다.

현재 만들 수 있는 정수들	현재 리스트 원소  = 2 (각각 더해줌)	만들어 낼 수 있는 정수들
1	+ 2	--> 3
2	+ 2	--> 4

 

 

근데, 현재 원소가 result보다 커지는 경우를 예시로 들어보자

만약 result가 5이고, 현재 원소가 6이라면

현재는 양의 정수 1, 2, 3, 4, 5를 만들어낼 수 있는데,

현재 원소를 각각 더해서 7, 8, 9, 10, 11 을 만들어 낼 수 있게 된다.

현재 만들 수 있는 정수들	현재 리스트 원소 = 6 (각각 더해줌)	만들어 낼 수 있는 정수들
1	+ 6	--> 7
2	+ 6	--> 8
3	+ 6	--> 9
4	+ 6	--> 10
5	+ 6	--> 11

이 경우에, 6을 만들어낼 수 있는 방법이 없기 때문에, 현재 원소가 result가 커지는 경우 반복문을 종료하는 것이다.

 

 

위의 규칙을 토대로 코드를 작성하면 아래와 같이 코드를 작성할 수 있다.

n = int(input())
coins = list(map(int, input()))
coins.sort()

result = 1

for c in coins:
    if result < c:
        break
    result += c

print(result)

 

---

볼링공 고르기

문제

A, B 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다.
볼링공은 총 N개가 잇으며 각 볼링공마다 무게가 적혀있다.
같은 무게의 공이 여러 개 있을 수 있으며, 각각은 서로 다른 공으로 간주한다.
N개의 공의 무게가 각각 주어질 때 두 사람이 볼링공을 고르는 경우의 수를 구하는 프로그램을 작성하시오.

- input
첫째 줄에 볼링공의 개수 N, 공의 최대 무게 M이 공백으로 구분되어 주어진다.
둘째 줄에 각 볼링공의 무게 K가 공백으로 구분되어 순서대로 자연수 형태로 주어진다.

- output
첫째 줄에 두 사람이 볼링공을 고르는 경우의 수를 출력한다.

- 입력 예시 1
5 3
1 3 2 3 2

- 출력 예시 1
8

- 입력 예시 2
8 5
1 5 4 3 2 4 5 2

- 출력 예시 2
25

 

---

풀이과정

풀이 1 : 이중 반복문을 사용하는 경우

n, m = map(int, input().split())
balls = list(map(int, input().split()))
count = 0

for i in range(n - 1):
    for j in range(i + 1, n):
        if balls[i] != balls[j]:
            count += 1

print(count)

 

• i는 balls 배열의 처음원소부터 마지막에서 두번째까지의 원소를 반복문으로 돈다.
• j는 i에 해당하는 다음 원소부터 마지막 원소까지 반복한다.
• 만약 i와 j에 해당하는 원소가 다른 경우 count를 더해주면 된다.

 

• 이 풀이과정의 단점?
  • 이중반복문을 사용함으로써 시간이 너무 오래 걸린다. :: 시간복잡도 = O(N^2)

 

---

풀이 2 : 이중 반복문을 사용하지 않는 경우 -  추가 리스트 사용하기

n, m = map(int, input().split())
balls = list(map(int, input().split()))
weights = [0] * 10
count = 0  # 경우의 수
total = 0  # 무게를 기준으로 정렬했을때, 지금까지 나온 공의 수

for b in balls:  # 각 무게 당 리스트
    weights[b - 1] += 1

for w in weights:
    count += total * w  # total * 현재 공의 수
    total += w

print(count)

• weights라는 추가 리스트를 사용하여 각각의 무게 - 1이 인덱스가 되도록 각각의 무게에 맞는 볼링공의 개수를 저장하는 배열을 만들어 준다.
• weights라는 반복문을 하나씩 돌며 count와 total을 설정한다. (아래 설명 참고)

 

 

만약 입력이 다음처럼 주어지고,

5 3
1 3 2 3 2

 

weights 배열이 다음처럼 설정된다고 가정하자.

1 2 2 0 0 0 0 0 0 0

 

weights의 원소(w)를 하나하나 돈다고 가정할때,

결과인 count에 앞에 나왔던 공의 개수 * 현재 공의 개수를 더해주면 된다.

그러므로, 앞에 나왔던 공의 개수를 알려주는 변수인 total을 사용하여, count에 저장해 줄 수 있다.

 

앞의 예시에 적용해보면,

• w = 1
  
  • (이전에 나왔던 공의 개수) total = 0이고, count += total * w 계산하여 ===> count는 0이 됨.
  • total += w을 계산하여 ===> total은 1이 됨.
• w = 2
  • total이 1이므로, count += total * w를 계산하여 count += 2 ===> count = 2
  • total += 2 ===> total = 3
• w = 2
  • total이 3이므로, count += total * w 계산하여 count += 6 ===> count = 8
  • total += 2 ===> total = 5
• ( 이후 0 이므로 생략 )

 

 

• 이 풀이과정의 장점
  • 추가 배열을 사용하지만, 시간이 굉장히 단축됨. :: 시간 복잡도 = O(N)

 

---

무지의 먹방 라이브

(heapq 모듈을 사용함. heapq모듈의 사용법은 아래 글을 참고한다.)

https://5ji-record.tistory.com/144

[Python 자료구조] max-heap, min-heap과 heapq 모듈

 

이 문제는 시간이 적게 걸리는 음식부터 확인해야 하므로,

heapq 모듈의 min-heap (우선순위 큐) 개념을 적용해야 한다.

 

 

예시로, 다음과 같은 3개의 음식이 있으며, K를 15초라고 가정한다.

• 1번 음식: 8초 소요
• 2번 음식: 6초 소요
• 3번 음식: 4초 소요

 

초기 단계에서는 모든 음식을 최소 힙에 집어넣는다.

마지막에 K초 후에 먹어야 할 음식의 번호를 출력해야 하므로 우선순위 큐에 삽입할 때

(음식 시간, 음식 번호) 형태의 튜플 형태로 삽입한다.

 

 

먼저, 가장 적게 걸리는 음식인 3번 음식을 뺀다.

다만 시간 비교를 먼저 해주어야 하는데,

3(남은 음식의 개수) * 4(3번 음식을 먹는 시간) <= k (15) 이므로

k에서 3 * 4를 빼주면, 남은 시간은 3초가 된다.

 

 

다음으로 두번째로 적게 걸리는 음식을 뺄 차례인데,

전체 남은 시간은 3초이고,

2번 음식을 모두 먹는 시간은

2(남은 음식의 개수) * ( 6 - 4) (2번 음시을 먹는 시간 - 이전동안 먹은 시간) 이므로 4이다.

그러므로 전체 남은 시간보다, 2번 음식을 모두 먹는 시간이 더 길기 때문에, 2번 음식을 빼지 못한다.

 

따라서 다음으로 먹어야 할 음식의 번호를 찾아 출력해준다.

남은 시간은 3초, 남은 음식은 2개이므로 다음으로 먹을 음식은 2번이다.

[(8, 1), (6, 2), (8, 1), (6, 2) ... ]

 

위의 알고리즘을 코드로 나타내면 다음과 같다.

import heapq

def solution(food_times, k):
    if sum(food_times) <= k:
        return -1
        
    q = []  # min heap
    for i in range(len(food_times)):
        # (음식 시간, 음식 번호) 형태로 min heap에 저장
        heapq.heappush(q, (food_times[i], i + 1))

    n = len(food_times)  # 음식 개수
    sum_value = 0  # 먹기 위해 사용한 시간
    prev = 0  # 직전에 다 먹은 음식의 시간

    # 시간 충분한 경우
    while sum_value + ((q[0][0] - prev) * n) <= k:
        now = heapq.heappop(q)[0]
        sum_value += (now - prev) * n
        n -= 1
        prev = now

    # 시간이 충분하지 않은 경우
    result = sorted(q, key=lambda x: x[1])  # 음식의 번호 기준으로 정렬
    return result[(k - sum_value) % n][1]

(여기서 sorted 함수를 사용할때 key를 lambda식으로 설정해주는데, lambda식의 사용법은 다음 글을 참고한다.)

https://5ji-record.tistory.com/145

[Python 문법] 람다(lambda)