Greedy(탐욕법)

개념

• 최적해를 구하는 데에 사용되는 근사적인 방법.
• 여러 경우 중 하나를 결정해야 할 때 마다 그 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달
• 순간마다 하는 선택은 그 순간에 대해 지역적으로 치적이지만 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그 것이 최적이라는 보장은 없다.
• 하지만 **탐욕알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 최종적(전역적)으로 최적인 문제들이다.

그리디로 문제를 해결하기 위한 조건

1. 탐욕스런 선택 성질(greedy choice property)

• 앞선 선택이 이후의 선택에 영향을 주지 않는다.
• 각 지역적 최적의 선택이 모두 전체에 포함됨

2. 최적 부분 구조 조건(Optimal Substructure)

• 전체 문제를 작은 부분으로 나누어 해결 할 때, 전체 문제의 해결 방법이 부분 문제의 최적의 해결 방법들로 구성된다.

실제 문제 풀이에서 필요한 것

• 기본적이고 합리적인 아이디어와 예시를 통해 과연 최적해가 맞는지 분석한다.
  • 많은 경우 입력 값이 크고, 완전 탐색이 불가능한 경우가 많다.
• 현재 최적의 선택이 다음 선택에 영향을 주는가?
• 무엇을 욕심 낼 것인가?
• 정렬이나 우선순위큐의 기준이 된다.
• 하기의 문제를 풀어보면서 적용해보도록 하겠다.

동전 문제

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

# baekjoon 11047 동전 0
# 동전 N종류 각각 동전을 많이 가지고 있음
# 가치의 합을 K로 만들려고 한다.
# 이 때 필요한 동전의 개수를 최솟값을 구하라
# 우선 N은 10종류, K는 10억 숫자가 10억이 나온게 의심스럽다
# 10억이면 선형 탐색 한 번이 되지 않는다.
# N은 종류, K는 가치의 합,동전의 가치 A가 오름차순으로 주어진다.
# 1<=A<=1000000, A1 = 1, Ai는 Ai-1의 배수

# 앞의 선택이 뒤의 결과에 영향을 주지 않음
# 최소 최대를 구하는 문제
# 가치가 10억 알고리즘을 적용해야 하는 문제
# 가치가 큰 기준으로 정렬하는 것이 중요하다.

n, k = map(int, input().split())
arr = [int(input()) for i in range(n)]
arr.reverse()
cnt = 0

for i in arr:
    # 만약 동전의 가치가 목표 가치보다 크다면 continue
    if k < i:
        continue
    # 몫을 구한다.
    t = k // i
    # 가치에서 동전 가치 만큼 빼준다.
    k -= i * t
    # 갯수를 더해준다.
    cnt += t

print(cnt)

강의실 문제
https://www.acmicpc.net/problem/11000

# baekjoon 11000 강의실 배정 (그리디)
# Si에 시작해서 Ti에 끝나는 N개의 수업이 주어진다.
# '최소'의 강의실을 사용해서 모든 수업을 가능하게 해야 한다.
# 1<=N<=200,000
# 0 <= S < T <= 10^9
# 기준 시작 시간이 작고 끝나는 시간도 작고
# 수업 종료가 다음 수업 시작 보다 크면 heappush
# 수업 종료가 다음 수업 시작 보다 작으면 heappop 그리고 heappush
# 입력 값이 크기 때문에 input으로 받으면 안 되고, sys.stdin.readlin()로 받아야 한다.

# from queue import PriorityQueue
import sys
import heapq

n = int(input())
q = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
room = []

# for i in range(n):
#     start, end = map(int, input().split())
#     q.append([start, end])

q.sort()

# 강의실에 끝나는 시간을 넣어준다.
heapq.heappush(room, q[0][1])

for i in range(1, n):
    # 현재 회의실 끝나는 시간보다 다음 강의 시작시간이 빠르면
    if q[i][0] < room[0]:
        # 새로운 회의실 개설
        heapq.heappush(room, q[i][1])
    # 현재 회의실 끝나는 시간보다 다음 강의 시작 시간이 느리면
    else:
        # 강의실 빼주고
        heapq.heappop(room)
        # 다시 채워준다.
        heapq.heappush(room, q[i][1])

print(len(room))

회의실 배정
https://www.acmicpc.net/problem/1931

# baekjoon 1931 회의실 배정 (그리디)
# 한 개의 회의실 이를 사용하고자 하는 N개의 회의에 대하여
# 회의 I에 대해 시작과 끝나는 시간이 주어짐
# 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 '최대' 개수를 찾아보자
# 회의의 수가 100,000이 주어진다. O(n^2)이 되면 시간초과가 생기기 때문에 알고리즘을 사용한다.
# 시작 시간과 끝나는 시간은 2^31 - 1 작거나 같은 자연수 또는 0이다.
# 그리디나 PQ를 사용해야 된다고 판단하고 시작한다.
# 입력 값이 많을 수 있기 때문에 input 대신 readline을 사용한다.
# 끝나는 시간이 빠를수록 여러 개의 회의를 넣을 수 있다.
# 정렬 기준을 끝나는 시간이 빠른 순서대로 정렬한다.
# list.sort(key=lambda x:(x[0],x[1])

import sys
n = int(input())
q = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
room = []

# 끝나는 시간으로 정렬, 그 후 시작하는 시간으로 정렬
# 정렬하는 표현식 잘 기억할 것
q.sort(key=lambda x: (x[1],x[0]))

# 첫 번째 회의가 끝나는 시간 넣는다.
room.append(q[0][1])
# 두 번째 회의부터 반복
for i in range(1,n):
    # 회의가 끝나는 시간이 다음 회의 시작 시간 보다 같거나 작으면
    if room[-1] <= q[i][0]:
        # 해당 인덱스의 회의가 끝나는 시간을 넣는다.
        room.append(q[i][1])
    # 회의가 끝나는 시간이 다음 회의 시작 시간 보다 크면
    else:
        continue

print(len(room))