본문 바로가기

우선순위큐

 (12)
[프로그래머스] 이중우선순위큐 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제분석 최대 힙큐와 최소힙큐를 두어서 최대값과 최소값을 POP 할때마다 자료를 옮긴뒤 POP 해주면 된다. 배열에 집어 넣을때에는 최소 힙큐에 집어넣는다. 최대값을 꺼낼때에는 최소 힙큐에 모든 값을 최대 힙큐에 넣어준다. 그리고 최대 힙큐를 POP 한다. 최소값을 꺼낼때에는 최대 힙큐에서 모든 값을 최소 힙큐에 넣어준다. 그리고 최소 힙큐를 POP 한다. 💻 코드 import java.uti..
[프로그래머스] 베스트 앨범 https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🤔 문제분석 장르별로 음악을 묶는다. 장르별로 묶을때 우선순위 큐를 활용하여 묶는다. 장르별로 묶은다음 큐에서 2개씩 꺼내어 결과에 집어넣으면 된다. 💻 코드 import java.util.*; // // 가장 많이 재생된 노래를 두개씩 모아 베스트 앨범을 출시 // 각 장르별로 우선순위 큐를 활용하여 최대 2개씩 뽑아야한다. // (장르, 재생횟수), Map(장르,노래들) class Soluti..
[백준] 11779번 : 최소비용 구하기2 11779번: 최소비용 구하기 2 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 🤔 문제분석 우선순위큐를 이용하여 문제를 해결하였는데요, 예전에 풀었던 유형이랑 비슷해서 문제를 쉽게 풀 수 있었습니다. 방문 경로를 구하는 로직은 거꾸로 우선순위큐를 역추적 하면됩니다. 말로는 어렵지만 코드를 보면 쉽게 이해 할 수 있습니다. 💻 코드 import sys import heapq input = sys.stdin.readline INF = sys.maxsize n = int(input..
[백준] 13975번 : 파일 합치기 3 13975번: 파일 합치기 3 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net 🤔 문제분석 우선순위큐를 활용하여 가장 작은 파일부터 합쳐나아가는 문제입니다. 가장 작은 파일끼리 합쳐야 합의 가중치가 낮기때문입니다. 💻 코드 import sys import heapq input = sys.stdin.readline T = int(input()) for _ in range(T): K = int(input()) queue = [] for file in list(map(int, input().split())): h..
[백준] 2014번 : 소수의 곱 2014번: 소수의 곱 2014번: 소수의 곱 첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 www.acmicpc.net 🤔 문제분석 우선순위큐로 문제를 해결하였습니다. 배열을 순회하면서 중복된 곱을 피하여 곱셈을 하며 N번 만큼 우선순위 큐에서 꺼내고 넣는다. 중복된 곱을 피하기위해서는 Set자료구조를 활용할 수 있으나, 메모리 초과가 발생하여 다른 방식으로 생각해보아야한다. 아래의 표를보면 파란색을 대칭으로 중복된값이 존재하는것을 볼 수 있다. 2x3, 2x5, 2x7이 있다면 추후 3x2, 5x2, 7x2로 나올 수 있기에 자..
[백준] 1781번 : 컵라면 1781번: 컵라면 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 🤔 문제분석 두 가지의 풀이방식이 존재하는데 저번에 풀었던 문제의 유형중에서 완전 똑같은 문제의 유형이라 쉽게 문제를 풀이 하였습니다. 첫번째 방법으로는 서로소 집합을 활용하여 문제를 해결합니다. 서로소 집합으로 풀때에는 컵라면의 개수를 기준으로 내람차순 정렬하고 배열을 순회하면서 해당 노드의 (데드라인, 데드라인-1)을 유니온하여 다음의 리터레이션에서 부모노드를 데드라인-1 을 가르키도록 만들어 여러개를 넣을 수 없게 만듭니다. 두번째 방법으로는 우..
[백준] 1826번 : 연료 채우기 1826번: 연료 채우기 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 🤔 문제분석 데이터를 거리는 오름차순 기름은 내림차순으로 정렬하고, 데이터를 순회하면서 우선순위큐를 활용하여 문제를 해결하였습니다. 배열을 순회하면서 우선순위큐에 기름을 가장 많이 넣을 수 있는 주유소를 넣습니다. 그리고 탱크의 오일이 다 바닥날 수 있는 거리에 도달하면 우선순위 큐에서 기름을 가장 많이 넣을 수 있는 주유소에서 기름을 넣습니다. 여기서 중요한점은 단 한번을 넣을 수 있는게 아니라, ..
[백준] 13334번 : 철로 13334번: 철로 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 🤔 문제분석 처음에는 이분탐색으로 문제를 접근하였습니다. 우선 시작, 종료 위치를 오름차순으로 정렬합니다. start = 가장 작은위치, end = 가장 끝에있는위치를 시작으로 이분탐색을 시작합니다. mid값을 구한다음, (mid, mid +d) 범위안에 있는 위치들을 카운팅 해줍니다. (mid, mid+d) 기준으로 왼쪽으로 있는 개수, 기준으로 오른쪽에 있는 개수를 카운팅한뒤 왼쪽이 더많다..

티스토리툴바