[이것이 코딩 테스트다] 2. 그리디

그리디 알고리즘

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

(ex)

• 일반적 상황서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다
  but 코딩테스트 에서 대부분 그리디 알고리즘 문제는 그리디로 푼 해가 최적의 해가 되는 상황이다. 이를 추론하여야 풀릴 수 있도록 출제된다고 함.

<문제> 거스름 돈

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

• 최적의 해를 구하기 위해선 가장 큰 화폐 단위부터 돈을 거슬러 주면 됨

<정당성 분석>

• 가장 큰 화폐 단위부터 돈을 거슬러 주는 이유? -> 가지고 있는 동전 중 큰 단위가 항상 작은 단위의 배수. 따라서 작은 단위의 동전들을 종합해 다른 해가 나올 순 없음

n = 1260
count = 0

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

for coin in array:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin # 화페로 나눈 나머지 n에 대입

print(count)

• 화폐 종류가 K라고 할 때, 시간복잡도는 O(K)
• 시간복잡도는 금액과 무관하며, 동전의 총 종류에만 영향.

<문제> 1이 될 때까지

# 내 풀이 -> 시간 오래걸림..
import sys
n,k=map(int,sys.stdin.readline().split())
cnt=0

while n>1:
    if n%k!=0:
        n-=1
        cnt+=1
        
    else:
        n=n//k
        cnt+=1

print(cnt)

import sys
n,k=map(int,sys.stdin.readline().split())
result=0
while True:   
    target=(n//k)*k # n이 k로 나누어 떨어지지 않을 때, k의 배수에서 n보다 작은 수를 target에 넣음 
    result+=(n-target) # 1빼주는 연산 수행 횟수를 result에 더함.
    n=target

    if n<k:
        break

    result+=1 # 
    n=n//k 

result+=(n-1)
    
print(result)

• 최대한 많이 나누는 작업을 수행하면 됨.

<문제> 곱하기 혹은 더하기

• 각 자리가 숫자(0부터 9)로만 이루어진 문자열 S가 주어졌을 때 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '×' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하라
• 단, +보다 ×를 먼저 계산하는 일반적인 방식과는 달리 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다
• 예를 들어 02984라는 문자열로 만들 수 있는 가장 큰 수는 ((((0 + 2) × 9) × 8) × 4) = 576 이다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다

내 답

• 그리디로 풀지 않았고, 문자열을 테이블로 나타낸 후, 경우를 나눠서 풀었다.

import sys
s=sys.stdin.readline()
num_list=[]
result=1


for num in s[:-1]: # 문자열을 배열로 분배.
    num_list.append(int(num))

num_list.sort() # 

if num_list[0]==0 or num_list[0]==1: # 첫 배열의 항목이 0, 1인 경우 예외 처리 
    result=num_list[0]+num_list[1]
    num_list=num_list[2:]

for num in num_list:
    result*=num
print(result)

코딩테스트 답

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명의 모험가에 대한 정보가 주어졌을때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하라
• 예를 들어 N = 5이고, 각 모험가의 공포도가 다음과 같다고 가정한다
  ' 2 3 1 2 2 '
• 이 경우 그룹 1에 공포도가 1, 2, 3인 모험가를 한 명씩 넣고, 그룹 2에 공포도가 2인 남은 두명을 넣게 되면 총 2개의 그룹을 만들 수 있다
• 또한 몇 명의 모험가는 마을에 그대로 남아 있어도 되기 때문에, 모든 모험가를 특정한 그룹에 넣을 필요는 없다

내 풀이
import sys

cnt=0
n=int(sys.stdin.readline())
data=list(map(int,sys.stdin.readline().split()))
data.sort()



while len(data)!=0:
    max_fear=data.pop()
    if max_fear==1:
        cnt+=data.count(1)+1
        break
    else:
        data=data[0:-max_fear+1]
        cnt+=1
    print(data)


print(cnt)

출제자 풀이
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) # 총 그룹의 수 출력