프로그래머스69 [코딩테스트 연습]예산 문제: https://programmers.co.kr/learn/courses/30/lessons/43237 이분 탐색 문제입니다. 지방의 갯수를 M개라 한다면, 정해진 예산으로 할당이 가능한지 판단하는데 O(M)이 걸립니다. 그러므로 예산을 정하는 로직을 로그시간에 처리해야합니다. 그래서 이분탐색이 필요합니다. 한 가지 주의해야 할 것은 오버플로우 입니다. 예산의 총액 상한액이 10억이지만, mid = (lower + upper ) / 2 를 구하는 과정에서 lower + upper는 INT 범위를 초과할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG43237.cc 2020. 7. 10. [코딩테스트 연습]다리를 지나는 트럭 문제: https://programmers.co.kr/learn/courses/30/lessons/42583 시뮬레이션 문제이므로 문제의 제약 조건만 잘 구현하면 됩니다. 1. 총 루프횟수: 다리를 통과한 트럭의 갯수 == 총 트럭의 갯수 2. 매 초마다 다리를 빠져나가는 트럭이 있는지, 대기열에 있는 트럭이 다리에 올라갈 수 있는지 체크해줍니다. 중요한 건 트럭이 여러 대 다리에 올라갈 수 있을 때 어떻게 처리하는지가 중요합니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42583.cc 2020. 7. 7. [코딩테스트 연습] 디스크 컨트롤러 문제: 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. 이전 1 ··· 9 10 11 12 13 14 15 ··· 18 다음
