그리디

06-1 그리디 알고리즘

• 그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

[그리디 알고리즘의 핵심 이론]
1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복한다.

📌 문제 032) 동전 개수의 최솟값 구하기

시간 제한 1초, 실버 III, 백준 11047번

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가격의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가격 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

10 4200 # 동전 수, 목표 금액
1
5
10
50
100
500
1000
5000
10000
50000

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

6

1단계 문제 분석

• 전형적인 그리디 알고리즘 문제이다.
• 그리디 알고리즘으로 풀 수 있도록 뒤의 동전 가격 Ai가 앞에 나오는 동전 가격 Ai-1의 배수가 된다는 조건을 부여했다.
• 즉, 동전을 최소로 사용하여 K를 만들기 위해서는 가장 가격이 큰 동전부터 차례대로 사용하면 된다.

1. 가격이 큰 동전부터 내림차순으로 K보다 가격이 작거나 같은 동전이 나올 때까지 탐색한다.
2. 탐색을 멈춘 동전의 가격으로 K를 나눠 몫은 동전 개수에 더하고, 나머지는 K값으로 갱신한다.
3. 1~2번을 나머지가 0이 될 때까지 반복한다.

2단계 슈도 코드

N(동전 개수) K(목표 금액)
A(동전 데이터 리스트)

for N만큼 반복:
	A 리스트 저장

# 가치가 큰 동전부터 선택해야 개수를 최소로 구성할 수 있음
for N만큼 반복 -> N-1 ~ 0으로 역순으로 반복:
	if 현재 K보다 동전 가치가 작거나 같으면:
    	동전 수 += 목표 금액 / 현재 동전 가치
		목표 금액 = 목표 금액 % 현재 동전 가치

누적된 동전 수 출력

3단계 코드 구현

N, K = map(int, input().split())
A = [0] * N

for i in range(N):
    A[i] = int(input())

count = 0

for i in range(N - 1, -1, -1): # 역순으로 출력
    if A[i] <= K:
        count += int(K / A[i])
        K = K % A[i]

print(count)

📌 문제 033) 카드 정렬하기

시간 제한 2초, 골드 IV, 백준 1715번

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.
매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.
N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

3 # 카드 묶음 수
10
20
40

출력

첫째 줄에 최소 비교 횟수를 출력한다.

6

1단계 문제 분석

• 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 끼친다.
• 따라서 카드 묶음의 카드 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법이다.
• 현재 데이터 중 가장 작은 카드 개수를 가진 묶음 2개를 뽑아야 하고, 이 2개를 기준으로 합친 새로운 카드 묶음을 다시 데이터에 넣고 정렬해야 한다.
• 즉, 데이터의 삽입, 삭제, 정렬이 자주 일어나므로 우선순위 큐(오름차순 정렬)를 이용하자.

1. 현재 카드 개수가 가장 작은 묶음 2개를 선택해 합친다.
2. 합친 카드 묶음을 다시 전체 카드 묶음 속에 넣는다.
3. 1~2번 과정을 카드 묶음이 1개만 남을 때까지 반복한다.

2단계 슈도 코드

N(카드 묶음 개수)
pq(우선순위 큐)

for N만큼 반복:
	우선순위 큐에 데이터 저장

# 자동 정렬에 따라 작은 카드 묶음 2개를 쉽게 뽑을 수 있음
while 우선순위 큐 크기가 1이 될 때까지:
	2개 카드 묶음을 큐에서 뽑음
    2개 카드 묶음을 합치는 데 필요한 비교 횟수를 결괏값에 더함
    2개 카드 묶음의 합을 우선순위 큐에 다시 넣음

결괏값 출력

3단계 코드 구현

from queue import PriorityQueue
N = int(input())
pq = PriorityQueue()

for _ in range(N):
    data = int(input())
    pq.put(data)

data1 = 0
data2 = 0
sum = 0

while pq.qsize() > 1:
    data1 = pq.get()
    data2 = pq.get()
    temp = data1 + data2
    sum += temp
    pq.put(temp)

print(sum)

📌 문제 034) 수를 묶어서 최댓값 만들기

시간 제한 2초, 골드 IV, 백준 1744번

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다.
예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열의 합을 구하면 0+1+2+4+3+5 = 15이다. 하지만, 2와 3을 묶고, 4와 5를 묶게 되면, 0+1+(2 x 3)+(4 x 5) = 27이 되어 최대가 된다.
수열의 모든 수는 단 한번만 묶거나, 아니면 묶지 않아야한다.
수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오.

입력

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

4 # 수의 개수
-1
2
1
3

출력

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

6

1단계 문제 분석

• N의 최대 범위가 10,000이므로 시간 복잡도와 관련된 제약은 적다.
• 가능한 큰 수들끼리 묶어야 결괏값이 커진다는 것을 알 수 있다.
• 주어진 수열이 1, 2, 3, 4라면 1x4+2x3보다 1x2+3x4의 결괏값이 더 큰다.
• 또한 음수끼리 곱하면 양수로 변하는 성질을 추가로 고려하자.

1. 수의 집합을 1보다 큰 수, 1, 0, 음수 이렇게 4가지 유형으로 나눠 저장한다.
2. 1보다 큰 수의 집합을 정렬해 최댓값부터 차례대로 곱한 후에 더한다. 원소 개수가 홀수일 때 마지막 남은 수는 그대로 더한다.
3. 음수의 집합을 정렬해 최솟값부터 차례대로 곱한 후에 더한다. 원소의 개수가 홀수일 때, 수열에 0이 있다면 1개 남는 음수를 0과 곱해 0을 만들고, 수열에 0이 없다면 그대로 더한다.
4. 2~3번에서 구한 값을 더하고, 그 값에 숫자 1의 개수를 더한다.

2단계 슈도 코드

N(카드 묶음 개수)
plusPq(양수 우선순위 큐) minusPq(음수 우선순위 큐)
one(1의 개수 카운트) zero(0의 개수 카운트)

for N만큼 반복:
	# 양수 우선순위 큐는 내림차순 정렬을 위해 -1을 곱하여 저장
    데이터를 4개의 그룹에 분리 저장

# 양수 우선순위 큐 처리
while 양수 우선순위 큐 크기가 2보다 작을 때까지:
	수 2개를 큐에서 뽑음
    2개의 수를 곱한 값을 결괏값에 더함

if 양수 우선순위 큐에 데이터가 남아 있으면:
	해당 데이터를 결괏값에 더함

# 음수 우선순위 큐 처리
while 음수 우선순위 큐 크기가 2보다 작을 때까지:
	수 2개를 큐에서 뽑음
    2개의 수를 곱한 값을 결괏값에 더함

if 음수 우선순위 큐에 데이터가 남아 있고, 데이터 0이 1개도 없으면:
	해당 데이터를 결괏값에 더함

숫자 1의 개수를 결괏값에 더함
결괏값 출력

3단계 코드 구현

from queue import PriorityQueue
N = int(input())
plusPq = PriorityQueue()
minusPq = PriorityQueue()
one = 0
zero = 0

for i in range(N): # 4가지로 데이터 분리 저장
    data = int(input())
    if data > 1:
        plusPq.put(data * -1) # 양수 내림차순 정렬을 위해 -1을 곱하여 저장
    elif data == 1:
        one += 1
    elif data == 0:
        zero += 1
    else:
        minusPq.put(data)

sum = 0

while plusPq.qsize() > 1: # 양수 처리
    first = plusPq.get() * -1
    second = plusPq.get() * -1
    sum += first * second

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

while minusPq.qsize() > 1: # 음수 처리
    first = minusPq.get()
    second = minusPq.get()
    sum += first * second

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

sum += one # 1 처리
print(sum)