[Python] 그리디

# 1. 그리디 알고리즘

• 현재 상태에서 보는 선택지 중 최선의 선택지가 최종적으로 최선이라고 가정하는 알고리즘.
• 수행과정
  • 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
  • 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
  • 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 처음으로 돌아가 같은 과정을 반복한다.
• DP보다 구현이 쉽고 시간복잡도가 우수하다.
• 그러나 항상 최적의 해를 보장하지 못하므로 논리 유무를 살피는 것이 중요한 문제.

https://www.acmicpc.net/problem/11047

11047번: 동전 0

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: # 현재 동전의 가치가 K보다 작거나 같으면 구성에 추가
        count += int(K/A[i])
        K = K%A[i] # K를 현재 동전을 사용하고 남은 금액으로 갱신

print(count)

• 전형적인 그리디 문제
• 그리디 알고리즘으로 풀 수 있도록 뒤이은 가격 Ai가 앞선 가격 Ai-1의 배수가 된다는 조건이 주어졌다.

 

# 우선순위 큐 자료구조

• 그리디 알고리즈메서는 최선의 선택을 위해 우선순위 큐를 사용하는 경우가 많다.
• 파이썬에서는 PriorityQueue 혹은 heapq를 이용해서 구현한다.
• PrioriryQueue는 객체 자체를 우선순위 큐 형태로 만들어 사용하고, heapq는 기본적인 list 객체를 대상으로 여러 함수를 이용해 직접 우선순위 큐를 구현한다.

from queue import PriorityQueue

myque = PriorityQueue() # myque를 우선순위 큐로 생성

put(data) # 원소 추가
get() # 큐에서 데이터 꺼내기
qsize() # 큐 사이즈 가져오기
empty() # 큐가 비어있는지 확인

import heapq

mylist= [] # 리스트 생성
heapq.heappush(mylist, 1) # 리스트에 데이터를 넣을 때 heapq를 이용해서 저장

heappush(mylist, data) # data를 list(heap 자료구조) 형태로 저장
heappop(mylist) # list(heap 자료구조)에서 데이터 꺼내기
heapify(mylist) # 일반적인 list를 heap 자료구조로 변환

 

 

https://www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

from queue import PriorityQueue
N = int(input()) # 카드 묶음 개수
pq = PriorityQueue() # 우선순위 큐

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

data1 = 0
data2 = 0
sum = 0

# 자동 정렬에 따라 작은 카드 묶음 2개를 쉽게 뽑을 수 있음
while pq.qsize()>1:
    data1 = pq.get()
    data2 = pq.get() # 2개 카드 묶음을 큐에서 뽑기
    temp = data1 + data2 
    sum += temp # 카드 묶음을 합치는데 필요한 비교 횟수를 결과값에 더하기
    pq.put(temp) # 2개 카드 묶음의 합을 우선순위 큐에 넣기

print(sum)

• 먼저 선택된 카드 묶임이 비교 횟수에 더 많은 영향을 끼친다. 즉, 카드의 개수가 작은 것부터 합치는 것이 전체 비교 횟수를 줄이는 방법이다.
• 따라서 큐의 크기가 1(정답)이 죌때까지 작은 카드 개수 2개를 뽑고 합친 후 다시 데이터에 넣은 후 정렬하는 것을 반복해야 한다.
• 데이터의 정렬, 삭제, 삽입이 자주 일어나므로 우선순위 큐를 이용해 푼다.

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

from queue import PriorityQueue
N = int(input()) # 카드 묶음 개수
plusq = PriorityQueue() # 양수 우선순위 큐
minusq = PriorityQueue() # 음수 우선순위 큐
one = 0 # 1개수 카운트
zero = 0 # 0개수 카운트

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

sum = 0

while plusq.qsize() > 1 : # 양수 처리
    first = plusq.get() * -1
    second = plusq.get() * -1
    sum += first*second # 내림차순으로 뽑은 2개의 수를 곱한 후 결과값에 더하기

if plusq.qsize() > 0:
    sum += plusq.get() * -1 # 양수 우선순위 큐에 데이터가 남아있으면 결과값에 더하기

while minusq.qsize() > 1: # 음수 처리
    first = minusq.get()
    second = minusq.get()
    sum += first*second # 2개의 수를 곱한 값을 결과값에 더함

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

sum += one # 숫자 1의 개수 결과값에 더하기
print(sum)

• 가능한 큰 수들끼리 묶어야 결과값이 커진다. 따라서 우선순위 큐에 정렬할 때 내림차순이 되도록 -1을 곱해서 put한다.(꺼낼 때는 다시 -1 곱해주기)
• 수의 집합을 1보다 큰 수, 1, 0, 음수로 나누어 정렬한다.
• 1보다 큰 수의 집합은 최댓값부터 차례대로 곱한 후에 더하고, 원소의 개수가 홀수일 때 마지막 남은 수는 그대로 더한다.
• 음수의 집합은 최솟값(절댓값이 큰 수)부터 차례대로 곱한 후에 더한다. 원소의 개수가 홀수 일때, 수열에 0이 있다면 남은 음수를 9과 곱해 0으로 만들고, 0이 없다면 그대로 더한다.
• 위 과정에서 구한 값과 숫자 1의 개수를 더한다.

 

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

N = int(input())
A = [[0]*2 for _ in range(N)]

for i in range(N):
    S, E = map(int, input().split())
    A[i][0] = E # 종료 시간 우선 정렬이 먼저이므로 0번째에 종료 시각을 먼저 저장
    A[i][1] = S

A.sort() # 첫번째 원소(종료 시각) 기준으로 정렬하며, 종료 시각이 같으면 시작 시각 기준(두번째 원소)로 정렬한다.
count = 0
end = -1

for i in range(N):
    if A[i][1]>=end: # 겹치지 않는 다음 회의가 나온 경우
        end = A[i][0] # 종료 시각 업데이트
        count += 1 # 진행할 수 있는 회의 수 1 증가

print(count)

• 현재 회의의 종료 시간이 빠를 수록 다음회의와 겹치지 않게 시작하는데 유리하다. 따라서 종료 시간이 빠른 순서대로 정렬해 적절하게 회의실을 선택한다.
• 만약 종료 시간이 같아면, 시작 시간을 기준으로 정렬한다.
• 순차적으로 탐색해다가 시간이 겹치지 않는 회의가 나오면 선택한다.
• 이차원 리스트 정렬은 lambda 식을 이용하거나, 데이터 입력 순서를 통하여 조정할 수 있다.

# 만약 [시작시간],[종료시간]으로 2차원 리스트를 이용하는 경우
lists.sort(key = lambda x: (x[1], x[0]))

 

 

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

answer = 0
A = list(map(str, input().split("-")))

# 현재 String에 있는 수를 모두 더하는 함수 구현
def mySum(i): # -로 나뉜 그룸들의 합을 구하는 함수
    sum = 0
    temp = str(i).split("+")
    for i in temp: 
        sum += int(i) # String을 int형으로 변환 후 리턴값에 더하기
    return sum

for i in range(len(A)):
    temp = mySum(A[i])
    if i==0:
        answer += temp # 가장 앞에 있는 값만 더하기
    else:
        answer -= temp # 뒷부분의 값은 합쳐서 빼기

print(answer)

• 가장 작은 최솟값을 만들기 위해서는 가능한 한 큰 수를 빼야 한다.
• 더하기에 해당하는 부분에 괄호를 쳐서 먼저 모두 계산한 후 빼기를 실행한다.

 

---

# 회고

 

DFS, BFS, DP 이런거 하다가 그리디 하면 너무 행복하다. 

파이썬의 기본 함수들을 최대한 잘 이용하는 것도 중요할듯.