고양이와 코딩하기

문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 핵심 로직 허용량이 가장 작은 가방부터 차례대로 보석 무게들을 비교하여, 담을 수 있는 보석후보를 보석 가격을 우선순위로 최대힙에 넣고, 각 가방에 담을 수 있는 가장 높은 보석 가격들의 합을 구한다. 사전작업: 보석(무게, 가격)리스트, 가방(허용량)리스트 오름차순 정렬 힌트: 오름차순으로 정렬되어 있는 리스트의 경우, 바로 he..

문제 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 핵심 로직 1. 최대힙, 최소힙 동시 사용 insert: 값을 넣을 때 최대힙, 최소힙에 해당값을 각각 넣어준다. delete: 최대힙 혹은 최소힙에서 값을 제거할 때, 해당 값이 제거되었음을 기록해준다. → 다른 쪽 힙에서 값을 제거해줄 때 이미 제거된 값인지 확인하여, 이미 제거된 값인 경우 제거되지 않는 값이 나올 때까지 헤더 값을 계속해서 제거해 나간다. Hint: 최대힙과 최소힙..

문제 https://www.acmicpc.net/problem/18870 핵심 로직 1. 이분 탐색, 집합 중복제거 후 이분 탐색 사전 작업: index값을 리턴하는 이분 탐색 함수 구현 - binary_search() 1. set()을 이용하여 리스트 X 안의 중복값 제거한 집합 생성 2. 집합을 다시 리스트로 만들고 오름차순으로 정렬하여 리스트 sorted_X를 생성 3. for문으로 리스트 X의 값들을 순회하여 binary_search()로 sorted_X에서의 index값을 구함 4. index값은 0부터 시작이므로, 이는 곧 자기보다 작은 수의 갯수와 값이 같음 정답 코드 - [시간복잡도: O(N*logN)] 더보기 import sys def binary_search(array, value): ..