본문 바로가기

전체 글

 (209)
[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 이중우선순위큐 우선순위 큐 문제 programmers.co.kr/learn/courses/30/lessons/42628 www.acmicpc.net/problem/7662 위 문제와 동일한 문제입니다. 테스트 케이스는 백준이 더 강력합니다. [문제 풀이] 이중 우선순위 큐를 구현하는 문제입니다. 사실 자료구조에 대해 숙련이 되어 있다면 매우 간단한 문제입니다. 레드 블랙 트리 기반의 자료 구조들은 최댓값, 최솟값을 무려 $O(1)$에 불러올 수 있기 때문입니다. 즉 C++의 multiset같은 경우, 그 자체로 이중 우선순위 큐의 역할을 할 수 있습니다. 자바의 경우 TreeSet은 중복이 안되므로 TreeMap을 사용하여 중복 처리를 해주는 방식으로 해결할 수 있습니다. 자바는 TreeSet이면 first, last..
[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 디스크 컨트롤러 구현 문제 programmers.co.kr/learn/courses/30/lessons/42627 [문제 풀이] 모든 작업에 대해 (작업이 끝난 시간) - (작업이 요청된 시간)의 합을 최소로 만드는 문제입니다. 하나의 디스크는 하나의 작업만 처리가 가능합니다. 작업 시간이 전혀 겹치지 않는다면 이 문제는 전혀 문제가 아닙니다. 그러나 작업 시간이 겹치는 경우에 어느 작업부터 시작해야 하는지 골라야 하는 것이 어려운 문제입니다. (작업이 끝난 시간) - (작업이 요청된 시간)만 보면 생각하기 쉽지 않으니 조금 형태를 바꿔보겠습니다. (작업이 끝난 시간) - (작업이 요청된 시간)은 (작업을 수행하는 시간) + (현재 시간) - (작업이 요청된 시간)으로 치환할 수 있습니다. 이해가 안 될 수도 있으니 그..
[프로그래머스 코딩테스트 고득점 Kit - 힙(Heap)] 더 맵게 우선 순위 큐 문제 programmers.co.kr/learn/courses/30/lessons/42626 [문제 풀이] 모든 음식이 K 이상의 스코빌 지수를 가질 때까지 음식들을 섞는 횟수를 구하는 문제입니다. 음식을 섞는 레시피는 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 입니다. 음식의 개수 N의 제한이 1,000,000입니다. 제한이 상당히 높으니 효율적으로 코드를 짤 필요가 있습니다. 매번 음식을 섞을 때마다 가장 맵지 않은 음식과 두 번째로 맵지 않은 음식을 뽑아낸다면 시간 복잡도가 음식의 개수 N, 섞는 횟수 M에 대해 $O(NM)$이 나옵니다. 섞는 횟수 M은 최악의 경우 N - 1이므로 결국 $O(N^2)이 됩니다. N이 100,000이어도..
[프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 프린터 큐 문제 programmers.co.kr/learn/courses/30/lessons/42587 [문제 풀이] 원형으로 계속 돌아가는 문서 중 우선순위가 가장 높은 것을 먼저 출력하는 문제입니다. 원형으로 문서를 계속 돌리고 확인해야 하므로 큐를 써야 한다고 생각할 수 있습니다. 가장 직관적으로 생각해보면 우선 배열을 순회하면서 1~9까지의 중요도가 몇 개씩 있는지 확인하고 큐 안에 문서에 대한 정보를 넣어야 합니다. 구해야 하는 답이 위치를 기반으로 찾게 됩니다. 그러므로 큐 안에 넣을 문서에 대한 정보는 위치가 필수적으로 들어갑니다. 중요도까지 넣어도 되지만 위치를 넣었다면 그 위치에 대한 중요도를 priorities배열로 구할 수 있기 때문에 넣지 않아도 좋습니다. 예를 들어 priorities가 ..
[프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 기능개발 구현 문제 programmers.co.kr/learn/courses/30/lessons/42586 [문제 풀이] 동시에 배포되는 기능의 개수를 순서대로 묻는 문제입니다. 뒷 순서의 기능이 먼저 배포되어도 이전 단계가 배포되지 않는다면 기다렸다가 한 번에 배포합니다. 즉 배포되지 않은 가장 앞 순서의 기능보다 뒷 순서가 더 짧은 시간이 걸린다면 그들을 그룹으로 묶고, 더 오래 걸리는 기능이 뒷 순서에 등장한다면 묶은 그룹의 크기를 answer에 넣고 그룹의 기능들이 배포되었다고 확정하면 됩니다. 그렇다는 것은 그룹을 구성할지 새로운 그룹을 만들지는 현재 순서의 기능과, 그룹의 가장 첫 번째 기능의 시간만 계속 비교해주면 됩니다. 그래서 큐를 사용합니다. 큐는 그룹의 역할을 합니다. 가장 첫 번째, 가장 먼..
[프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 주식가격 스택 문제 programmers.co.kr/learn/courses/30/lessons/42584 [문제 풀이] 주식의 가격이 떨어지지 않는 기간을 구하는 문제입니다. 단순하게 생각한다면 이중 for문을 사용하여서 현재 가격이 유지되는 시간을 구하면 풀이가 가능합니다. 그러나 위의 풀이는 $O(N^2)$의 시간 복잡도를 갖고 배열의 크기 N의 최대가 100,000이므로 효율이 매우 떨어집니다. $O(N^2)$의 풀이가 통과가 되는 것 같지만 실제로는 그렇게 풀면 안 됩니다. 주어진 순서대로 특정 상태가 유지되는지 확인하는 문제이므로 스택의 느낌이 납니다. 예시로 어떻게 푸는지 흐름을 보여드리면 스택으로 풀이할 방법이 보일 겁니다. prices가 [1, 2, 3, 2, 0, 1]처럼 주어져 있다고 가정하겠..
[프로그래머스 코딩테스트 고득점 Kit - 스택/큐] 다리를 지나는 트럭 구현 문제 programmers.co.kr/learn/courses/30/lessons/42583 오래 걸린 문제입니다. 알고리즘 풀이를 많이 해도 구현 문제를 연습하지 않으면 상당히 어렵습니다. [문제 풀이] 순서가 정해져 있는 트럭들이 다리를 지나는 데에 걸리는 최소 시간을 구하는 문제입니다. 다리의 특징은 먼저 들어간 트럭이 먼저 나와야 한다는 것입니다. 여기서 우리는 큐를 떠올려야 합니다. 이제부터 다리를 큐라고 생각하겠습니다. 어떻게 풀이해야 하는지 한 번에 감이 오지 않습니다. 그러므로 해야 하는 작업을 나눠서 생각해보겠습니다. 새로운 트럭이 다리에 들어올 때, 다리의 용량이 버틸 수 없다면 새로운 트럭이 지나갈 수 있을 때까지 다리 위의 트럭들을 건너 보냄 새로운 트럭이 다리에 들어올 때, ..
[프로그래머스 코딩테스트 고득점 Kit - 해시] 베스트앨범 해시 문제 programmers.co.kr/learn/courses/30/lessons/42579 [문제 풀이] 총 재생 수대로 장르를 정렬하고 장르 내에서도 가장 많은 재생 수와 두 번째로 많은 재생 수를 가진 고유 번호를 순서대로 출력하는 문제입니다. 문제를 이해하는 것조차 쉽지 않습니다. 요약하자면, 총 재생 수대로 장르를 정렬하고 그 장르 내에서도 가장 많은 재생 수를 가진 두 곡을 차례로 answer에 넣는 문제입니다. 단, 한 장르 내에 곡이 한 개인 경우 한 곡만 넣습니다. 한 번에 하려고 하면 머리가 아프니 한 개씩 천천히 생각해 봅시다. 우선 장르 별로 정렬할 필요가 있으니 장르 별 총 재생 수를 기록합시다. 이 과정까지는 간단한 해시 문제입니다. 맵을 하나 만들어 key로 장르 이름을 ..

티스토리툴바