www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 핵심 아이디어. 기본적인 최소 스패닝 트리의 크루스칼 알고리즘을 사용하면 된다 추가적인 조건이 있다면 union을 1번 할 수 록 다른 모든 간선에 t만큼 비용이 추가된다. 모든 간선에 같은 값이 추가되므로, edge를 선택하는 순서에는 변화가 생기지 않으므로 비용을 더해줄때 누적된 t값을 추가적으로 더해주기만 하면된다. 'use strict' const readline = require("readline"); c..

www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 핵심아이디어. 최소 스패닝 트리의 크루스칼 알고리즘을 사용하면 된다. 다만, 특별한 점이 있다면 각 노드들이 발전소가 있는 도시와 일반도시로 나누어 진다는 것이다. 일반 도시들은 발전소에서 전기를 끌어와야 하므로, 모든 발전소 도시들의 미리 union으로 묶어놓고 크루스칼/유니온파인드 알고리즘을 사용하면 된다. 'use strict' const readline = re..

문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다. N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 예를 들어서 네 개의 문제가 있다고 하자. 4번 문제는 2번 문..

www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 위 문제를 풀 때 사용한 코드입니다. 자바스크립트는 원래 call by value이기 떄문에 아래 unionFind할때 배열 전체를 덮어씌우는 작업이 오래걸릴 줄 알고 class형으로 짜봤는데 오히려 시간이 더 늘어났습니다. (이유가 뭐지?) 'use strict' const readline = require("readline"); const rl = readlin..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 핵심 아이디어 이분탐색으로 찾으면된다! 최악의 경우 N,M이 각각 100000개 이므로 일반적인 방법으로는 시간초과가 나기 때문이다. 'use strict..

문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력 첫째 줄에 자연수 N의 최댓값을 출력한다. 핵심 아이디어 서로다른 n개의 수를 합쳤더니 s가 되었고, s가 주어진다. 이때 최대 n을 구하면 되는데, 최대 n을 만드려면 최대한 작은 수를 여러번 사용하기만 하면된다. 하지만 서로 다른 자연수여야 하므로, 1부터 1씩 증가해가며 더해주다가 s가 넘어가는 시점에 멈추고 1을 빼주면된다. 예를 들어서 s=200일때 1부터 20까지 차례로 더해보면 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 136 153 171 190 210 순으로 증가함을 알 ..

www.acmicpc.net/problem/14241 14241번: 슬라임 합치기 영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다. 모든 슬라임은 양수 크기를 가지고 있다. 두 www.acmicpc.net 문제를 풀 수 있는 정도로 구현하였고 가장 큰값을 추출해내는 MaxHeapTree이다. 단, www.acmicpc.net/problem/15903 처럼 BigInt가 필요한 경우에는 값이 infinity로 통일되어서 실패한다. BigInt인 경우를 적절하게 예외처리할 수 있게 바꿔야한다 ㅠ 'use strict' function PriorityQueue(comparator) { this.defaultComp..

www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이 www.acmicpc.net 문제를 풀기 위해 가장 최대값을 먼저 pop해주는 큐를 구현해야한다. 템플릿으로 사용하기 위한 최대힙을 사용한 코드는 다음과 같다. 'use strict' class MaxHeapTree { values = [] isEmpty() { return this.values.length === 0 } parentIndexOf(index) { return Math.floor((index - 1) / 2..