[Python] 백준 온라인 저지 Greedy Algorithm(그리디 알고리즘) - 1

그리디 알고리즘(Greedy Algorithm)

"매 선택에서 지금 이 순간 가장 최적인 답을 선택하여 적합한 결과를 도출하자"

Greedy(탐욕, 욕심쟁이)라는 이름처럼, 지금 당장 최적인 답을 선택하는 과정을 단순 반복하여 결과를 도출하는 알고리즘이다. 말 그대로 각 단계에서 미래를 생각하지 않고, 그 순간 최선의 선택을 하는 기법이기 때문에 최종적으로는 최적의 해를 보장하지 못한다.

• 지역적(local)으로는 최적의 선택이지만, 전체적(global)으로는 최적의 해가 아닐 수 있다.
• 매 순간 최적을 따라가면 1-1-1-100이지만, 중간에 살짝 먼 길을 섞어 1-1-10-10으로 움직일 때 최적일 수 있기 때문.

그리디 알고리즘은 탐욕 선택 속성(Greedy Choice Property), 최적 부분 구조(Optimal Substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. 즉, 한 번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간 최적해가 문제에 대한 최적해여야 한다는 의미이다.

• 탐욕 선택 속성(Greedy Choice Property) : 현재 선택이 이후의 선택에 영향을 주지 않음
• 최적 부분 구조(Optimal Substructure) : 매 순간 최적의 해가 문제 전체에 대한 최적의 해여야 함

위 조건을 만족하는 경우 그리디 알고리즘을 이용하면 아주 빠른 속도로 정답을 찾아낼 수 있다.

• 근사 알고리즘 : 위 조건에 부합하지 않더라도, 어느 정도 적합한 수준의 해답을 찾을 수도 있다. 최적이 아닌 "되는가" 또는 "적당히 괜찮은 방법"을 찾을 때 사용한다는 뜻. 계산 속도가 정확한 알고리즘에 비해 빠른 경우가 많아 실용적!

---

 

11047번 동전 0

문제	준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.
입력	첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력	첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

• 나열된 동전 중 금액이 높은 순으로 남은 금액과 비교하며 동전의 개수를 카운팅한다.

n, k = map(int, input().split())
a = [0] * n # n개의 동전

for i in range(n):
    a[i] = int(input())

count = 0 # 필요한 동전의 개수

for i in range(n-1, -1, -1):
    if a[i] <= k:
        count += (k // a[i]) # 동전의 개수
        k = k % a[i] # 남은 금액

print(count)

 

1931번 회의실 배정

문제	한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
입력	첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.
출력	첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

• 회의가 빨리 끝나는 순으로 정렬한 뒤 최대한 많은 회의를 할 수 있도록 구성해야 함.
• 끝나는 시간의 오름차순으로 정렬 → 시작하는 시간의 오름차순으로 정렬
• Python의 sort를 이용하는 방법
  • 1. (2번 sort) 전체를 시작 시간의 오름차순으로 정렬 → 정렬된 리스트를 다시 끝나는 시간으로 오름차순 정렬
  • 2. (1번 sort) key에 튜플로 여러 인자를 주어 한 번에 정렬 ★

n = int(input()) # 회의의 개수
time = [[0]*2 for i in range(n)] # 회의 시간 2차원 배열 생성, 초기화

for i in range(n): # 회의 개수만큼 입력받기
    time[i] = list(map(int, input().split()))

# 1순위 : 끝나는 시간(오름차순), 2순위 : 시작하는 시간(오름차순)
time = sorted(time, key = lambda x: (x[1], x[0]))

count = 1 # 현재 회의 수 저장. 최소 1번은 회의 진행
end = time[0][1] # 첫 번째 회의가 끝나는 시간
    
for i in range(1, n):
    if time[i][0] >= end: # 다음 회의를 시작할 수 있으면
        count += 1
        end = time[i][1] # 다음 회의가 끝나는 시간 갱신

print(count)