Algorithm283 [코딩테스트 연습] 이중우선순위큐 문제: https://programmers.co.kr/learn/courses/30/lessons/42628 쿼리의 개수가 100만입니다. 하나의 쿼리를 로그 시간에 처리해야함을 알 수 있습니다. N개의 숫자에 대한 최소/최대를 O(logN)에 구하려면 힙을 사용해야 합니다. 다만, O(logN)만에 최소/최대를 모두 다 구해야하니 최소힙, 최대힙 이렇게 두 개를 선언해줍니다. 여기에 모두 숫자를 넣게되면 한 번 넣을 때 마다 두 번씩 넣는 꼴이 되니, 최소힙, 최대힙에 숫자를 넣는 것과는 별개로 정수 두 개 front, rear를 사용해서 실제로 입력받은 수를 세줍니다. 0. 초기화는 front = rear = 0 1. 숫자가 들어오면 rear++ 2. 숫자를 제거하면 front++ 3. 힙이 비었는지.. 2020. 6. 18. [코딩테스트 연습] 단속카메라 문제: https://programmers.co.kr/learn/courses/30/lessons/42884 ST: 고속도로에 진입한 시점 EN: 고속도로에서 나간시점 차량이 고속도로에서 나간시점을 오름차순으로 우선순위 큐에 넣어줍니다. 그 후 우선순위 큐를 순회하면서 1. 이전 단속카메라가 커버하는 범위(EN)가 현재 탐색하는 자동차의 도로 진입시점(ST)보다 빠르다면, 현재 자동차를 찍어줄 단속카메라를 추가해줍니다 (camera++) 2. 이전 카메라가 커버하는 범위(EN)가 현재 탐색하는 자동차의 도로 진입시점(ST)을 포함한다면, 이전 단속 카메라로 현재 자동차도 찍을 수 있으니, 다음 자동차를 탐색하러 가면 됩니다 (continue) 코드: https://github.com/cottory/alg.. 2020. 6. 18. [BOJ]12837번: 가계부 (Hard) 문제: https://www.acmicpc.net/problem/12837 쿼리랑 N 제한이 큽니다. O(NQ)에 처리하면 터집니다. 구간합, 갱신 쿼리를 O(logN)에 처리하기 위해 세그먼트 트리로 해결합니다. 코드: https://github.com/cottory/algorithm/blob/master/BOJ/BOJ12837.cc 2020. 6. 17. [코딩테스트 연습] 최고의 집합 문제: https://programmers.co.kr/learn/courses/30/lessons/12938 어떻게 풀지 오래 고민했던 문제입니다. 총합이 1억인 10,000개인 숫자를 모두 곱한 값을 구하는 시도 자체가 파이썬이 아닌 이상 불가능하다고 생각했습니다. 합을 직접 안구해도 알 수 있는 방법이 있나 생각해봤을 때, 곱하는 수의 차가 최소일 때 곱한 값은 최대가 됩니다. (아마 수학적으로 증명이 가능할텐데 그거까진 모르겠네요) 그래서 제곱, 세제곱, N제곱 형태가 되면 가장 베스트 케이스입니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43163.cc 2020. 6. 17. 이전 1 ··· 50 51 52 53 54 55 56 ··· 71 다음
