programmers8 [코딩테스트 연습] 이중우선순위큐 문제: 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/42898# DP 문제입니다. dp[i][j] = dp[i-1][j] + dp[i][j-1] 의 관계가 성립함을 알 수 있습니다. 단, 전처리에서 중요한 것이 있는데요. 맨 처음 경로 계산을 위해 가장 자리 값들을 1로 셋팅 할 때 아래와 같이 할 수 있습니다. 집 1 1 1 1 1 1 학교 그런데, 특정 지점에서 웅덩이가 등장했다면, 그 뒷 지점은 전부 방문할 수 없으므로 0으로 놔둬야 합니다. 집 웅덩이 0 0 1 1 1 집 이 부분만 신경써주면 무난히 DP로 해결할 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG42.. 2020. 6. 17. [코딩테스트 연습] 멀리 뛰기 문제: https://programmers.co.kr/learn/courses/30/lessons/12914 DP 문제입니다. 푸는 방식은 다양하겠지만 값을 저장함으로써 중복되는 연산은 O(1)에 리턴하는 로직이 중요합니다. 효진이는 한 번에 1칸 또는 2칸을 뛸 수 있으므로, N번째 칸까지 점프하는 방법을 구한다면 1. N-1번째 칸에서 + 1 점프하는 방법 2. N-2번째 칸에서 + 2 점프하는 방법 JUMP[N] = JUMP[N-1] + JUMP[N-2] 의 점화식이 성립하게 됩니다. 문제 조건처럼 1234567로 나눌 때 모듈러 연산자 법칙을 적용하면 답을 얻을 수 있습니다. 코드: https://github.com/cottory/algorithm/blob/master/PROGRAMMERS/PG1.. 2020. 6. 15. 이전 1 2 다음
