Algorithm/Programmers93 [코딩테스트 연습] 디스크 컨트롤러 문제: https://programmers.co.kr/learn/courses/30/lessons/42627 문제 조건 중 아래의 조건 때문에 그리디로 해결할 수 없는 문제입니다. 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. 디스크 컨트롤러가 처리해야 할 상황은 두 가지로 나눌 수 있습니다. 1. 현재 디스크 컨트롤러가 위치하는 시간 = 가장 우선처리 해야 할 작업의 시작시간 1번 케이스의 경우 작업을 수행하고 있지 않은 경우이니 그냥 가장 시작시점이 빠른 작업을 수행합니다. 2번의 경우 흔히 말하는 SJF(Shortest Job First)로 해결하면 됩니다. 즉, 현재 디.. 2020. 6. 30. [코딩테스트 연습] 이중우선순위큐 문제: 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. [코딩테스트 연습] 최고의 집합 문제: 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 ··· 12 13 14 15 16 17 18 ··· 24 다음
