[Java]running median 복습하면서 자바로 구현해보기

1. running median 우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median (tistory.com) 우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median 1. 개요 수열이 계속 변화할때, 이 수열의 중앙값을 어떻게 빠르게 구할 수 있을까 매번 정렬해서 중간의 값을 찾아야하는가? 최대 힙과 최소 힙을 이용하면 중앙값을 아주 쉽게 찾을 수 있다 결 deepdata.tistory.com 1) 최대힙과 최소힙 2개를 초기화 2) 최대힙의 원소의 수와 최소힙의 원소의 수가 동일하다면, 최대힙에 수를 넣어주고 3) 최대힙의 원소의 수가 최소힙의 원소의 수 + 1이라면, 최소힙에 수를 넣어준다. 즉 최대힙 > 최소힙 > 최대힙 > 최소힙 >....으로 번갈아가면서 수..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 21.
• textsms

[Java]자바 우선순위 큐 응용하기1 -뒤에서부터 생각하면 효과적으로 변하는 경우-

1. 문제 N개의 정수들이 있습니다. 이 중 정확히 앞에서부터 K개를 삭제하고 난 후, 남아있는 정수 중 가장 작은 숫자 하나를 제외한 평균을 구한다 했을 때 이 평균값이 최대가 될 때의 값을 구하는 프로그램을 작성해보세요. 단, K는 1이상 N - 2 이하까지만 고려하도록 합니다. 아니 쉬운문제 같은데 메모리,시간제한 도저히 안되는데..? 2. 풀이 K=1부터 시작해서, 배열에서 1개 지우고 나머지 N-1개에서 최솟값을 찾아 지우고, 평균을 구하고 K=2이면, 2개 지우고 나머지 N-2개에서 최솟값을 찾아 지우고, 평균을 구하고. ... K=N-2이면, N-2개 지우고 나머지 2개에서 최솟값 찾아 지우고, 평균 구하고 이렇게하면, 최솟값 찾는 과정에서 우선순위 큐에 매번 N-1개의 원소넣고 최솟값 찾고..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 20.
• textsms

자바 자료구조 우선순위 큐 심화응용 - 내가 원하는 우선순위에 맞는 우선순위 큐를 만드는 방법

1. 원하는 우선순위 기준에 맞는, 우선순위 큐 만들기 [(1, 7), (3, 2), (3, 1), (6, 2)] 와 같이 2차 평면상의 점들의 위치가 순서대로 주어졌을 때, 각각의 점의 위치가 주어질 때 마다 지금까지 주어진 점들 중 x, y의 곱이 가장 큰 경우를 출력하는 프로그램을 작성해보세요. 위와 같은 문제는 어떻게 해결할 수 있을까? 무작정 코드를 작성한다면 점의 위치가 주어질때마다, x*y를 계산하여 최대가 되는 경우를 골라야하므로, $O(N^{2})$이 된다. 하지만 PriorityQueue를 이용한다면 순간 최댓값을 찾는 과정이 O(logN)이 되어, 시간복잡도가 O(NlogN)이 된다. 그런데, 우선순위 큐를 어떻게 만들어야할까? 두 수의 곱이 최대가 되는 특별한 경우를 원하므로, 이..

• format_list_bulleted Java 기초
• · 2023. 3. 19.
• textsms

우선순위 큐 재활하면서 응용력 키우기1 -카드 정렬하기, N번째 큰 수

1. 문제1 1715번: 카드 정렬하기 (acmicpc.net) 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 문제를 잘 보면 매 순간 최소인 얘들을 더해나가면 최적이 될 것 같다는 생각이 든다 우선순위 큐에 주어진 수를 모두 넣는다 큐가 빌때까지 정수를 2개 뽑아, 두 수를 더한 다음에, 다시 우선순위 큐에 넣어준다. 그러니까, 10, 20, 40이 있는데, 10,20을 뽑아 10+20을 한 다음에 40을 바로 뽑는게 아니고, 30을 우선순위 큐에 넣어서 30,40이 된 상태에서,..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2023. 3. 18.
• textsms

자바 자료구조5 -우선순위 큐 사용법-

1. 우선순위 큐 큐가 먼저 들어오는 데이터가 먼저 나가는 선입선출 형식의 자료구조라면, 우선순위 큐는 항상 우선순위가 가장 높은 데이터에만 관심이 있고 이 데이터만 먼저 나갈 수 있는 형태의 자료구조 힙을 이용할때 삽입, 삭제, 탐색시간을 O(logN)으로 맞출 수 있어서 힙으로 보통 구현한다. 자바에서는 PriorityQueue라는 클래스를 사용할 수 있다. import java.util.PriorityQueue; PriorityQueue (name) = new PriorityQueue(); 형태의 선언 필요 자바는 기본적으로 최솟값을 우선적으로 뽑아준다. 2. 핵심 메소드 2-1) add(E) 우선순위 큐에 데이터 E를 추가 2-2) size() 우선순위 큐에 들어있는 데이터 수를 반환 2-3) i..

• format_list_bulleted Java 기초
• · 2023. 3. 4.
• textsms

회의실 배정 문제 응용하기 -모든 수업을 가능하게 하는 회의실의 수는-

1. 문제 11000번: 강의실 배정 (acmicpc.net) 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si = 현재 종료시간"이면 하나의 회의실에서 가능하다는 알고리즘으로 해결했다 근데 이 문제는 모든 수업을 가능하게 하는 최소의 회의실 수를 구해야한다 어떻게 하냐면 시작시간이 빠른 순서대로 오름차순 정렬한다 먼저 가..

• format_list_bulleted 그리디 알고리즘
• · 2022. 10. 18.
• textsms