본문 바로가기

우선순위 큐10

[자바] 백준 15323 - ZigZag (java) 목차 문제 : boj15323 필요 알고리즘 우선순위 큐 정렬을 통해서도 짤 수 있다. 내 경우에 가장 간단히 짤 수 있는게 우선순위 큐라 생각해서 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 문제에서 제시된 조건을 정리해보면 다음과 같다. 1. K개의 문자열을 입력받는다. 2. N개의 문자를 입력받으며 각각에 대해, 입력받은 문자로 시작하는 현재까지 가장 말한 횟수가 적은 문자를 얘기한다. 3. 만약 가장 말한.. 2023. 3. 10.
[자바] 백준 11003 - 최솟값 찾기 (java) 목차 문제 : boj11003 필요 알고리즘 그리디 그리디 개념으로 풀 수 있는 문제이다. 덱, 우선순위 큐 생각한 그리디 로직을 구현하기 위해 필요하다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 우선 우선순위 큐를 사용한 풀이부터 얘기해보자 (코드2) 코드만 봐도 어떤 느낌인지 알 것 같다. 순서대로 입력값을 넣을 때, 입력값과 위치도 같이 넣는다. 그리고 우선순위 큐에서 최솟값을 꺼낼껀데, 이게 위치가 현재 보고 있.. 2023. 3. 9.
[자바] 백준 12764 - 싸지방에 간 준하 (java) 문제 : boj12764 필요 알고리즘 개념 시뮬레이션, 구현, 우선순위 큐 문제에서 제시된대로 시뮬레이션을 구현해주면 된다. 이 문제를 구현할 때 효율적이라 생각한게 우선순위 큐 이므로 우선순위큐도 사용했다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 뭔가 알고리즘적으로 풀이해나가야할 것 같이 생겼는데, 실은 문제에 나온 말 대로 구현만 해주면 풀 수 있다. 다만 쌩구현 문제라고 보기엔 생각이 좀 필요하다. 문제를 보고.. 2023. 2. 24.
[자바] 백준 23757 - 아이들과 선물 상자 (java) 문제 : boj23757 필요 알고리즘 개념 우선순위 큐 (priority queue) 또는 max heap 우선순위 큐로 시작해서 우선순위 큐로 끝나는 문제이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 대놓고 우선순위 큐(이하 pq) 문제이다. 다만, 가장 큰 값부터 꺼내져야하므로 pq 또한 최대값을 기준으로 꺼내질 수 있도록 해줘야 한다. 자바의 경우 new PriorityQueue(Collections.rever.. 2022. 8. 30.
[자바] 백준 1715 - 카드 정렬하기 (java) 문제 : boj1715 필요 알고리즘 개념 그리디 일정한 규칙을 정해 매번 해당 규칙을 적용시키다 보면 답이 나오는 알고리즘으로, 뭔가 알아야 하는건 아니고 그냥 그런 식으로 생각할 수 있어야 한다. 우선순위 큐 (Priority Queue), Min heap 다른걸 사용해서 풀어도 되지만, 이 문제를 가장 쉽게 풀 수 있는건 우선순위 큐를 사용해 min heap으로 사용하는 것이다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다... 2022. 8. 21.
[자바] 백준 21939 - 문제 추천 시스템 Version 1 (boj java) 문제 : boj21939 우선 한글적으로 좀 해맬만한 부분이 있어서 그것부터 써보겠다(제가 그래서 틀렸었단 얘깁니다 ㅠ). add의 '(추천 문제 리스트에 없는 문제 번호 P만 입력으로 주어진다. 이전에 추천 문제 리스트에 있던 문제 번호가 다른 난이도로 다시 들어 올 수 있다.)' 라는 설명과 solved의 '(추천 문제 리스트에 있는 문제 번호 P만 입력으로 주어진다.)' 라는 설명 때문이었다. 결론적으로 '추천 문제 리스트'는 처음 N개의 입력만을 뜻한다. 그리고 '이전에 추천 문제 리스트에 있던 문제 번호'라는 말은 즉, N개에 존재했었으나 solved로 제거된 경우엔 add로 동일한 번호가 들어올 수 있다는 말이었다. 마찬가지로 solved의 설명 또한 해석하자면 결국 N개에 존재했던 녀석들만 .. 2022. 5. 25.
[자바] 백준 10979 - 가넷이나 버는게 낫지 않아요? 문제 : boj10979 이하의 질문글을 보고 궁금해서 풀어보려다가 물렸다... 결국 31회의 시도로 개인 최장 시도횟수를 찍었고, 결국 뚫긴 했다. 10시간 넘게 걸렸다. 다른 분들 시도횟수까지 포함하면 자바 제출 시도 60회 만에 첫 통과이다 ㅋㅋㅋ 1. 자바로 풀 때 이 문제를 위한 메모리 최적화 일단 이게 자바로는 Scanner는 애초에 느려서 못쓰고, 많이들 사용하는 BufferdReader로 입력받는 순간 메모리 초과가 뜬다. 이게 BufferdReader가 미리 버퍼를 두고 더 많은 양을 미리 입력받아두기 때문에 그렇다. 일반적으로는 그정도론 문제가 없는데 이 문제는 메모리 제한이 너무 낮아 일단 그것만으로도 메모리 초과가 되는 것이다. BufferedReader 생성자 중 두 번째 para.. 2022. 4. 23.
[자바] 백준 1854 - K번째 최단경로 찾기 문제 : boj1854 다익스트라에 대한 이해를 높히고 으용하는데 매우 도움되는 문제이다. 강추! (플로이드 와샬 이해에는 23258번 밤편지 강추) 다른 문제 풀다가 2번째 최단경로를 찾아야 하는 경우가 있어 찾아보다가 이 문제도 풀게됬다. 다익스트라를 돌릴 때 1부터 n까지 가는 최소 가중치를 알려고 한다고 해보자. 이 때, n번에 처음 도착 했을 때 바로 답을 출력하면 될까? 가중치가 동일한 bfs와 달리 다익스트라는 가중치가 있을 때 사용하기 때문에 그러면 안된다. 다익스트라는 priority queue가 빌 때 까지 다 해봐야 답이 나온다. 그럼 2번째로 작은 가중치를 가지는 경로를 어떻게 구할 수 있을까? 어떠한 정점에 도달한 기록을 2개 유지하면 된다. 물론 이 때에도 마찬가지로 원하는 위치.. 2022. 4. 23.
백준 2170 자바 - 선 긋기 (boj 2170 java) 문제 : boj2170 당연히 전체 위치를 보게되면 -10억부터 +10억까지 봐야하므로 시간초과가 뜬다. 최대 100만개인 N을 기준으로 동작할 방법을 찾아야 한다. 문제에서 제시된 '예제 입력 1'은 이미 그렇게 정렬된 데이터긴 하지만, N개를 전부 x를 기준으로 오름차순으로 정렬했다고 생각하고 어떻게 풀지 한번 생각해보자. 4 1 3 2 5 3 5 6 7 그렇다면 위와 같이 x값 기준 오름차순으로 차례대로 확인할 경우(x값이 동일할 경우 y값 순서는 상관 없음. 그나마 내림차순으로 하면 아주 약간의 대입연산 정도는 줄여볼 수 있는데 의미 없음), 이전 y 값보다 현재의 x값이 작거나 같다면 이어진 항목으로 생각해볼 수 있다. 1-3을 본 후, 2-5를 보자. 현재 보고 있는 x인 2는 이전의 y값인 .. 2022. 3. 30.
백준 2696 자바 - 중앙값 구하기 (BOJ 2696 JAVA) 문제 : https://www.acmicpc.net/problem/2696 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/02600/BOJ_2696.java 1. 중앙값을 빨리 찾기 위한 방식을 찾아야 한다. 이렇게 중앙값을 취하는 경우 보통 절반씩 나눠서 어떠한 자료구조에 넣는 방식으로 풀면 괜찮은 경우가 많다. 2. 이 문제의 경우 힙 2개에 넣으면 괜찮게 풀 수 있다. PriorityQueue 2개를 둬보자. 하나는 맥스힙, 하나는 민힙으로 사용한다. 예를들어 1,2,3,4,5,6,7,8,9가 맥스힙에 1,2,3,4,5가 들어있고, 6,7,8,9가 민힙에 들어있다고 보자. 맥스힙에서 하나를 peek해보면 가장 큰 수인 '5'가.. 2021. 10. 29.

티스토리툴바