그리디 알고리즘
매 순간 가장 좋아보이는 것을 선택하는 알고리즘
힌트 keyword : 가장 큰 순서대로, 가장 작은 순서대로
예제 1 : 거스름돈
그리디 알고리즘의 대표적인 문제 중 하나
단위가 큰 동전이 항상 단위가 작은 동전의 배수이므로 그리디 알고리즘을 적용할 수 있다.
# 교재 풀이
n = 1260
count = 0
# 큰 단위의 화폐부터 차례대로 확인하기
coin_types = [500, 100, 50, 10]
for coin in coin_types:
count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)실전 문제 1 : 1이 될 때까지
# 내 답안
n, k = map(int,input().split())
count = 0
while True :
if n == 1 :
break
if n % k == 0 :
n /= k
count += 1
else :
n -= 1
count += 1
print(count)
# 교재 풀이
# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())
result = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
target = (n // k) * k
result += (n - target)
n = target
# N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
# K로 나누기
result += 1
n //= k
# 마지막으로 남은 수에 대하여 1씩 빼기
result += (n - 1)
print(result)실전 문제 2 : 곱하기 혹은 더하기
# 내 답안
s = list(map(int,input()))
sum = 0
if (s[0] == 0 or s[1] == 0) or (s[0] == 1 or s[1] == 1) :
sum = s[0] + s[1]
else :
sum = s[0] * s[1]
for i in range(2,len(s)) :
if s[i] == 0 or s[i] == 1 :
sum += s[i]
if sum >= 2000000000 :
sum -= s[i]
break
else :
sum *= s[i]
if sum >= 2000000000 :
sum /= s[i]
break
print(int(sum))# 교재 풀이
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)
실전 문제 3 : 모험가 길드
# 내 답안
n = int(input())
mem = list(map(int,input().split()))
mem.sort()
count = 1
group = 0
for i in range(n) :
if mem[i] == count :
group += 1
count = 1
else :
count += 1
print(group)
# 교재 풀이
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) # 총 그룹의 수 출력실전 문제 4 : 큰 수의 법칙
# 내 답안
n,m,k = map(int,input().split())
data = list(map(int,input().split()))
data.sort(reverse = True)
result = 0
while True :
for _ in range(k) :
if m == 0 :
break
result += data[0]
m -= 1
if m == 0 :
break
result += data[1]
m -= 1
print(result)내가 작성한 코드로는 M의 크기가 100억 이상처럼 커진다면 시간 초과 판정을 받을 것이다.
따라서, 시간 초과를 피하기 위해서는 반복되는 수열을 먼저 파악해야 한다.
# 교재 풀이
# N, M, K를 공백을 기준으로 구분하여 입력 받기
n, m, k = map(int, input().split())
# N개의 수를 공백을 기준으로 구분하여 입력 받기
data = list(map(int, input().split()))
data.sort() # 입력 받은 수들 정렬하기
first = data[n - 1] # 가장 큰 수
second = data[n - 2] # 두 번째로 큰 수
# 가장 큰 수가 더해지는 횟수 계산
count = int(m / (k + 1)) * k
count += m % (k + 1)
result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m - count) * second # 두 번째로 큰 수 더하기
print(result) # 최종 답안 출력실전 문제 5 : 숫자 카드 게임
# 내 답안
n, m = map(int,input().split())
min_value = []
result = 0
for _ in range(n):
data = list(map(int,input().split()))
data.sort()
min_value.append(data[0])
for i in range(n-1):
if min_value[i] < min_value[i+1]:
result = min_value[i+1]
else:
result = min_value[i]
print(result)나의 답안은 min() 함수를 이용하지 않았다. min() 함수를 이용하면 간단히 작성할 수 있다.
# 교재 풀이
# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())
result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
data = list(map(int, input().split()))
# 현재 줄에서 '가장 작은 수' 찾기
min_value = 10001
for a in data:
min_value = min(min_value, a)
# '가장 작은 수'들 중에서 가장 큰 수 찾기
result = max(result, min_value)
print(result) # 최종 답안 출력
