그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함
• 그리디 해법은 그 정당성 분석이 중요함
  • 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토

문제 1. 거스름돈

거스름돈으로 사용한 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.
손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소의 개수를 구하여라.

 

풀이

# 거스름돈

n = 1260
count = 0

# 큰 단위의 화폐부터
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin  # 거슬러 줄 수 있는 동전 개수 세기
    n %= coin  # 남은 거슬러 줘야할 금액

# [500, 100, 50, 10]을 순서대로 2, 2, 1, 1개 사용함
print(count)

문제 해설

그리디 알고리즘을 이용해 풀어 보자.

가장 큰 화폐 단위부터 돈을 거슬러 주는 것이다.

가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다. 그다음 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.

시간 복잡도 분석

• 화폐의 종류가 K라고 할 때, 소스코드의 시간 복잡도는 O(K)이다.
  • O(4)
• 이 알고리즘의 시간 복잡도는 거슬러줘야 하는 금액과는 무관하며, 동전의 총 종류에만 영향을 받음

 

문제 2. 1이 될 때까지

두 숫자 N과 K가 입력으로 들어오면 N이 1이 될 때까지 아래의 2가지 연산중 한가지를 수행한다.
N을 1로 만드는 연산의 최소 횟수를 구한다.
2가지 연산:
1) N에서 1을 뺀다.
2) N을 K로 나눈다.

입력 조건

• 자연수 N, K

출력 조건

• N을 1로 만드는 연산의 최소 횟수

 

풀이

# 아이디어 : 최대한 많이 나누기
n, k = map(int, input().split())
count = 0
while True:
    # N이 K로 나누어 떨어지는 수가 될 때까지 빼기
    target = (n // k) * k

    # N이 target이 될 때까지의 연산 수 더해줌
    count += n-target
    
    # n 재정의 
    n = target

    # 더이상 나눌 수 없을 때
    if n < k:
        break

    count += 1
    n = n // k

# n < k일 때 남은 수에 1씩 빼기
count += (n-1)
print(count)

 

문제 3. 곱하기 혹은 더하기

 

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때,왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며
숫자 사이에 'X' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하세요.
단, +보다 X를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정함.

예를 들어 02984라는 문자열이 주어지면, 만들어질 수 있는 가장 큰 수는 (((( 0 + 2 ) x 9) x 8) x 4) = 576 입니다.
또한, 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어집니다.

입력 조건

• 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1 <= S의 길이 <= 20)

출력 조건

• 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력합니다.

풀이

# 아이디어: 두 수 중 하나라도 0이면 +, 두수 모두 0이 아니면 *
data = input()

result = int(data[0])
for i in range(1,len(data)):
    # 두 수 중 하나라도 0이면 +, 아니면 *
    num = int(data[i])
    if result == 0 or num == 0:
        result += num
    else:
        result *= num
print(result)

# input : 02984 -> output : 576

 

문제 4. 모험가 길드

공포도가 높을수록 공포를 많이 느끼는 사람이다.
X 공포도를 가진 사람은 X 명 이상의 그룹에 속해야 그룹을 형성할 수 있다.
모험을 떠날 수 있는 최대 그룹수를 구하라 ( 단, 모든 사람이 그룹이 결성이 되지 않아도 된다.)

입력 조건

• N 명 , 전체 인원 수
• 모험가의 공포도 간격을 두고 N 개수 만큼 들어온다.

출력 조건

• 모험을 떠날 수 있는 최대 그룹수를 구하라.

풀이

n = int(input())
data = list(map(int, input().split()))
data.sort()

result = 0 # 그룹 수
count = 0 # 현재의 모험가 수

for i in data:      # 공포도 낮은 것부터 하나씩 확인
    count += 1      # 현재 그룹에 해당 모험가 포함시키기
    if count >= i:  # 현재 그룹에 포함된 모험가 수가 현재 공포도 이상이면, 그룹 결성
        result += 1 # 총 그룹 수 증가
        count = 0   # 현재 그룹에 포함된 모험가 수 초기화
print(count)