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..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안 www.acmicpc.net 위 문제를 풀었던 소스 코드이다. 'use strict' const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const binarySearch = (array, target, start, end) =..

문제 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..

=== 를 썼는지 depth가 2가 넘어가는지 세미콜론 붙어있는지 전역변수를 사용 안했는지 함수는 1가지의 기능만 사용하는지 캐멀케이스로 구현되어 있는지 기능별로 파일을 나누었는지 Const를 let보다 위에 선언했는지. Const, let은 선언시점에 바로 할당했는지 함수 끝에 ; 붙였는지 값을 하드코딩하지 않았는지 Space, tab 혼용하지 않았는지 private한 변수에 _를 적절히 적용했는지 (function내부에 this는 기본적으로 모두 접근가능하고 const/let/var로 선언하면 외부에서 접근할 수 없다!) 혹시 모르니 arrow function보다 그냥 function 사용하기 (arrow function 은 this 바인딩을 갖지 않는다 / arrow function은 new를 호출..