[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 -카드 정렬하기, 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

스택 테크닉 익히기1 -문자열 폭발

1. 문제 9935번: 문자열 폭발 (acmicpc.net) 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 2. 풀이1 주어진 첫번째 문자열에서 제시된 두번째 문자열을 모두 지우고 합친다음에, 또 두번째 문자열이 존재한다면 지우고 합쳐서... 이를 반복해서 더이상 지울 문자열이 존재하지 않으면 그것을 출력하면 되는 간단한 문제 단순히 replace 함수를 사용하면 그냥 시간초과다 replace 함수가 O(N)보다 조금 더 걸린다고 함 from sys import stdin s1 = stdin...

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

우선순위 큐로 중앙값을 빠르게 구하는 방법 - running median

1. 개요 수열이 계속 변화할때, 이 수열의 중앙값을 어떻게 빠르게 구할 수 있을까 매번 정렬해서 중간의 값을 찾아야하는가? 최대 힙과 최소 힙을 이용하면 중앙값을 아주 쉽게 찾을 수 있다 결론부터 말하자면, (크기와는 무관하게) 항의 순서대로 수열이 주어질때 최대힙에 들어간 원소의 수와 최소힙에 들어간 원소의 수가 서로 같을 때는 최대힙에 수를 넣어주고 최대힙의 원소의 수가 최소힙의 원소의 수보다 1개 더 많을때는 최소힙에 수를 넣어준다 즉 항상 최대힙 > 최소힙 > 최대힙 > 최소힙 >.. 으로 번갈아가면서 수를 넣어준다. 힙은 완벽하게 정렬해주지는 않지만, 루트에는 최소힙이면 힙에 들어간 원소들 중 최솟값이, 최대힙이면 힙에 들어간 원소들 중 최댓값이 온다는건 확실하다 최대힙에 원소를 넣으면 최대힙..

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

stack 활용법 - 올바른 괄호 문자열 판별

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/76502 코딩테스트 연습 - 괄호 회전하기 programmers.co.kr 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다. (), [], {} 는 모두 올바른 괄호 문자열입니다. 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A}도 올바른 괄호 문자열입니다. 예를 들어, []가 올바른 괄호 문자열이므로, ([])도 올바른 괄호 문자열입니다. 만약 A,B가 올바른 괄호 문자열이라면, AB도 올바른 괄호 문자열입니다. 예를 들어, {}와 ([])가 올바른 괄호 문자열이므로, {}([])가 올바른 괄호 문자열이므로, {}([])도 올바른 괄호 문자열입니다. 대괄호, 중괄호, 그리..

• format_list_bulleted 자료구조(스택,큐,해시맵)
• · 2021. 11. 17.
• textsms