알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 이중우선순위큐

문제 : https://programmers.co.kr/learn/courses/30/lessons/42628 서론 제목에 나와있듯 우선순위 큐를 이용한 문제. 이중우선순위 큐를 이용하려면 최대힙, 최소힙 두개의 우선순위 큐를 만들면 될듯하지만 STL의 우선순위 큐는 인덱스를 이용한 접근이 안된다. 벡터의 위엄이다. 어쨌든 그래서 생각한 방법은 1. 우선순위 큐를 배열로 구현한다. 2. 우선순위 큐를 이용하지 않는다. 3. 다른분의 풀이를 참고한다. 2번을 선택했는데, 우선순위 큐를 만들지 않고 단순히 벡터를 만들고 삽입할떄마다 정렬해주고 최대값 삭제하려면 가장 뒤의 값을, 최소값 삭제하려면 가장 앞의 값을 지우는 형태로 풀었더니 효율성체크가 없어서 통과했다. 그래도 개운치 않아서 우선순위 큐를 이용해서..

2019. 11. 2. 19:32
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 단속카메라

문제 : https://programmers.co.kr/learn/courses/30/lessons/42884 풀이 그리디 알고리즘을 이용하여야 한다. 여러 방법이 있겠으나 우선순위 큐를 이용하여 풀었다. routes를 첫항을 기준으로 오름차순 정렬하면 [[-20,15], [-18,-13], [-14,-5], [-5,-3]] 여기서 [-20,15], [-18,-13], [-14,-5]는 [-14,-13] 범위에서 중복된다. 그러므로 위 세개는 -14, -13 둘 중 하나에서 카메라를 설치하고 -5~-3의 범위에서 카메라를 또 하나 설치한다. 시간이 -30000부터 계속 증가하다가 -20이 되면 [-20, 15]를 만난다. 그럼 [-20, 15]를 우선순위 큐에 넣는다. 우선순위 큐는 현재 고속도로에 존재..

2019. 10. 27. 10:50
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 디스크 컨트롤러

문제 : https://programmers.co.kr/learn/courses/30/lessons/42627 서론 운영체제의 SJF(Shortest Job First)에서 착안한 문제인것 같다. 풀이 예제를 통해 작업시간이 짧은것부터 우선적으로 처리하는게 효율적이라는걸 유추할 수 있다. 그러나 작업시간이 짧은것을 먼저 처리하기 위해 하드디스크가 쉬고 있는데 이미 요청을 받은 다른 작업을 기다리게 하고 작업시간이 짧은것을 요청받을때까지 기다리지는 않는다. 요청을 받은 작업들 중 작업시간이 짧은것을 먼저 처리하기 위해 min-heap의 우선순위 큐를 이용한다. 시간이 0초부터 1초씩 증가하면서 jobs에 요청을 받은 작업이 있는지 확인한다. 아직 없다면 시간을 계속 증가시켜주고 있다면 요청받은 작업을 우선..

2019. 10. 11. 21:08
알고리즘/문제풀이 - 백준

백준 16235 나무 재테크

문제 : https://www.acmicpc.net/problem/16235 서론 시뮬레이션 문제. 풀이과정 나무를 저장하기 위해 자료형을 벡터로 가지는 2차원 배열, A의 2차원 배열, 영양분을 저장히기 위한 2차원 배열을 각각 만들어주고 문제에서 시키는대로 하면 시간초과를 고려하지 않는 구현에 큰 어려움은 없다. 주의해야할점은 처음 주어지는 나무의 위치가 (x,y)인데 r이 x이고 c가 y다. 봄에서 죽을 나무들은 다 죽인 후 여름을 진행해야한다. 가을에서 한 칸에 나이가 5의 배수인 나무가 n개 있으면 n번 번식시켜야한다. 그리고 각 칸에 나무를 저장히기 위해 벡터 컨테이너를 사용했는데, 시간초과가 떴다. 봄에서 나무가 여러개면 어린 나무부터 양분을 먹어야 하기때문에 사용한 sort, 오름차순으로 ..

2019. 10. 2. 13:22
알고리즘/문제풀이 - 백준

백준 2075 N번째 큰 수

문제 : https://www.acmicpc.net/problem/2075 서론 메모리 제한이 잡혀있다. 입력값을 전부 배열에 넣거나 큐에 넣으면 메모리초과가 발생할 것이다. 일부만 넣어야 한다. 아이디어 최소힙을 가지는 우선순위 큐를 만든 다음 큐에는 입력값 중 가장 큰 수 n개만 들어가도록 한다. 그럼 큐의 루트 힙이 정답이 될 것이다. 큐의 사이즈가 n개가 될때까지는 그냥 채워주고 n개가 되면 큐의 루트 힙보다 큰 값만 큐에 집어넣고 큐의 루트힙은 빼주면 된다. 그럼 입력값 중 가장 큰 수 n개가 들어있는 큐가 유지된다. 구현 //c++ #pragma warning(disable:4996) #include #include int main() { std::priority_queueq; int n; s..

2019. 8. 22. 11:49
알고리즘/문제풀이 - 백준

백준 1655 가운데를 말해요

문제 : https://www.acmicpc.net/problem/1655 서론 상당히 오래 걸린 문제. 반나절은 푼것 같다. 우선순위 큐는 내부 힙이 완벽히 정렬이 되지는 않지만 큐에서 빼낼때마다 배열에 저장하면 완벽히 정렬이 된다. 그래서 입력 한번 받을때마다 큐를 비웠다 채웠다를 반복해봤는데 시간초과 트리에서 수식으로 얻을 수 있는게 있는지 고민해봤으나 찾을 수 없었다. 엑셀에서 예상되는 결과를 표로 그려봤는데 시프트레지스터가 떠올라서 아이디어를 얻을 수 있었다. 아이디어 입력값이 들어올때마다 예상되는 중앙값을 표로 나타내봤다. 각 행의 노란색 셀이 중앙값인데, 노란색 셀이 두개면 둘 중 최소값이다. 우선순위 큐에선 입력될때마다 위와 같이 완벽히 정렬이 되지는 않지만 일단은 정렬이 된다고 가정하고 ..

2019. 8. 21. 20:29