그리디 알고리즘으로 생각하기

0. 학습 참고자료

• 알고리즘 코딩테스트(파이썬) 문제33
• 백준 1715번(골드4)

1. 그리디 알고리즘식 생각의 방향

현재 상황에서 최선의 선택을 한다. 이후 과정에서는 앞에 했던 선택이 최선의 선택이 아니었음을 깨닫더라도

2. 우선순위 큐가 그리디랑 잘 맞는 이유

아직 많은 문제를 풀어본 것은 아니라서 100% 장담은 못하겠다
하지만, 1715번 문제처럼 합치고 넣고 다시 합치고 하는 과정에서는 일반적인 리스트 구조로 문제를 푸는 것보다 효율적이라고 생각한다

이 문제를 구간합 방법으로 구현해봤는데 역시나 시간오류에서 걸렸던 경험적인 근거로 설득할 수 있다

3. 코드로 문제 풀어보기

import sys
input = sys.stdin.readline # 여기는 입력이 다중으로 들어로 때 빠르게 처리할 수 있는 라이브러리

from queue import PriorityQueue
myque = PriorityQueue() # 우선순위 큐를 호출하는 방법

N = int(input()) # 카드 묶음 개수

for _ in range(N):
    data = int(input())
    myque.put(data) # 이게 우선순위 큐 형태로 데이터를 넣어준다
    				# 반복인자를 생략해도 되는 점 또한 일반 리스트보다 나은 점인듯

data1 = 0 # 큐에 쌓인 데이터를 뽑으면 사라지니까 객체로 임시 저장
data2 = 0
count = 0 # 정답으로 출력할 객체

while myque.qsize() > 1:
    data1 = myque.get() # get으로 가져오면 큐에는 데이터가 없음
    data2 = myque.get()
    print("data1 : ", data1) # 여기 출력문은 내가 생각한 대로 진행되는지 파악하기 위한 부분, 문제 제출시에는 지워야함
    print("data2 : ", data2)
    temp = data1 + data2 # 앞에 계산한 큐에 쌓인 2개의 값을 합침
    
    print("temp :", temp) # 이 부분도 지워야 함
    count += temp
    myque.put(temp) # 다시 넣어서 비교하는 횟수를 카운트 하기 위해서

print(count) # 답 출력

부록. 우선순위큐 명령어

.get() : 큐에 있는 데이터를 가져옴
.put(넣어줄 값) : 큐에 데이터를 넣음
.qsize() : 큐의 크기를 가져옴
.empty() : 큐가 비어있는지 확인

자료구조상 while문 하고 잘 맞는 부분이 많이보임