문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; let [N, K] = fs.readFileSync(filePath).toString().trim().split(" ").map(Number); const MAX =..
문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt"; let [num, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n"); const n = +num; const schedule = arr.map((row) => row.split(" ").map(Number)); let maxVal = Number.MIN_SAFE_INTEGE..
문제 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 풀이 function solution(n, arr) { // dy[i]는 i분 안에 풀 수 있는 최대 점수 // 해당 문제를 풀 것인지, 아닌지에 따라 최대 점수 구하기 const dy = Array.from({ length: n + 1 }).fill(0); for (let i = 0; i < arr.length; i++) { const [ps, pt] =..
문제 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? 풀이 /** * 다이나믹 프로그래밍(동적 계획법) * - 점화식(관계식)을 만드는 것이 중요 * - 문제를 작은 단위로 쪼개서 구하고, 이걸 기록해뒀다가 문제 범위(데이터 범위) 넓히기 * - dy[n] = dy[n-1] + 3처럼 관계를 구한다. * - 많은 문제를 풀어봐야 한다. */ function solution(n) { const dy = Array.from({ length: n + 1 }).fill(0); dy[1] = 1; dy..
문제 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 풀이 function solution(m, coin) { let dy = Array.from({ length: m + 1 }, () => 1000); // 가장 작은 동전으로 금액 m 만들 때보다 크게 설정 dy[0] = 0; // 각 동전을 사용할 경우 for (let i = 0; i < coin.length; i++) { // 해당 동전 사용 시 금액마다 필요한 동전 개수 세기 for (let j = coin[i]; j
문제 N개의 자연수로 이루어진 수열이 주어졌을 때, 그 중에서 가장 길게 증가하는(작은 수에서 큰 수로) 원소들의 집합을 찾는 프로그램을 작성하라. 예를 들어, 원소가 2, 7, 5, 8, 6, 4, 7, 12, 3 이면 가장 길게 증가하도록 원소들을 차례대로 뽑아내면 2, 5, 6, 7, 12를 뽑아내어 길 이가 5인 최대 부분 증가수열을 만들 수 있다. 풀이 function solution(arr) { const n = arr.length; let dy = Array.from({ length: n }, () => 0); dy[0] = 1; for (let i = 1; i < n; i++) { // 현재까지의 최장 증가 수열 길이는 현재 원소보다 앞에 위치한 작은 수 중 dy 값이 가장 큰 요소에서 1..
문제 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 class Deque { constructor() { this.deque = []; } push_front(newElement) { this.deque.unshift(newElement); } push_back(newElement) { this.deque.push(newElement); } pop_front() { if (this.empty()) return -1; re..
문제 https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 풀이 const input = require("fs") .readFileSync("/dev/stdin") .toString() .trim() .split("\n"); const maxLength = Math.max(...input.map(row => row.length)); let vertical = ""; for (let i = 0; i < maxLength; i++) { for (..
