https://programmers.co.kr/learn/courses/30/lessons/43237
flow
한동안 다른 일로 바빠서 예전에 풀어놨던 문제인데 정리를 못했었다.
기억이 완전하진 않지만 이것도 이분탐색 알고리즘을 이용하면 되는 문제이다.
예산 배정 상한액을 구하는데 min=0, max=max(budgets) 부터 스타트하면 깔끔한 것 같다.
처음에 풀었을 때, 효율성 테스트 1,2번 이었나? 정답이 안 나와서 효율성 문제인 줄 알고 여러 뻘짓을 했었던 기억은 확실히 난다..
def solution(budgets, M):
Min = 0
if sum(budgets) < M:
return max(budgets)
Max = max(budgets)
budgets.sort()
while Max > Min:
if Max == Min + 1:
return Min
mid = (Max + Min) // 2
ma = len(budgets)-1
mi = 0
while ma > mi:
midd = (ma + mi) // 2
if budgets[midd] > mid:
ma = midd
else:
mi = midd
if ma == mi + 1:
break
Sum = mid * (len(budgets)-ma)
for e in budgets[:ma]:
if Sum > M:
break
Sum += e
if Sum > M:
Max = mid
else:
Min = mid
return Min
이런 식으로 mid 값 테스트하는 것도 이분탐색을 한번 더 이용해서 효율성을 많이 끌어 올렸었다..
근데 나중에야 효율성문제가 아니라 답이 틀렸다는 것을 깨닫고.. 조건 하나 바꿔서 올 correct를 띄운 기억이..
result
https://github.com/songjy6565/alg-py/blob/master/programmers/level3/A13.py
https://programmers.co.kr/learn/courses/30/lessons/42898 - flow 처음에 이 문제를 보고 카테고리가 dp라서 바로 생각의 풀이 제한되어 버렸다.. 특정 칸의 최단 경로 갯수는 인접한 전칸들의 최단 경로 갯수 합이 될 것이고, 웅덩이들만 적절히 반영해주면 풀릴 문제라고 생각을 했다. 근데 막상 알고리즘을 짜려...
https://programmers.co.kr/learn/courses/30/lessons/42886 - flow 일단 추를 무게순으로 정렬하고, 특정 추의 무게가 n일 때, 그 추보다 작은 무게를 가진 추들 모두의 합이 n-1 보다 작으면 sum+1 ~ n-1 의 무게는 절대 잴 수 없다. 이 점을 이용하면 무게가 작은 추부터 차례대로 확인해 나아가면서...
https://programmers.co.kr/learn/courses/30/lessons/43237 - flow 한동안 다른 일로 바빠서 예전에 풀어놨던 문제인데 정리를 못했었다. 기억이 완전하진 않지만 이것도 이분탐색 알고리즘을 이용하면 되는 문제이다. 예산 배정 상한액을 구하는데 min=0, max=max(budgets) 부터 스타트하면 깔끔한 것...
https://programmers.co.kr/learn/courses/30/lessons/43238 - flow 처음에 카테고리가 이분탐색인 것을 보고 약간 멘붕이 왔다. binary search 를 오랜만에 보다 보니 이게 이분 탐색으로 푸는 게 적합한 문제인가 감이 안 왔다. 계속 생각해보다가 적합한 time을 이분탐색으로 찾는 거구나 해서 바로 풀...
https://programmers.co.kr/learn/courses/30/lessons/42628 - flow 동시에 최소힙과 최대힙을 운용하면 된다. 예전 글에 python heapq를 이용했던 적이 있다. 이번에도 이용해서 풀면 금방 풀 수 있다.. 시간 복잡도는 힙 두개를 만드는 것이므로 O(NlogN) 이다. Operations 길이가 N이고 ...