우선순위큐

📖 문제 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net 💡 풀이 방식 • 다익스트라 (우선순위 큐) 최단 경로인 지점을 항상 우선으로 탐색하고자 점프 횟수 기준 오름차순 정렬하는 우선순위 큐를 활용한다. class Node implements Comparable { int x, y, w; public Node(int x, int y, int w) { this.x = x; this.y = y; this.w = w; } @Override public int compareTo(Node n) { // 💥 ..

📖 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 방식 • 우선순위 큐 - 적의 수를 순서대로 우선순위 큐에 저장한다. (무적권으로 방어할 라운드의 적의 수) - 무적권의 수보다 방어할 라운드가 많은 경우, 적의 수가 가장 적은 라운드에서 전투해 병력을 감소한다. - 병력이 0보다 적어지면, 게임이 종료되며 해당 라운드 수를 반환한다. / 게임을 클리어한 경우, 총 라운드 수를 반환한다. 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import java.util.*; class Solu..

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java.util.*; class Solution { public long solution(int n, int[] works) { PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); // 내림차순 정렬 for(int w : works) pq.add(w); while(n > 0) { int work = p..

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import java.util.*; class Solution { public int solution(int[] priorities, int location) { PriorityQueue pq = new PriorityQueue(Collections.reverseOrder()); // 내림차순 정렬 int answer = 0; for(int i : priori..

🔺 문제 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 import java.util.*; import java.io.*; public class Main { static int N, cnt; static int[][] arr; public static void main(String[] args) throws IOException { B..

🔺 문제 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(..

📍 정의 및 특징 완전 이진 트리의 일종 반정렬 상태 (완전 정렬 X) 중복값 허용 시간 복잡도 : O(logN) 종류 : 최대 힙 (부모 노드가 가장 큰) / 최소 힙 (부모 노드가 가장 작은) 구현 : 우선순위 큐 #완전이진트리 #우선순위큐 📍 필요 변수 ✔ 우선순위 큐 ✔ 배열 📍 실행 과정 부모 노드가 N (N ≥ 1)이면, 자식 노드는 *2, *2 + 1 자식 노드가 N이면, 부모 노드는 N/2 ➕ 예제 [백준/JAVA] 1927번: 최소 힙 🔺 문제 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는( bono039.tistory.com [..

🔺 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔺 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import java.util.*; import java.io.*; class Solution { public int solution(int[][] jobs) { int total = 0; int end = 0; // 수행되고 난 직후 시간 int idx = 0; // jobs 배열의 인덱스..

📍 정의 및 특징가중치가 있는 그래프에서 출발 노드에서부터 모든 노드 간 최단 거리 탐색 알고리즘특정 지점까지의 거리 = A까지의 거리 + A에서 특정 지점까지 소요되는 거리- 제약조건 : 엣지, 항상 양수여야 한다.- 시간 복잡도 : O(E log V)(모든 지점 간 최단 거리 구하는 시간 복잡도 : O(V³)) + 인접 리스트 쓰는 게 더 효율적+ 꼭 우선순위 큐를 사용해야 함. (사용자 정의 정렬)+ 가중치 있는 그래프 담기 위한 노드 클래스 별도 구현 필요 (또는 int[]) #가중치O    #양수    #모든정점간최단경로탐색  📍 필요 변수 · 자료구조1.  인접 리스트2.  최단 거리 배열3.  우선순위 큐4.  방문 배열 5.  노드 클래스   📍 실행 과정인접 리스트로 그래프 구현  ..