[알고리즘] 그리디

2023. 03. 31.

그리디 알고리즘

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

그리디 알고리즘의 수행과정

1. 해 선택: 현재 상태에서 가장 최선이라고 생각하는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는 지 검사한다. 전체 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복한다.

2023. 03. 31. 오늘의 문제풀이 ✍🏼

BOJ 14916 - 거스름돈

그리디 기초문제로, 가치가 큰 동전을 먼저 사용하여 가장 적은 동전을 사용한다. 결국 2원과 5원의 동전만을 사용하기 때문에 5로 나누어 떨어질 때까지 2를 빼면 된다.

import sys
input = sys.stdin.readline

n = int(input())

result = 0

while n > 0:
    if n % 5 == 0:
        result += n // 5
        n -= 5 * n // 5
        break
    else:
        n -= 2
        result += 1

if n == 0:
    print(result)
else:
    print(-1)

---

BOJ 2839 - 설탕 배달

3kg, 5kg의 무게만 존재하기 때문에 위 문제와 마찬가지로 크기가 큰 5kg부터 시작해 5로 나누어 떨어지는지 검사하고 그렇지 않다면 3kg를 빼주어 결과를 확인해 나가면 된다. 만약 while문을 벗어나도 n이 0이 되지 않는다면 3kg와 5kg로 정확하게 n kg그램을 만들 수 없다는 뜻이므로 -1을 반환해주면 된다.

import sys

input = sys.stdin.readline

n = int(input())
result = 0

while n > 0:
    if n % 5 == 0:
        n -= 5
        result += 1
    else:
        n -= 3
        result += 1
    
if n == 0:
    print(result)
else:
    print(-1)

---

BOJ 1931 - 회의실 배정

1개의 회의실에 회의가 겹치지 않게 최대한 많은 회의를 배정하는 문제이다. 현재 회의의 종료 시간이 빠를수록 다음 회의와 겹치지 않게 시작하는 데 유리하므로 종료 시간이 빠른 순서대로 정렬해 문제를 풀었다. 회의의 시작 시간과 종료 시간이 같을 수도 있다고 했기 때문에 예를 들어(2,2) (1,2) 2개의 회의가 있다고 가정했을 때 실제로는 2개의 회의가 겹치지 않게 할 수 있지만, 로직 상 (2,2)가 먼저 나오면 마중 나온 (1,2)가 불가능할 수 있다. 따라서 종료 시간이 같으면 시작 시간이 빠른 순서로 정렬하는 로직도 추가해야 한다.

import sys

data = []

input = sys.stdin.readline

n = int(input())

for _ in range(n):
    start, end = map(int,input().split())
    data.append((start,end))

data.sort(key = lambda x: (x[1], x[0]))
result = 1
end = data[0][1]

for i in range(1,n):
    if data[i][0] >= end:
        result += 1
        end = data[i][1]

print(result)