[이코테] 그리디 알고리즘

매 순간마다 가장 최적의 답을 선택하여 최종의 답을 도출하는 방법

 

• 매 순간의 최적해가 문제에 대한 최적해이다.
• 한번의 선택이 다음 선택에는 무관하다.

문제를 해결하기 위한 아이디어를 직관적으로 찾고 그 아이디어의 정당성을 검토할 수 있어야 한다.

1. 거스름 돈

문제

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재

손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하기

(단, 거슬러 줘야 할 돈 N은 항상 10의 배수)

 

해결 방안

가장 큰 단위부터 돈을 거슬러 준다.

 

why? 

• 큰 단위가 항상 작은 단위의 배수이다! 
  • 500원을 각각 100원 5개, 50원 10개, 10원 50개
• 400원 동전이 있다면 800원을 거슬러 주는데 문제가 생김

문제 풀이

n = 1260	# 거스름돈
count = 0	# 동전의 개수

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

for coin in array:
    count += n // coin	# 몫
    n %= coin # 나머지
    
print(n)

 

2. 1이 될 때까지

문제

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행

(단, 두번째 연산은 N이 K로 나누어 떨어질 때만 가능)

1. N에서 1을 뺀다
2. N을 K로 나눈다

가장 최소의 수행 횟수를 구하기

 

해결 방안

최대한 많이 나누기를 수행한다.

 

why?

• 1을 빼기보다 2이상의 수로 나누는 것이 1에 떠 빠르게 가까워 질 수 있다.

문제 풀이

n = 25 # 1로 만들려는 수
k = 5  # 나누는 수
result = 0 # 수행 횟수

while True:
    target = (n // k) * k	# 몫을 구해서 k의 배수 만들기
    result += (n - target)	# target과 n의 차이가 1을 빼야하는 수행 횟수와 같음
    n = target

    # N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    
    # k로 나누기
    result += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1) # 남은 n에서 1이 될 때 까지의 수행횟수 (n - 1)

print(result) # 2

 

3. 곱하기 혹은 더하기

문제

각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며
숫자 사이에 *(곱하기) 혹은 +(더하기) 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하기

(단, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정)

 

해결 방안

최대한 곱하기를 많이 한다. 예외로 0과 1은 더해준다.

 

why?

• 0부터 9자리의 숫자에서 0과 1을 제외하면 항상 곱하기를 해주는 것이 가장 큰 수가 된다.

문제 풀이

data = "02984"

# 첫 번째 문자를 숫자로 변경하여 대입
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) # 576

 

4. 모험가 길드

문제

모험가 길드장인 동빈이는 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로
구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.

 

N명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하라

 

• 2 3 1 2 2

해결 방안

공포도를 오름차순으로 정렬해서 순서대로 그룹을 묶는다.

 

why?

• 공포도가 오름차순으로 정렬되어 있다면 그룹을 편성할 때 이미 그룹에 포함되어 있는 인원은 생각하지 않아도 된다.
• 최소한의 모험가의 수만으로 그룹이 편성된다.
• 최소한의 인원으로 그룹을 만들어야 그룹의 수도 최대가 된다.

data = [2, 3, 1, 2, 2]
data.sort()	# 오름차순 정렬

result = 0	# 총 그룹의 수
count = 0	# 현재 그룹에 포함된 모험가의 수

for i in data:
    count += 1		# 현재 그룹에 해당 모험가를 포함시키기
    
    if count >= i:	# 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
        result += 1	# 총 그룹의 수 증가
        count = 0	# 현재 그룹에 포함된 모험가의 수 초기화

print(result) # 2