문제https://www.acmicpc.net/problem/11724 문제 해석이 문제는 크루스칼 알고리즘을 활용해 MST(최소스패닝트리)를 생성하는 문제이다.Union-find 알고리즘을 활용해 집합을 대표하는 원소 변경과 사이클을 생성하지 않으면서 MST를 생성해 주면 된다. DisjointSet class를 만들어서 그 안에 union, find, connected 메서드를 만들어서 해결하였다.처음 생성자에서 갯수에 맞는 숫자 배열을 생성 후 COST 순으로 정렬된 가중치를 따라서 부모를 변경해 주면 된다.풀이const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";const input = require("fs").re..
문제https://www.acmicpc.net/problem/11724 문제 해석이 문제 또한 그래프 이론 중 BFS로 쉽게 풀 수 있다.그래프의 앞 뒤가 구분되지 않기 때문에, 앞과 뒤 모두 각 배열에 추가해주고 한번 지나간 곳을 체크해 주는 방식으로 풀면 된다.풀이const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";const input = require("fs").readFileSync(filePath).toString().trim().split("\n");function solution(input) { const [N, M] = input.shift().split(" ").map(Number); const lin..
문제https://www.acmicpc.net/problem/2606문제 해석이 문제는 BFS로 쉽게 풀 수 있다.다만, 그래프의 앞 뒤가 구분되지 않기 때문에 둘다 추가하는 방식으로 풀어야한다. 풀이const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";const input = require("fs").readFileSync(filePath).toString().trim().split("\n");function solution(input) { const qty = Number(input.shift()); const pair = Number(input.shift()); const computers = input.map(..
문제https://www.acmicpc.net/problem/2667문제 해석이 문제는 그래프 이론 카테고리에 있으며 BFS로 풀 수 있다.2중 반복문을 통해 모든 배열을 순회 하지만 그 위치에 집이 있는경우 BFS를 통해 먼저 값을 정답 배열에 추가해주고, grid 값을 0으로 바꿔주면 된다. 풀이const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";const input = require("fs").readFileSync(filePath).toString().trim().split("\n");function solution(input) { const N = Number(input.shift()); const grid ..
문제https://www.acmicpc.net/problem/16637문제 해석이 문제는 입력 제한부터 완전탐색의 냄새가 났다. (1 관건은 재귀 조건이였는데 문제에 힌트가 있었다. 자세히 봐야하는 조건은 중첩된 괄호는 사용할 수 없다인데 이 조건으로 인해 계산시 고려해야 하는 부분은 지금 계산하고 있는 부분과 그 다음 부분까지만 고려하면 되었다. 이를 현재 위치와 남은 길이를 비교하여 새로운 재귀 조건을 추가해 주었다. 풀이const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";const input = require("fs").readFileSync(filePath).toString().trim().split("\n");c..
문제https://www.acmicpc.net/problem/31863 문제 해석이 문제는 BFS로 해결하였다. 먼저 본진에 대해 뻗어나가며 해당 위치의 지진 횟수를 하나 증가 후 큐에 위치를 저장하였고,큐에서 하나씩 꺼내며, 해당 위치에 지진 횟수를 바탕으로 건물이 무너지게 되는지 판단하였다.그 후 건물이 무너지면 해당 위치로부터 여진을 전파하는 방식으로 해결하였다. 직관적인 x,y 좌표 설정을 위해 class도 같이 사용해 주었다. 풀이const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";const input = require("fs") .readFileSync(filePath) .toString() .trim()..
문제https://www.acmicpc.net/problem/12904문제 해석처음엔 재귀 방식으로 가볍게 도전했다가 처참하게 깨졌다...S의 길이가 999, T의 길이가 1000이기 때문에 재귀는 시간 초과가 발생한다. 해결 방법은 최대 길이가 T이기 때문에 T에서 하나씩 제거하며 결국 S와 길이가 같아졌을 때 비교하면 해결할 수 있다. 풀이const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";const input = require("fs").readFileSync(filePath).toString().trim().split("\n");function solution(input) {let a = input[0].trim(..
문제https://www.acmicpc.net/problem/17413 문제 해석이 문제는 아래 첫 풀이처럼 문제의 모든 조건을 하나씩 구현한 다음 해결해도 되지만, 정규식으로 쉽게 해결할 수도 있다. (정규식을 배우자..) 풀이const filePath = process.platform === "linux" ? "dev/stdin" : "../test.txt";const input = require("fs").readFileSync(filePath).toString().trim().split("\n");function solution(input) { const arr = input[0].split(""); let tempArr = ""; let answer = ""; for (let i = 0;..