그리디
작성 수정
『이것이 코딩 테스트다』 3장 그리디 문제다. 그리디는 현재 상황에서 지금 당장 좋은 것만 고르는 방법이고, 지금의 선택이 나중에 미칠 영향은 따지지 않는다. 2021년 11월에 처음 풀고 2023년 2월에 문제 요약을 주석으로 적으면서 다시 풀었다. 다시 푼 것을 앞에, 처음 풀이를 뒤에 둔다. 거스름돈 풀이의 주석에 그리디가 성립하는 이유를 적어 두었는데, 큰 단위가 항상 작은 단위의 배수여야 한다는 점이다.
거스름돈
# 문제
# N: 거슬러줘야할 돈
# answer: 거슬러줘야할 동전의 최소 개수
n = 1260
coin_type = [500, 100, 50, 10]
answer = 0
for coin in coin_type:
count = n//coin
answer += count
n = n % coin
print(answer)
# 시간 복잡도 O(K)
# K는 동전의 종류
# 문제가 풀리는 이유
# 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로
# 작은 단위의 동전들을 종합해 다른 해가 나올 수 없다.
# 예를 들어 800원을 거슬러 줘야 할 때 500원 1개와 100원 3개를 사용해야 한다고 하지만
# 화폐 단위가 500원, 400원, 100원일경우 400원 2개를 사용하는 것이 더 적은 수의 동전을 사용하는 것이다.
# 화폐 단위가 배수 형태가 아니라면 그리디 알고리즘으로 해결할 수 없다.큰 수의 법칙
# 문제
# 큰 수 만들기
# N: 배열의 크기
# M: 더할 횟수
# K: 연속해서 더할 수 있는 횟수
# 입력 예시
# 5 8 3
# 2 4 5 4 6 배열에 들어있는 수
# 출력 예시
# 46
# 일반적인 풀이
# 가장 큰 수를 연속으로 더하고 두번째로 큰 수를 한번 더하는 방식
n, m, k = map(int,input().split())
data = list(map(int,input().split()))
data.sort()
max1 = data[n-1]
max2 = data[n-2]
answer = 0
while m>0:
for i in range(k):
if m!=0:
answer += max1
m-=1
else:
break
if m!=0:
answer+=max2 #실수: 이 연산에서 m이 0일 수도 있음, if문 추가
m-=1
else:
break
print(answer)
#수열 풀이
# M의 크기가 100억 이상이면 시간 초과가 발생할 수 있음
# 반복되는 수열을 파악하여, 수열의 길이로 나눈 나머지만큼만 계산하면 됨
n,m,k = map(int,input().split())
data = list(map(int,input().split()))
data.sort()
max1 = data[n-1]
max2 = data[n-2]
max1_count = int(m / (k+1)) * k
max1_count += m % (k+1)
max2_count = m - max1_count
answer = 0
answer += max1_count * max1
answer += max2_count * max2
print(answer)숫자 카드 게임
# 문제
# N x M 크기의 배열
# N은 행의 개수, M은 열의 개수
# 각 칸에는 숫자가 하나씩 들어있음
# 1 <= N,M <= 100
# 1 <= 각 칸에 들어있는 숫자 <= 10000
# 규칙: 한 행을 선택하고 그 행에서 가장 작은 수를 선택
# 원하는 답: 가장 큰 수
# min함수를 이용한 풀이
n,m = map(int,input().split())
data = [list(map(int,input().split())) for _ in range(n)]
min_list=[]
for row in data:
min_list.append(min(row))
result = max(min_list)
print(result)
# 책 풀이 + 연산 횟수 줄음
n,m = map(int,input().split())
answer= 0
for _ in range(n):
data=list(map(int,input().split())) # 한 행씩 입력받아 리스트로 저장
answer = max(min(data), answer)
print(answer)1이 될 때까지
# 문제
# 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행
# 1. N에서 1을 뺀다
# 2. N을 K로 나눈다
# N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하라
# 2 <= N, K <= 100000
# 내 풀이
n,k = map(int,input().split())
count = 0
while n!=1:
if n%k==0:
n//=k
else:
n-=1
count +=1
print(count)
# n이 100억 이상일 때
# N이 K의 배수가 되도록 한 번에 빼기
n,k = map(int,input().split())
result = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때까지 1씩 빼기
# 처음 나누는 수가 아닌 나누어 떨어지는 수가 될 때까지 1씩 빼기
target = (n//k) * k # 타겟을 한 번에 빼서 1씩 빼는 횟수를 줄임
result += n - target
if n < k :
break
# K로 나누기
result += 1
n//=k
# 마지막으로 남은 수에 대하여 1씩 빼기
result += n-1
print(result)
# 다른 버전
n,k = map(int,input().split())
result = 0
while n>=k:
result += n%k
n //= k
result+=1
print(result+n-1)모험가 길드
2023년 다시 풀기. 세 번 시도한 흔적이 그대로 있다
# 1차 시도
# x인 모험가는 반드시 x명 이상으로 구성한 모험가 그룹에 참여해야 한다.
n=int(input())
data = list(map(int,input().split()))
# 우선 X가 높은 순서대로 그룹 형성
data.sort(reverse=True)
answer = 0
# 제약사항: 공포도가 X인데 X명 이상 남았는지 확인하기
while data[0] <= len(data):
answer +=1
data=data[data[0]:]
print(answer)
# 공포도 9111 배치에서 최대 그룹수는 1/1/1 총 3개인데, 9먼저 할당시키면 0개임
# 그리디는 fair play에 관심 없음. 조건에 만족시키기만 하면 된다
# 내림차순말고, 오름차순으로 하고 적은애들 부터 보내는 게 능사이다.
#2차 시도
n=int(input())
data = list(map(int,input().split()))
data.sort()
answer=0
while data[0] <=len(data):
data=data[data[0]:]
answer +=1
print(answer)
# answer =3이 나옴. 마지막 slicling에서 2,3에서 2 때문에 3도 포함됨
# 3차 시도
n=int(input())
data = list(map(int,input().split()))
data.sort()
count=0
answer=0
for i in data:
count +=1
if i <= count :
answer +=1
count = 0
print(answer)
# 1,2차 시도는 직관적인 인간의 방식
# 3차시도는 작은 단위로 쪼갠 컴퓨터 방식
# 컴퓨터 방식을 익히려면 분해해서 생각...많이 풀어보자2021년 처음 풀이
n = int(input())
group = sorted(list(map(int,input().split())))
answer = 0
num = 0
for fear in group:
num += 1
if num == fear:
answer+=1
num = 0
print(answer)2021년 복습
# 1. 공포도가 X인 모험가는 반드시 X명 이상으로 그룹을 구성
# 2. 그룹수가 최대가 되게
# 3. 모든 모험가가 참여하지 않아도 된다. = 공포도가 높은 참여자를 빼도 된다.
# 출력 값: 그룹 수
n = int(input())
li = list(map(int,input().split()))
li.sort()
answer = 0
count = 0
for item in li:
count +=1
if count >= item:
answer +=1
count = 0
print(answer)곱하기 혹은 더하기
2023년 다시 풀기
#1차 시도
# + * 만 이용, 좌측부터 계산, 가장 최대 값
s=list(map(int,input()))
# 1은 가장 작은 수에 더하는 게 남
# 0은 무시
sum=0
s.sort()
for i in s:
if sum ==0 or i<2:
sum+=i
else:
sum*=i
print(sum)
# 2차시도(보완)
# sum의 대입을 첫번째 값으로 넣어서 보완하기
s=list(map(int,input()))
sum=s[0]
for i in s[1:]:
if sum <2 or i<2:
sum+=i
else:
sum*=i
print(sum)2021년 처음 풀이
s=sorted(list(map(int,input())))
answer =0
for num in s:
if num == 0 or num ==1 or answer ==0:
answer+=num
else:
answer*=num
print(answer)
a = list('123') # OK
a = list(map(int,'123')) # OK
print(a)2021년 복습
# 0은 곱하면 안되고, 1은 더해야 하고 = 0과1은 더하기
s=list(map(int,input()))
s.sort()
result = s[0]
for item in s[1:]:
if item == 0 or item == 1 or result ==0 :
result += item
else:
result *= item
print(result)문자열 뒤집기
2023년 다시 풀기
#1차시도
#그리디니깐, 적은 놈들을 많은 놈들 쪽으로 바꿔!
# 적은 그룹 ,많은 그룹 카운트
s=list(map(int,input()))
temp=s[0]
count0=0
count1=0
if temp ==0:
count0=1
else:
count1=1
for i in s[1:]:
if temp != i:
temp = i
if i == 0:
count0+=1
elif i ==1:
count1+=1
print(count0 if count0<=count1 else count1 )
# 답하고 비교해봐야 하는데, 포기하지 않고 그리디 문제 해결방법을 떠올렸더니 풀린 문제였다.
# 포기하지 말고, 고민(문제의 목적, 해결방법 알고리즘이 나와있으니까)을 한 번더 해보자2021년 처음 풀이
s = list(map(int,input()))
chunk0 = 0
chunk1 = 0
prev=s[0]
for now in s[1:]:
if prev == 0:
if prev == now:
pass
else:
chunk0 +=1
prev = now
else:
if prev ==now:
pass
else:
chunk1 +=1
prev = now
print(min(chunk0,chunk1))2021년 복습
# 연속된 숫자 뒤집기
# 출력: 최소의 뒤집는 횟수
# 뒤집기를 구현하는 것이 아니라, 답이 되게 하는 연산을 구하면 되겠군
# 연속된 숫자 뭉치를 구하고, 최소의 뭉치 개수를 출력하면 그게 답이 되겠군
# 첫번째 문자열도 카운트 하는 것 실수
s = list(map(int,input()))
prev=s[0]
count0 = 0
count1 = 0
if prev == 0 :
count0=1
else:
count1=1
for item in s[1:]:
if prev != item:
if item == 0:
count0 +=1
prev = 0
else:
count1 +=1
prev = 1
print(min(count0,count1))만들 수 없는 금액
n = int(input())
li = sorted(list(map(int,input().split())))
# 가능한 경우의 수 입력 ㄴㄴ
# 그리디: x는 1부터 target-1까지 모든 금액을 만들 수 있는 상태라고 가정
# 그리디 문제특: 증명하긴 어렵지만 말이됌 ㅇㅇ
# target을 만들 수 있으려면 니가 가진 동전의 단위가 target과 같거나 작아야한다.
# 만들 수 없는 금액의 조건: 1) 가장 작은동전보다 적은 금액 2) 모든 동전을 더한 것 보다 큰 금액
target = 1
for x in li:
if target<x:
break
target+=x