짜리몽땅 매거진
[Baekjoon] 그리디 알고리즘(1) 본문
그리디 알고리즘은 현재 시점에서 지금 당장 좋은 것만 고르는 방법으로 '탐욕법'이라고 부르기도 한다. 그리디 알고리즘은 다음과 같은 특징을 지니고 있다.
- 일반적인 상황에서 최적의 해를 보장할 수 없다.
- 코딩테스트에서 대부분의 그리디 문제는 그리디 알고리즘으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제된다.
코딩테스트에서는,
- 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높다.
- 정렬 라이브러리의 사용법이 필요하다.
- 일반적으로는 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력만을 요구한다.
- 정당성 분석이 중요하다. 탐욕법으로 문제를 풀어도 최적의 해를 구할 수 있는가?
그리디 알고리즘으로 분류되는 코딩테스트 문제를 백준 알고리즘 사이트에서 풀어보았다.
문제1. Project Teams
문제 정보 : Silver IV / 정답률 70.176%
https://www.acmicpc.net/problem/20044
20044번: Project Teams
입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로
www.acmicpc.net
# n, data(=2n) 입력받기
n = int(input())
data = list(map(int, input().split()))
# 입력받은 수들 정렬하기
data.sort()
# 두 숫자 씩 묶기
sum = []
for i in range(n*2):
current_sum = data[i] + data[n*2 - i-1]
sum.append(current_sum)
# 최소 합 구하기
min_sum = min(sum)
# 최소 합 출력
print(min_sum)
문제2. 거스름돈
문제 정보 : Bronze II / 정답률 65.356%
https://www.acmicpc.net/problem/5585
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
N = 1000 - int(input())
# 거슬러줘야 할 동전 개수
count = 0
# 동전 종류
money = [500, 100, 50, 10, 5, 1]
# 가장 큰 단위 부터, 나눈 몫을 count에 더하기
for coin in money:
count += N // coin
# 아직 거슬러주지 못한 돈은 나머지로 계산
N %= coin
print(count)