본문 바로가기

전체 글

(45)
[백준 1655 : JAVA] 가운데를 말해요 / PriorityQueue 개요 PriorityQueue를 이용하여 풀 수 있는 문제이다. 해당 자료구조에 대한 이해도가 없는 사람들은 기초 문제부터 풀고 오면 좋을 것이다. 문제를 읽어보면 오름차순 정렬을 했을 때 가운데 인덱스에 있는 값을 찾는 문제이다. https://www.acmicpc.net/problem/11286 불러오는 중입니다... https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연..
[백준 11286 : JAVA] 절대값 힙 / PriorityQueue 개요 이 문제는 백준 11279 최대 힙 문제와 다른 점이 거의 없다. 자세한 사항이 궁금하면 아래 링크를 참조하면 좋을 것 같다. Comparator 인터페이스의 compare메소드만 오버라이딩해주면 문제의 풀이는 끝난다. 2020/01/26 - [알고리즘/백준] - [백준 11279 : JAVA] 최대 힙 / PriorityQueue [백준 11279 : JAVA] 최대 힙 / PriorityQueue 개요 priorityqueue 자료구조를 이용하여 푸는 문제이다. 기존의 queue는 [FIFO] 구조로 First In First Out 구조를 가지고 있다. 식당에 밥을 먹기 위해 가서 줄을 섰을 때 맨 처음 줄을 선 사람이 맨 처음으로.. dragon-h.tistory.com 문제 절댓값 힙은 다..
[백준 1927 : JAVA] 최소 힙 / PriorityQueue 개요 이 문제는 백준 11279 최대 힙 문제와 다른 점이 거의 없다. 자세한 사항이 궁금하면 아래 링크를 참조하면 좋을 것 같다. Comparator 인터페이스의 compare메소드만 오버라이딩해주면 문제의 풀이는 끝난다. 2020/01/26 - [분류 전체보기] - [백준 11279 : JAVA] 최대 힙 / PriorityQueue [백준 11279 : JAVA] 최대 힙 / PriorityQueue 개요 priorityqueue 자료구조를 이용하여 푸는 문제이다. 기존의 queue는 [FIFO] 구조로 First In First Out 구조를 가지고 있다. 식당에 밥을 먹기 위해 가서 줄을 섰을 때 맨 처음 줄을 선 사람이 맨 처음으로.. dragon-h.tistory.com 문제 널리 잘 알려진..
[백준 11279 : JAVA] 최대 힙 / PriorityQueue 개요 priorityqueue 자료구조를 이용하여 푸는 문제이다. 기존의 queue는 [FIFO] 구조로 First In First Out 구조를 가지고 있다. 식당에 밥을 먹기 위해 가서 줄을 섰을 때 맨 처음 줄을 선 사람이 맨 처음으로 식당에 들어가는 것과 같이 입력이 10 20 30 40 50 이 있을 때 출력도 10 20 30 40 50 이 된다고 생각하면 된다. 따라서 stack [LIFO] 과는 반대의 개념이라고 볼 수 있다. priorityqueue는 queue 구조와 비슷하게 생각할 수 있고, 이름처럼 우선순위 큐이다. queue는 First In First Out이라면 priorityqueue는 Comparator 인터페이스의 compare 메소드를 오버라이딩 한 코드에 따라 우선순위가..
[백준 12015 : JAVA] 가장 긴 증가하는 부분 수열 2 / 이진탐색 풀이 개요 이 문제는 [최장 증가수열] LIS (Longest Increasing Subsequence)로 유명한 문제인 것 같다. 이 문제는 두 번째 버전의 문제로 [11053 가장 긴 증가하는 수열 1] 문제가 첫 번째 버전의 문제라고 생각할 수 있다. 첫 번째 버전을 풀지 않았다면 풀고 오는것을 추천한다. ▶ https://www.acmicpc.net/problem/11053 기존의 첫 번째 버전과 차이점은 입력되는 값의 범위이다. 첫 번째 버전보다 입력되는 값의 범위가 1,000 -> 1,000,000으로 변경되었기 때문에 기존의 동적 프로그래밍 방식으로 풀게 되면 O(N^2)이 되어 시간 초과가 나게 된다. 우리는 이분 탐색을 이용하여 O(NlogN)의 시간 복잡도로 풀게 될 것이다. 문제 수열 A가..