[알고리즘] 그리디

* 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다.

---

출처

동빈나 이코테

 

 

■ 그리디 알고리즘(greedy algorithm)

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미

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

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

 

---

 

[문제] 거스름 돈

카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정.
손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하라.
(단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.)

 

■ 문제 해결 아이디어

최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 거슬러 준다.

 

 

■ 정당성 분석

가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문.

만약 800원을 거슬러 주어야 하는데 화폐 단위가 500원, 400원 100이라면??
모든 해가 배수여야 가능하다 500 x 1, 100 x 3가 아닌 400 x 2가 제일 적게 적용된다. 400원의 배수가 500원이 아니기 때문이다.

 

 

■ 답안 예시(Python)

n = 1260
count = 0

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

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

 

 

■ 시간 복잡도 분석

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

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

 

---

 

[문제] 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택한다.
1. N에서 1을 뺀다.
2. N을 K로 나눈다.
(N과 K가 주어질 때 N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성)

 

 

■ 문제 해결 아이디어

주어진 N에 대하여 최대한 많이 나누기를 수행한다.

N의 값을 줄일 때 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있다.

 

 

■ 정당성 분석

N이 아무리 큰 수여도, K로 계속 나눈다면 기하급수적으로 빠르게 줄일 수 있다.

K가 2 이상이기만 하면, K로 나누는 것이 1을 빼는 것보다 항상 빠르게 N을 줄일 수 있다.
또한 N은 항상 1에 도달하게 된다.(최적의 해 성립)

 

 

■ 답안 예시(Python)

# N, K을 공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())

result = 0

while True:
	# N이 K로 나누어 떨어지는 수가 될 때 까지 빼기
    target = (n // k) * k
    result += (n - target)
    n = target
    # N이 K보다 작을 때(더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
    	break
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n-1)
print(result)

 

---

 

[문제] 곱하기 혹은 더하기

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

 

 

■ 문제 해결 아이디어

대부분의 경우 '+'보다는 'x'가 더 값을 크게 만든다.

두 수에 대하여 연산을 수행할 때, 두 수 중에서 하나라도 1이하인 경우에는 더하며, 두 수가 모두 2 이상인 경우에는 곱하면 정답이다.

 

 

■ 답안 예시(Python)

data = input()

# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
	# 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
    num = int(data[i])
    if num <= 1 or result <= 1:
    	result += num
    else:
    	result += num
        
print(result)

 

---

 

[문제] 모험가 길드

한 마을에 모험가가 N명있다. 모험가 길드에서 N명의 모험가 '공포도'를 측정했는데, '공포도'가 높은 모험가는 위험상황을 대처할 능력이 떨어진다.
모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 그룹에 참여해야 여행을 떠날 수 있다.
(N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹의 수의 최댓값을 구하라)

 

 

■ 문제 해결 아이디어

오름차순 정렬 이후에 공포도가 가장 낮은 모험가부터 하나씩 확인.

현재 그룹에 포함된 모험가의 수가 현재 확인하고 있는 공포도보다 크거나 같다면 이를 그룹으로 설정한다.

 

 

■ 답안 예시(Python)

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(result) # 총 그룹의 수 출력