우선순위 큐3 우선순위 큐 (최소 힙) 구현하기 프로그래머스에서 자바스크립트로 코테 문제 풀면서 힙큐를 직접 구현해야 하는 김에 블로그에 정리 함.힙의 필요 기능 2개 push,pop힙에서의 각각의 원소들은 배열로 이루어져 있고 최소힙과 최대힙을 구현할 때 값의 기준은들어가는 배열의 첫번 째 인덱스 값을 비교값으로 구현함1. 삽입(push)힙은 트리 형태로 되어 있지만 배열로도 구현 하는게 더 편함.인덱스로 접근하면 root부터 left right가 존재함.삽입을 구현할려면 일단 배열 제일 마지막에 현재 삽입값을 넣어준다.이후 자신의 부모 노드를 비교해가며 부모 노드가 현재의 값보다 작다면 swap해줄것.이것을 루트까지 반복 ( 작은 값을 만난다면 멈추고 )push(a) { this.heap.push(a); if (this.h.. 2024. 4. 30. [우선순위 큐] 야근 지수 *** 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 큰 값을 모두 처리하는 것보다 큰 값들을 모두 균등하게 처리해야 제곱값들의 합이 최소가 나옴 a^2 + b^2 2023. 4. 3. [힙] 이중 우선순위 큐 문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 operation에 따라 삽입/ 최댓값 pop/ 최솟값 pop을 하는 문제 각 op에 따라 split로 나눠 준 뒤 각 연산을 수행 우선순위 큐로 짬 heapq 는 push와 동시에 정렬을 수행함 (기본적으로 최대 정렬-최솟값이 맨 앞으로) 파이썬에서 제공하는 heapq의 기본은 최소 힙을 기반으로 하고 있어서 pop을 할 시 최솟값이 나옴 최댓값은 큐의 맨 뒤에 있으므로 D.. 2023. 3. 29. 이전 1 다음