그리디-그리디 알고리즘

이론

📖 그리디 알고리즘
현재 상태에서 볼 수 있는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘.
But, 항상 최적의 해를 보장하지는 못한다는 단점이 있다.

문제풀이

📖 백준 1715 (🔗 백준 1715 문제)

✏ 그리디 알고리즘.

✏ .sort() 를 사용하여 오름차순으로 정렬해서 계산해야 비교횟수가 최소가 된다.

#그리디 알고리즘 - 우선순위 큐 
from queue import PriorityQueue
import sys
input=sys.stdin.readline

n=int(input())
myqueue=PriorityQueue()
data1=0
data2=0
total_sum=0

for i in range(n):
	size=int(input())
	myqueue.put(size)

while myqueue.qsize()>1:
	data1=myqueue.get()
	data2=myqueue.get()
	sum=data1+data2
	total_sum+=sum
	myqueue.put(sum)

print(total_sum)

📖 백준 1931 (🔗 백준 1931 문제)

✏ 그리디 알고리즘.

✏ 종료시간이 빠른 순서대로 정렬.

✏ 종료시간이 같다면 시작시간이 빠른 순서대로 정렬.

✏ 종료시간이 제일 빠른것부터 선택해서 탐색시작. 탐색하다가 앞에 선택한 시간대와 겹치지 않는 시간대가 나오면 선택한다.

#그리디 알고리즘
#종료시간이 빠른 순서대로 정렬 (종료시간이 같으면 시작시간을 기준으로 시작시간이 빠른 순서로 정렬)
#종료시간이 제일 빠른것부터 선택
#탐색하다가 앞에 선택한 시간대와 겹치지 않는 시간대가 나오면 선택

import sys
input=sys.stdin.readline

n=int(input())
arr=[[0]*2 for i in range(n)]
count=0

for i in range(n):
	start,end=map(int,input().split())
	arr[i][0]=end
	arr[i][1]=start

arr.sort()

setting_end=-1

for i in range(n):
	if arr[i][1]>=setting_end:
		setting_end=arr[i][0]
		count+=1

print(count)

📖 백준 1541 (🔗 백준 1541 문제)

✏ 그리디 알고리즘.

✏ 최솟값을 만들려면, 가장 작은값 - 가장큰값 을 해야된다.

✏ 따라서, 더하기부분에 괄호를 쳐서 한 번에 뺀다.

#그리디 알고리즘
#최솟값 -> 작은수-큰수
#괄호 -> 더하기에 해당하는 부분에 괄호쳐서 한번에 뺀다.

import sys
input=sys.stdin.readline

test=list(map(str,input().split("-")))
result=0

def Sum(a):
	sum=0
	seg=str(a).split("+")

	for i in seg:
		sum+=int(i)

	return sum

for i in range(len(test)):
	seg2=Sum(test[i])
	if i==0:
		result+=seg2
	else:
		result-=seg2

print(result)

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준