그리디 알고리즘 & 구현

그리디 알고리즘

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다.

일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

그리디 해법은 그 정당성 분석이 중요하다.

• 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다.

 

일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.

코딩 테스트에서는 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이론 추론할 수 있어야 풀리도록 출제된다.

 

예제: 거스름돈

문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 10원짜리의 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러줘야할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈은 항상 N은 항상 10의 배수이다.

 

문제 해설

동전의 최소 개수를 구해야하는 문제이기 때문에, 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.

 

코드 구현

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin

print(count)

 

시간 복잡도

화폐의 종류가 K라고 할때, 소스코드의 시간 복잡도는 O(K)이다.

이 알고리즘의 시간복잡도는 거슬러줘야하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받는다.

 

 

구현

머리속에 있는 알고리즘을 소스코드로 바꾸는 과정이다.

풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제

 

구현 유형의 예시

• 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
• 실수 연산을 다루고, 특정 소수점자리까지 출력해야하는 문제
• 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제
• 적절한 라이브러리를 찾아서 사용해야하는 문제