onaeonae1

어떤 숫자들의 입력이 계~속 주어진다. 들어온 입력들에 대해서 중앙값을 계속 반환해야 한다. 자 그럼 이걸 어떻게 해볼까? 들어온 입력을 계속 push 하고 정렬을 한다?-> N번 동안 N 크기의 배열을 정렬하므로 N^2logN  . 따라서 시간 초과가 될 수 밖에 없다. 우리가 원하는 건 "중앙값"이다. 구체적으로 전체가 어떻게 정렬되어 있는지는 관심이 없다.중앙값을 T 라고 했을 때, T는 정렬된 List 에서 가운데에 위치해야 한다. 하지만, 정렬을 다해주면 시간 초과. 그래서 정답 T에 대해 배열을 다음과 같이 나눠보자.1. 무조건 작은 쪽 -> LEFT2. 무조건 큰 쪽 -> RIGHT LEFT에 있는 모든 애들은 RIGHT 보다 반드시 작아야 한다. 그래서 LEFT를 최대힙으로 설정. RIGH..

문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제 설명 - 각 작업의 시작 시점, 걸리는 시간이 주어짐 - 이들을 "특정 순서"로 진행하면 평균적인 대기 시간(=전체 대기 시간) 을 최소화할 수 있다. - 이때 대기 시간은 시작 시점~종료된 시점 으로 계산 - 대기 시간을 최소화해봤을 때 평균 값을 구해봐라 문제 풀이 풀이는 참 간단한데 구현에서 좀 까다롭다 우선, 풀이에서 사용할 자료구조..

문제 설명 매운 맛에 대한 배열 scoville 이 주어지고, 최소한의 매움 지수인 K가 주어진다 가장 안 매운 값 2개를 "섞어" 서 특정 값으로 바꾸는 연산이 가능하다 new = alpha + (beta *2). 이때 alpha 가 가장 작은 값, beta가 2번째로 작은 값 이렇게 "섞기"를 통해 매움 지수가 K를 넘기도록 하고, 이에 필요한 연산의 수를 구하는 것 어떻게 해도 구할 수 없다면 -1 을 결과를 출력 문제 풀이 힙(Heap) 을 사용하면 쉽게 풀어줄 수 있다. 우리가 접근해야 하는 것은 리스트 전체가 아니라 "최소값" 이므로, 이에 대해 접근하기 위한 Heap 자료구조 사용 python 에서는 heapq를 써서 쉽게 처리할 수 있다. 우선 해당 문제에서는 while 문을 돌면서 최소값..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 이번에도 위상정렬을 쓰는 문제다. 위상정렬을 쓰는 문제들은 그래프에서 순서가 주어지는데, 이 문제에서는 하나의 조건이 더 추가된다. 일단 문제를 풀어 써보자. 1~N까지 총 N개의 문제들로 구성된 문제집이 있다. 1이 가장 쉽고, N이 가장 어렵다.(=번호가 낮을 수록 쉬운 문제이다.) 그리고 주어지는 조건은 다음과 같다. N개의 문제를 모두 풀어야 한다. 주어진 순..