Algorithm/백준[BOJ]18 [JS] 백준 2565번 전깃줄 문제 링크 https://www.acmicpc.net/problem/2565 풀이 전략 문제의 요지는 서로 교차하지 않기 위해 없애야하는 전깃줄의 최소 개수를 구하는 것이다. 그리디 풀이 방식으로 가장 많이 교차하고 있는 전깃줄을 없애가며 풀 수 있지만dp로 풀기 위해서는 이를 반대로 생각할줄 알아야했다. 전깃줄이 꼬이지 않게 하려면 오른쪽에 있는 전깃줄들의 번호가 오름차순이어야한다. 다시말해, 우리는 우리가 없애야하는 전깃줄을 최소로 하기 위해서, 전체 전봇대중 가장 긴 증가하는 부분수열(LIS)을 찾으면 된다. 이게 왜 가능하냐면, 만약 전깃줄이 꼬여있을 때 오른쪽 전깃줄의 전기선은 오름차순으로 가다가 중간중간 낮아지는 부분들이 있을 것이다. 이 부분의 전깃줄만 제거한다면, 우리가 원하는 최소의 갯수.. 2022. 11. 21. [JS] 백준 10814번 나이순 정렬 문제 링크 https://www.acmicpc.net/problem/10814 풀이 전략 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오. => stable하게 정렬해야 한다. => 대표적인 stable sort 알고리즘인 counting sort(계수정렬)을 이용하였습니다. 코드 const fs = require("fs"); const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n"); // counting sort. const n = input.shift(); solution(input.. 2022. 7. 12. [JS] 백준 1300번 K번째 수 문제 링크 https://www.acmicpc.net/problem/1300 풀이 전략 B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. 코드 const fs = require("fs"); const [n, k] = fs .readFileSync("/dev/stdin") .toString() .trim() .split(/\s/) .map(Number); solution(n, k); function solution(n, k) { let lt = 1; let rt = n * n; // k의 최대값은 n * n이기 때문에 rt는 n * n while (lt = k) rt = mid - 1; // 순서를 확인하여 k보다 크거나 같다면 rt를 mid보다 작게한 else .. 2022. 7. 8. [JS] 백준 2110번 공유기 설치 문제 링크 https://www.acmicpc.net/problem/2110 풀이 전략 C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. 코드 const fs = require("fs"); const input = fs .readFileSync("/dev/stdin") .toString() .trim() .split(/\s/) .map(Number); const n =.. 2022. 7. 6. [JS] 백준 2630번 색종이 만들기 문제 링크 https://www.acmicpc.net/problem/2630 풀이 전략 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다. 코드 const fs = require("fs"); const input = fs .readFileSync("/dev/stdi.. 2022. 6. 16. [JS] 백준 18258번 큐2 문제 링크 https://www.acmicpc.net/problem/18258 풀이 전략 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 큐를 이해하고 이를 구현하는 문제이다. 큐의 동작원리를 완전히 이해하고 있어야한다. 코드 const fs = require("fs"); const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n"); class Node { constructor(data) { this.data = data; this.next = null; } } class Queue { constructor() { this.head = null; this.rear = null; this.l.. 2022. 6. 14. [JS] 백준 1874번 스택 수열 문제 링크 https://www.acmicpc.net/problem/1874 풀이 전략 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라. 코드 const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); const input = []; rl.. 2022. 6. 11. [JS] 백준 4949번 균형잡힌 세상 문제 링크 https://www.acmicpc.net/problem/4949 풀이 전략 모든 오른쪽 괄호들은 자신과 짝을 이룰 수 있는 왼쪽 괄호가 존재한다. (다른 괄호 일 수도 있음) 모든 괄호들의 짝은 1:1 매칭만 가능하다. 즉, 괄호 하나가 둘 이상의 괄호와 짝지어지지 않는다. 코드 const fs = require("fs"); const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n"); input.pop(); solution(input); function solution(arr) { const answerArr = []; for (const str of arr) { answerArr.push(confirm(str)); }.. 2022. 6. 11. [JS] 백준 1707번 이분 그래프 문제 링크 https://www.acmicpc.net/problem/1707 풀이 전략 https://gmlwjd9405.github.io/2018/08/23/algorithm-bipartite-graph.html 우선 이분그래프에 대해서 자세히 알 필요가 있다. 이 블로그에 잘 정리해주신 분이 계셔서 상대적으로 쉽게 개념을 이해할 수 있었다. 다시 설명해보자면, 그래프가 존재하는데 이 그래프를 둘로 나누었을 때 모든 정점이 간선으로 연결되어있으면 이분그래프이다. 즉, 같은 그룹에 속한 정점은 인접하지 않아야한다. 코드 const fs = require("fs"); const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n"); c.. 2022. 6. 10. 이전 1 2 다음
