[알고리즘] 그리디 Greedy

그리디(Greedy)

• 현재 상황에서 가장 최적의 답을 선택하는 알고리즘
• 최종적으로 최적의 해가 나온다는 보장이 없다.
• 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성의 문제에 적합하다.
  • 최적 부분 구조 예시 : (서울과 대구의 최단 경로) + (대구와 부산의 최단 경로) = 서울과 부산의 최단 경로
• 한 번의 선택이 다음 선택에 무관해야 하고, 매 순간의 최적해가 문제에 대한 최적해여야 한다.
• 활용 예시
  • 거스름돈, 다익스트라 알고리즘, 허프만 코드, 크루스칼 알고리즘

 

그리디 문제 - 11047번 동전 0

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

11047번: 동전 0

 

# n, k = 10, 4200  # 동전 종류, 구하려는 값 - 동전의 최소 개수 구하기
# arr = [1, 5, 10, 50, 100, 500, 1000, 5000, 10000, 50000]
n, k = map(int, input().split())
arr = []
for _ in range(n):
    arr.append(int(input()))
arr = sorted(arr, reverse=True)
cnt = res = 0

for x in arr:
    if k >= x:
        cnt = k // x
        res += cnt
        k = k - (x * cnt)
    if k <= 0:
        break
print(res)

 

그리디 문제 - 1931번 회의실 배정

- 최대 회의 횟수 구하기

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

1931번: 회의실 배정

n = int(input())  # 회의 수 - 회의가 겹치지 않게 진행할 수 있는 회의 최대 개수 구하기
arr = [[0] * 2 for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    arr[i][0] = a # 회의 시작 시간
    arr[i][1] = b # 회의 끝나는 시간

#n = 11
#arr = [[1, 1], [1, 5], [0, 6], [5, 7], [3, 8], [5, 9], [6, 10], [8, 11], [8, 12], [2, 13], [12, 14]]
#n = 3
#arr = [[1,1],[1,1],[0,1]]
arr.sort(key=lambda x: (x[1], x[0])) # 두번째 값이 같은 경우, 첫번째 값으로 오름차순
time = cnt = start = end = 0

for element in arr:
    start = element[0]
    end = element[1]
    if time <= start:
        time = end
        cnt += 1
print(cnt)

 

그리디 문제 - 11000번 강의실 배정

- 최소 강의실 개수 구하기

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

11000번: 강의실 배정

# 최소 강의실 개수 구하기
import heapq
import sys

input = sys.stdin.readline
N = int(input())  # 수업의 개수

class_list = []

for _ in range(N):
    x, y = map(int, input().split())
    class_list.append([x, y])

class_list.sort()
heap = []
heapq.heappush(heap, class_list[0][1])  # 첫 번째 강의 끝나는 시간
# heap 최소 힙 유지 = 0 번째 인덱스는 가장 작은 값

for idx in range(1, N):
    start, end = class_list[idx]
    if start < heap[0]: # 빠른 시작 시간 < 앞에서 가장 빨리 끝나는 값
        heapq.heappush(heap, end) # 새 강의실 추가
    else: # 강의실 유지, 강의 시간 갱신
        heapq.heappop(heap)
        heapq.heappush(heap, end)
print(len(heap))

 

 

그리디 문제 - 2217번 로프

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

2217번: 로프

 

# n = 2  # 로프의 개수
# arr = [10, 15]  # 로프가 버틸 수 있는 최대 중량
n = int(input())
arr = []
for _ in range(n):
    arr.append(int(input()))
arr = sorted(arr, reverse=True)
maxRes = 0

# 내림차순으로 들을 수 있는 로프 개수 * 현재 무게를 계산해서 최대값을 구해준다.
for k in range(n):
    maxRes = max(arr[k]*(k+1), maxRes)
print(maxRes)

 

그리디 문제 - 1026번 보물

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

1026번: 보물

 

# n = 5  # 정수의 개수
# arrA = [1, 1, 1, 6, 0]  # A 정수 배열
# arrB = [2, 7, 8, 3, 1]  # B 정수 배열

n = int(input())
arrA = list(map(int, input().split()))
arrB = list(map(int, input().split()))

# S = A[0] * B[0] + A[1] * B[1] + ...+ A[N-1] * B[N-1]
# 계산 값을 가장 작게 만들기 위해서는 각 배열을 오름차순, 내림차순 해준다.
arrA.sort()
arrB.sort(reverse=True)
res = 0

for x in range(n):
    res += arrA[x]*arrB[x]

print(res)

 

그리디 문제 - 8980번 택배

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

8980번: 택배

 

# 트럭 한 대로 배송할 수 있는 최대 박스 수 출력
N, C = map(int, input().split())  # 마을의 수, 트럭 용량
M = int(input())  # 박스 정보 개수
info = []
res = 0

for _ in range(M):
    # 박스를 보내는 마을, 박스를 받는 마을, 보내는 박스의 개수
    from_box, to_box, num_box = map(int, input().split())
    info.append((from_box, to_box, num_box))

sort_info = sorted(info, key=lambda x: x[1]) # 가장 빨리 받는 순서대로 정렬
remain = [0] * (N+1) # 남은 상자

for item in sort_info:
    start, end, box = item[0], item[1], item[2]
    max_box = box
    for i in range(start, end): # 시작점부터 도착지까지 보낼 수 있는 박스 개수
        max_box = min(max_box, C - remain[i])
    # print(max_box, C-remain[i])
    for j in range(start, end):
        remain[j] += max_box
    res += max_box
print(res)

---

https://hhiyeon.tistory.com/252

[백준] 1541번 잃어버린 괄호

 

https://hhiyeon.tistory.com/253

[백준] 11501번 주식

 

https://hhiyeon.tistory.com/254

[백준] 2170번 선긋기

 

https://hhiyeon.tistory.com/255

[백준] 1744번 수묶기