힙

문제링크https://www.acmicpc.net/problem/11279 문제풀이자바스크립트로 풀게 된다면 힙(heap) 구조를 직접 class로 구현해서 풀어야 한다.힙 구조를 이용하면 계산횟수를 현저히 줄일 수 있다. 만약 힙구조에 대해 모른다면 이를 학습하고 이 문제를 풀기를 권한다.힙구조에 대해 이해하고 있기 때문에 문제없이 해당 문제를 풀 수 있었다. let fs = require("fs");let input = fs .readFileSync("/dev/stdin") .toString() .split("\n") .map((n) => Number(n));class MaxHeap { constructor() { this.heap = []; } pu..

문제링크https://www.acmicpc.net/problem/1927 문제풀이, 후기이 문제는 힙 자료구조를 이용해서 최솟 값을 구하는 연산을 최적화 하라는 문제라고 이해하면 된다. 자바스크립트에서 힙 자료구조를 구현하기 위해서는 Class를 이용해서 직접 구현해야 하므로 직접 구현하여 풀었다.참고로 초반엔 시간초과가 났는데 알고보니 console.log때문이었다. 매번 console.log를 하지 않고 답을 구한 뒤 한번의 console.log로 답을 출력하니 시간초과가 일어나지 않았다. 생각보다 console.log가 시간을 먹는다는 걸 알 수 있었다.heap 구현은 능숙하였기 때문에 쉽게 풀 수 있었고 한번더 heap자료구조와 시간복잡도를 최적화 해주는 트리구조에 대해 생각해보는 계기가 되었다...

문제링크https://www.acmicpc.net/problem/11000 제출코드 일단 수업들을 시작시간이 빠른순으로 정렬하고 시작시간이 같으면 끝나는 시간이 빠른시간 순으로 정렬하였다.그리고 정렬한 수업들을 순회하면서 최소 힙과 비교하면서(힙을 안쓰고 정렬을 이용하면 연산횟수가 기하급수적으로 많아서 시간초과가 발생한다.) 비어있는 강의실이 없는 경우 힙에 새롭게 추가하였다. 여기서 추가할 때 수업의 끝나는 시간만 힙에 추가했다. ( 우리가 필요한 정보는 수업이 끝나는 시간이기 때문이다. )마지막에 힙의 사이즈를 통해 몇개의 강의실이 쓰였는 지 알 수 있다.참고) 자바스크립트에서는 힙 자료구조를 직접 구현해야 한다.class MinHeap { constructor() { this.he..