본문 바로가기
반응형

heap4

[Python] 프로그래머스 - 디스크 컨트롤러(탐욕기법) 프로그래머스 코딩 테스트는 안 하다가, 지식인을 통해서 답변을 하면서 하게 되었네요. https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제에서 핵심은 작업을 관리하는 것을 어떻게 시뮬레이션할 것인가입니다. 현재 태스크에 있는 작업들은 모두 대기상태에서 어떤 것을 먼저 실행하는 것이 좋을까입니다. 태스크에 있는 작업이 한개뿐이라면 전혀 문제가 없겠죠. 하지만 여러개라면, 우선순위를 정해야 합니다. K개의 작업이 있다면, 먼저 수행하는 작업에 .. 2023. 3. 23.
백준 #1572 중앙값(힙) 이번 문제는 N개의 데이터가 들어올 때, K개의 연속된 값 구간의 중앙값을 구해야 하는 문제입니다. 일반적으로 N개의 정렬되지 않은 데이터가 주어졌을 때, 중앙값을 구하는 것을 \(O(N)\) 알고리즘으로 가능합니다. N개의 데이터에 K개의 연속된 값 구간은 \(N-K+1\)개가 존재합니다. 만약, 위의 방법으로 하고자 한다면, \(O(NK)\) 알고리즘으로 풀어야 합니다. 그런데 문제에서 N의 최대값을 250,000, K의 최대값은 5,000으로 \(O(NK)\) 알고리즘으로 풀게 되면 시간초과가 될 것이 뻔합니다. https://www.acmicpc.net/problem/1572 1572번: 중앙값 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 .. 2022. 9. 7.
자료구조의 보석 힙(Heap) 2010-02-19 19:27:20 오늘은 자료 구조의 보석인 힙(Heap)을 찾아서 가기로 해요.. 태고의 도시 야율론에 힙이라는 보물이 숨겨져 있다는 보물지도를 얻은 이비는 친구인 리시타와 피오나와 함께 야율론으로 떠나는 배를 탑니다. 이 보물지도는 고대 문자인 에리스문으로 되어 있는데, 이것을 해석하는 것은 아주 어렵다고 합니다. 특히 다중상속문이 존재하는 이 언어는, 고도의 지식을 요합니다. 더구나 템플릿을 이용하기도 하는데, 이 템플릿은 스택, 큐, 동적 배열을 한단어로 표현할 수 있을 정도로 강력한 마법 언어로 알려져 왔습니다. 다행히 이 보물지도에 있는 에리스문은 상속도 없고 템플릿도 없습니다. 리시타와 피오나 모두 준비가 되었다고 하는군요. 선장인 이비가 출발을 외칩니다..~ 뿌웅..~~~.. 2011. 9. 27.
Prim algorithm with heap Prim algorithm with heap 제가 좋아하는 자료구조는 힙(Heap)이라는 것입니다. 힙은 이진트리 중에 특별한 형태를 사용하고 있습니다. 꽉 찬 이진트리를 사용함으로써 배열을 그대로 이진트리로 사용할 수 있습니다. 이중에서 최소힙과 최대힙이 있는데, 루트의 값이 가장 작은 경우를 최소힙, 가장 큰 경우를 최대힙으로 이해하면 됩니다. 힙의 조건은 다음과 같습니다. 힙의 제일 아래층을 제외하고 꽉 차있고, 제일 아래층은 왼쪽부터 꽉 차있다. 힙의 모든 노드는 하나의 값을 가지고 있다. 각 노드의 값은 자식의 값보다 항상 작다. (최소힙) 최대힙의 경우에는 3)항만 다릅니다. 꽉 찬 이진트리이기 때문에 배열로 바로 구현할 수 있습니다. 그렇지 않다면 자식들의 링크를 보관해야 하죠. 다음의 힙을.. 2011. 9. 27.
728x90