문제https://www.acmicpc.net/problem/1753 풀이이번 문제는 다익스트라 알고리즘 문제이다. 필자는 BFS를 이용한 다익스트라 알고리즘 구현을 시도했지만, 시간 초과 에러가 발생했다.이유는 BFS의 탐색 방식에 있다. 필자의 BFS는 큐에 탐색할 경로의 정보를 담고 하나씩 가져오며 완전 탐색을 진행했다. 불필요한 경로까지 검증하면 시간 복잡도가 높아진다.... 이를 해결하기 위해서는 항상 최소의 값을 가져올 수 있는 최소힙을 이용해야 한다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim..
최소힙
문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 방법 이번 문제는 최소 힙을 적용한 우선순위 큐를 이용해 풀어야 했던 문제이다. 나는 정렬을 이용해 웨이브가 가장 큰 순서대로 해결하려 했다. 하지만, 이렇게 하게 되면 초반에 작은 웹이브들의 합이 갖고있는 병사의 수를 넘는 경우는 처리하지 못하기에 포기했다. 그렇다면 큰 웨이브는 무적권을 사용한다 치고, 작은 수만 골라 문제를 풀어야 한다는 것이다. 이진 탐색을 통해 웨이..
