greedy algorithm 이란, 최적해를 구하는 방법이다.
최적해를 구하는 문제는 주로 최대값이나 최소값 같은 최적의 값을 구하는 것으로, 풀이 방법은 여러개가 있을 수 있당
즉, 여러 경우 중 하나를 선택하는데, 이때 선택시마다 최적이라고 생각되는 것을 선택하여 최종적인 해답에 도달하는 것이당.
한번 선택하는 것은 번복하지 않으며, 한 선택에서의 최적은 local한 최적이고
local 한 최적만을 수집한다고 해서 최종 해답이 꼭 최적인 건 아니당.
1) 현재 상태에서 부분 문제의 최적해를 구해 solution set에 추가
- 이때 새로운 부분 문제가 발생
2) 1)에서 생긴 새로운 부분해 집합의 실행가능 여부, 문제의 제약조건 위반 여부를 검사한다
3) 새로운 부분해 집합이 문제의 해가 되는지 확인하고, 아니라면 1부터 다시 시작한다
대표적인 예로 배낭문제, 거스름돈 문제, 회의실 배정문제 가 있다
11047: 동전 문제는 자꾸 시간 초과가 뜨는거야,,,
n,k = map(int, input().split())
a = []
for i in range(n):
a.append(int(input()))
count = 0
l = len(a)-1
while(k!=0):
for i in range(l, -1, -1):
if k-a[i]>=0:
k-=a[i]
count+=1
l = i
break
print(count)
찾아보니까 다들 뺄셈 말고 몫으로 구하시더라궁,,,
2875: 대회 or 인턴도 풀었당
n, m, k = 6,3,2
total = n+m
count = 0
while (count!=k and (n+m+count == total)):
able = abs(n//2 - (n//2-m//1))
if (n-1)//2 <= (m-1)//1:
m-=1
else:
n-=1
#print(n, m)
count +=1
print(able)
이렇게 풀어놓고 왜 틀린거지 한참을 고민했당
그러다 다른 분들 블로그를 봤는뎅 내가 문제를 잘못 이해하고 있도라구,,
woman, man, k = map(int, input().split())
team = 0
while woman >=2 and man >=1 and woman+man >= k+3 :
woman -= 2
man -= 1
team += 1
print(team)
#출처: https://yongku.tistory.com/entry/백준-알고리즘-백준-2875번-대회-or-인턴-파이썬Python [츄르 사려고 코딩하는 집사]
사실 그리디가 너무 어려워서,
생각해보다가 모르겠으면 구글링해보고, 그 코드를 이해하는 방식으로 공부했당
10610: 30을 존경하는 마르코 ,,,
처음에 문제를 잘못 이해해서 이렇게 풀었다가
a = int(input())
if a%30 == 0:
print(a)
else:
if a%3 == 0:
if a%5 == 0: print(a*2)
elif a%2 ==0: print(a*5)
else: print(a*10)
elif a%5 == 0:
if a%2 == 0: print(a*3)
else: print(a*6)
elif a%2 ==0: print(a*15)
else: print(a*30)
이렇게 바꿨다! 아니 왜 자꾸 문제 이해를 못하지 엉엉
from itertools import permutations
a = int(input())
if a%30 ==0:
print(a)
else:
nums = [int(i) for i in str(a)]
nums = list(permutations(nums))
nums.sort()
is_30 = False
for n in nums:
n = list(n)
temp = 0
for i in range(len(n)):
temp+= n[i]*(10**i)
if temp%30 == 0: is_30 = True
if is_30:
print(temp)
break
if not is_30: print(-1)
그치만 이것도 시간초과가 떠서 다른 코드를 참고했다 하하,,
1783: 병든 나이트 역시 greedy는 넘모 어렵다 엉엉
처음에는 dx, dy를 쓰는 bfs를 도전해보려 했지만,,, 결국 또 구글링 ㅠㅠ
그림을 그려가며 이해해보았당
# 여행에서 방문할 수 있는 칸의 개수중 최댓값을 출력
n,m = map(int, input().split())
if n==1: #아무 방법도 쓸 수 x
print(1)
elif n==2: #
print(min(4,(m+1)//2)) # 4번 이상 이동 시 모든 이동 방법이 한 번 이상씩 사용되어야 한다
else:
if m<=6: # 모든 칸을 다 갈 수 있당
print(min(4, m))
else:
print(m-2)
# 출처: https://pacific-ocean.tistory.com/354
1931: 회의실 사용은 처음에 문제를 잘못 이해했어서 틀렸었당
n= int(input())
lst = []
for i in range(n):
a,b = map(int, input().split())
lst.append([a, b]) # [시작, 종료]
lst.sort()
max_count = 0
for i in range(5):
timeline = 0
count = 0
for j in range(i, len(lst)):
if lst[j][0]>=timeline:
count +=1
timeline = lst[j][1]
if count > max_count:
max_count = count
print(max_count)
그래서 구글링해보니까, 접근을 다시 해야한다는 걸 알게되어따,,
그리디는 왜이렇게 접근 방식 파악이 힘든걸깡 !_!
정렬을 1. 끝나는 시간의 오름차순 , 2. 시작하는 시간의 오름차순 으로 해줬당
n = int(input())
lst = []
for i in range(n):
a,b = map(int, input().split())
lst.append([a, b]) # [시작, 종료, 시간]
lst.sort(key = lambda x: (x[1], x[0]))
max_count = 0
for i in range(4):
timeline = 0
count = 0
for j in range(i, len(lst)):
if lst[j][0]>=timeline:
count +=1
timeline = lst[j][1]
if count > max_count:
max_count = count
print(max_count)
[11399]
[2873]
[1744]