알고리즘/힙 썸네일형 리스트형 [python] baekjoon 1202 보석 도둑 문제 -> 문제 링크 : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 � www.acmicpc.net 문제풀이 가방의 개수와 보석의 개수 모두 30만으로 O(logN) 이하의 시간 복잡도로 문제를 해결해야 한다. 가방에 들어가는 보석을 선택하는 문제이든 보석을 담을 수 있는 가방을 선택하는 문제이든 시간이 O(logN)으로 찾을 수 있어야 문제를 해결할 수 있다. 기준을 가방으로 잡고, 현재 가방에 들어갈 수 있는 보석 중 가장 비싼 보석을 넣는 방식으로 문제를 해.. 더보기 [python] algospot RUNNINGMEDIAN 문제 -> 문제 링크 : https://algospot.com/judge/problem/read/RUNNINGMEDIAN algospot.com :: RUNNINGMEDIAN 변화하는 중간값 문제 정보 문제 한 수열의 중간값(median)은 이 수열을 정렬했을 때 가운데 오는 값입니다. 예를 들어 {3,1,5,4,2}를 정렬했을 때 가운데 오는 값은 3이지요. 수열의 길이가 짝수일 때 algospot.com 문제풀이 수열의 길이가 최대 20만이기 때문에 매번 새로운 숫자가 들어왔을 때 중간값을 구하는 방법으로는 시간 안에 해결할 수 없다. O(nlogn)이나 O(logn)에 해결할 수 있는 방법이 필요하다. 수열에 있는 숫자들은 모두 한 번씩은 사용해야 하기 때문에 n이 나올 수밖에 없다고 생각했고, 숫.. 더보기 이전 1 다음