그리디 알고리즘
- 현재 상황에서 지금 당장 좋은 것마을 고르는 방법
- 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함
- 문제 푸는 해법은 정당성 분석이다! -> 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토.
(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) # 총 그룹의 수 출력
공부방