본문 바로가기

우선순위큐

[백준 11279] 최대 힙 (JAVA)

CodingTEST 2023. 12. 19. [백준 11279] 최대 힙 (JAVA) 백준 11279번 문제 - 최대 힙 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 분석 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다. (만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.) 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 해결 포인트 우선순위 큐(PriorityQ..

[백준 1927] 최소 힙 (JAVA)

CodingTEST 2023. 12. 8. [백준 1927] 최소 힙 (JAVA) 백준 1927번 문제 - 최소 힙 문제 분석 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성해라 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. N개의 수를 입력 받을 때, 0이 입력되면 가장 작은 값 출력 및 삭제, 다른 숫자는 배열에 삽입 프로그램은 처음에 비어있는 배열에서 시작 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력 해결 포인트 우선순위 큐 사용 코드 import java.io.*; import java.util.PriorityQueue; public class Main { public static void main(String[] args) thro..

[백준 1715] 카드 정렬하기 (JAVA)

CodingTEST 2023. 8. 12. [백준 1715] 카드 정렬하기 (JAVA) 백준 1715번 문제 - 카드 정렬하기 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제 분석 모든 카드를 합치기 위해 사용되는 합치는 최소 횟수를 구하고 출력해라. 해결 키 포인트 그리디 알고리즘 사용 가장 작은 수들끼리 먼저 합치는 것이 이 문제의 핵심 하지만, 시간도 메모리도 여유롭지 않다 List 사용 - 메모리, 시간 초과 ArrayList 사용 - 시간 초과 뽑아내고 넣고 정렬하고의 반복으로 메모리, 시간 초과가 난다 우선순위 큐 사용으로 메모리, 시간을 최소화한다. 그리디 알고리..

이전 1 다음

티스토리툴바