[Algo] 그리디(탐욕) 다시 보면 좋은 문제 모음집!
오른쪽 문제를 클릭하면 해당 문제를 볼 수 있습니다.
1. 백준 - 거스름돈
소요시간: 25분
난이도: 하
def sol(n):
tmepN = n
div5 = n // 5
while True:
if div5 > 0:
tmepN -= div5 * 5
div2 = tmepN // 2
tmepN -= div2 * 2
if tmepN == 0:
return div2 + div5
if div5 == 0 and tmepN != 0:
return -1
if div5 > 0:
div5 -= 1
tmepN = n
print(sol(int(input())))
2. 백준 - 뒤집기
소요시간: 30분
난이도: 하
def sol(s):
cnt = 0
for i in range(1,len(s)):
if s[i-1] != s[i]:
cnt += 1
if cnt % 2 == 0:
return cnt // 2
else:
return (cnt + 1) // 2
s = list(input())
print(sol(s))
3. 백준 - 등수매기기
소요시간: ??분/시간초과가 계속 뜬다....왜지.. -> pype3로 하면 통과
난이도: 하
n = int(input())
arr = [int(input()) for _ in range(n)]
ans = 0
arr.sort()
for i in range(len(arr)):
ans += abs(arr[i] - (i + 1))
print(ans)
4. 백준 - 배
소요시간: ??분/pypy3으로 해야함
난이도: 중
- 단순히 박스의 무게와 크레인의 무게 제한을 오름차순으로 정렬 후 문제를 해결하다가 계속 틀렸다는 것을 깨달았다. 왜 계속 오름차순 정렬에만 집착을 했니 과거의 나 자신. 내림차순도 있다고!!예를들어,
- 내림차순 정렬
크레인 무게 제한: 9 8 6
박스의 무게: 9 9 4 2 2
이 경우 2분 소요.
- 오름차순 정렬
크레인 무게 제한: 6 8 9
박스의 무게: 2 2 4 9 9
이 경우 3분 소요
이처럼 내림차순으로 해야 최적의 해를 가질 수 있다.
ans = 0
n = int(input())
weight_limit = list(map(int,input().split()))
m = int(input())
weight = list(map(int,input().split()))
weight_limit.sort(reverse=True)
weight.sort(reverse=True)
if max(weight) > max(weight_limit):
print(-1)
exit()
while len(weight) > 0:
ans += 1
for w in weight_limit:
if len(weight) == 0: #사실 필요없는 부분. len(weight)가 0이면 for문이 실행되지 않기때문
break
for i in range(len(weight)):
if weight[i] <= w:
del weight[i]
break
print(ans)
#틀린 코드
weight_limit.sort() # 틀린 이유: 내림차순을 고려하지 않음!
weight.sort()
if max(weight) > max(weight_limit): # 틀린 이유: 문제 조건 -1 출력 상황도 놓침 - 뒤늦게 캐치
print(-1)
exit()
while len(weight) > 0:
ans += 1
for w in weight_limit:
if weight[0] <= w: #틀린 이유: 첫번째꺼가 수용이 안되면 다음꺼가 기회를 가질 수 있어야한다
del weight[0]
if len(weight) <= 0:
break
print(ans)
5. 백준 - 센서
소요시간: 한시간
난이도: 하 (권장 소요 시간 30분)
O(nlogn)
n = int(input())
k = int(input())
if k >= n: #놓친부분
print(0)
exit()
arr = list(map(int,input().split()))
arr.sort()
dist = []
for i in range(1,n):
dist.append(arr[i] - arr[i-1])
#dist를 정렬했을때
dist.sort(reverse=True)
print(sum(dist[k-1:]))
#dist를 정렬하려고 생각하지 않았을때 답안
for _ in range(k-1):
dist.remove(max(dist))
print(sum(dist))
6. 백준 도서관
소요시간: 분
난이도: 중(40분)
코드를 입력하세요
- 소요시간: 분
난이도:
코드를 입력하세요
Author And Source
이 문제에 관하여([Algo] 그리디(탐욕) 다시 보면 좋은 문제 모음집!), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ehddms7410/Algo-그리디탐욕-50문제-풀기-도전기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)