그리디 알고리즘은 간단하며 많이 사용되는 알고리즘이다. 채용을 위한 코딩테스트같은 곳에서도 출제확률이 굉장히 높다고 한다. 난이도는 정말 문제마다 천차만별이다.
각 상황마다 적합한 알고리즘을 이용하여 푸는 것이 효율적인 것은 당연하다. 그래서 개인적으로 문제를 보고 어떤 알고리즘을 사용하여 풀이할 것인지 아이디어를 떠올리는 것을 중요하게 생각하는데, 문제를 보고 알고리즘을 선택하는 안목을 늘리기 위해서는 같은 알고리즘 분류의 문제들을 단기간에 최대한 많이 풀어보는게 좋을 듯 하여 백준에서 알고리즘 분류탭을 이용해 문제들을 풀어보는 중이다.
백준 그리디 알고리즘 문제들
저번에 동적계획법(DP) 프로그래밍에 대해 글을 쓴 적이 있었다.
이번에는 그리디(Greedy)이다.
내가 느끼기로는 dp알고리즘은 문제 전체를 해석하고 하위문제로 나누어 푼뒤 시간 복잡도를 위해 계산을 여러번 하지않도록 자료형에 저장하고 푸는 식,
그리디 알고리즘은 가장 눈앞에 있는 문제들부터 하나하나 빠르게 풀어간다. dp보다는 문제해결이 빠를 수 있지만 정확한 결과값을 얻지 못할 수도 있다. 이렇게 알고리즘이 100% 최적의 해를 보장하지 못하면 근사 알고리즘이라고 한다.
그리디 알고리즘을 사용하여 풀이하기 좋은 문제들의 조건은 다음과 같다.
- 탐욕 선택 속성(greedy choice property)
탐욕 선택 속성이란 문제를 풀이하며 선택하는 과정이 다음 선택 과정에서 영향을 끼치면 안된다는 조건이다.
- 최적 부분 구조(optimal substructure)
최적 부분 구조는 과정마다 순간의 최적해가 문제 전체의 최적해와 같은 구조를 말한다.
글로만 읽어서 이해하기 어려우니 대표적인 예제를 보자.
백준 5585번 거스름돈 문제
문제
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
예를 들어 입력된 예1의 경우에는 아래 그림에서 처럼 4개를 출력해야 한다.
입력
입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다.
출력
제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오.
문제는 간단하다.
소스코드
import sys
input = sys.stdin.readline
a = int(input())
b = 1000 - a
li = [500, 100, 50, 10, 5, 1]
li_ = []
while b != 0:
for i in li:
r = 0
r += b // i
li_.append(r)
b -= r * i
print(sum(li_))정말 간단한 문제인데 문제를 제대로 읽지도 않고 그림을 보면서 풀었더니 50엔을 리스트에 넣지않고 풀어서 틀렸다..
문제는 천천히 꼼꼼히 읽고 풀자.