명왕성의 공전기록

https://www.acmicpc.net/problem/2644 문제는 각 node 간의 관계가 주어졌을 때, 특정 두 node의 촌수를 계산하는 문제다. (노드 간 거리 +1) 나는 그래프를 먼저 구현한 후, BFS를 활용하여 해결했다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim().split('\n') function solution(data) { const [N, temp, _, ...arr] = data // '촌수'를 구해야하는 두 노드 const [target1,target2] = temp.split(' ').m..

https://www.acmicpc.net/problem/11048 문제에서 '미로'라고 하길래, DFS나 BFS로 풀이해야 할 줄 알았는데, 자세히 읽으니 DP 문제였다. (허허) 문제는 좌표 [0,0]위치에 있던 인물이 우향 | 우하향 | 하향 으로만 움직일 수 있고, 각 좌표마다 '사탕의 갯수'가 있다고 할 때 가장 많은 사탕을 담는 경우에 대해 묻는다. 따라서 특정 좌표에서 우향 | 우하향 | 하향으로 움직일 때, 움직일 좌표가 미로에서 유효한 위치인지 파악 후, 위치가 유효하다면 해당 위치의 사탕 갯수, 이전 가지고 있던 사탕의 갯수를 더해 기록(메모라이징)해나가며 풀이하면 된다. 전체 소스 코드 const fs = require('fs') const input = fs.readFileSync(..

https://www.acmicpc.net/problem/7795 문제는 다음과 같이 A의 요소 값 > B의 요소 값을 만족하는 모든 경우를 출력하는 문제다. 수의 길이가 각각 '2만' 이하이기 때문에 완전탐색으로는 해결할 수 없으니, 이분탐색으로 해결했다. 이분탐색은 넓게 보아 탐색 범위를 좁혀가며 값을 찾아내는 방법이다. 위에 주어진 첫 번째 예시로, A = [1,3,7] 이고, B = [1,3]이라고 두자. 그리고 두 배열의 이분탐색 과정을 글로 쓰면 다음과 같다. 1. A[0] = 1과 B[0] = 1 을 비교했을 때, A의 요소 값 > B의 요소 값을 만족하지 못한다. 2. A[1] = 3과 B[0] = 1 을 비교했을 때, A의 요소 값 > B의 요소 값을 만족한다. => 이때, A,B는 오름..

https://www.acmicpc.net/problem/1337 문제는 길이가 n인 배열을 주고, 길이가 5이며 인접한 수의 차이가 1인 연속적인 배열을 만든다고 할 때, 추가해야 할 최소 원소의 갯수를 출력하는 문제다. 각 원소를 해쉬 테이블에 저장해둔 뒤, 검색하는 용도로 활용했다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim().split('\n') function solution(data) { data.shift() const table = {} data.forEach(el => table[el] = true) let..

https://www.acmicpc.net/problem/1003 해당 문제는 이전 포스팅과 같이, 문제가 요구하는 것에 규칙성(점화식)을 찾아 해결하면 된다. 2023.10.10 - [개발/algorithm] - 백준17175 - 피보나치는 지겨웡~ (DP) JS 0부터 6까지의 0, 1의 등장 횟수를 구하면 다음과 같다. 0 => 1 0 1 => 0 1 2 => 1 1 / f(2)는 f(1), f(0)을 호출하기 때문에 각각 한번씩이다 3 => 1 2 / f(2), f(1) | f(1), f(0) 을 호출한다 // 이때 f(1), f(0)는 fi(2)에서 호출 4 => 2 3 / fi(3), f(2) | f(2) f(1) f(1) f(0) | f(1) f(0) 5 => 3 5 // 중략 6 => 5 ..

https://www.acmicpc.net/problem/17175 문제는 피보나치 수열을 응용하여, input이 들어왔을 때 피보나치 수열이 몇 번 호출되는지를 묻는다. 먼저 문제에서 제시된 함수를 살펴봐야 하는데, fibonacci(n)이 호출되고 fibonacci(n-1)과 fibonacci(n-2)이 호출됨을 확인할 수 있다. (이때 n이 2 이하인 경우는 추가 호출이 없음을 인지해야 한다.) 즉 예를 들면 다음과 같다. // input === 2 fi(2) fi(1) fi(0) // => 총 3번 호출 // input === 3 fi(3) fi(2) fi(1) fi(1) fi(0) // 이때 fi(1)와 fi(0)은 fi(2)에서 일어나는 호출 // => 총 5번 // input === 4 fi..

https://www.acmicpc.net/problem/13909 해당 문제에는 아래와 같이 접근했다. 최대 입력값이 21억이기 때문에, 반복문으로는 해결할 수는 없으므로 나름의 규칙성이 있을 것이라 판단했다. 따라서 먼저 문제가 요구하는대로 시뮬레이션을 할 수 있는 코드를 먼저 작성해서 적용해보았다. // 시뮬레이션 코드 function solution(data) { const arr = Array.from({length : +data+1}, (_,i)=> [false,i]) for(let i = 1 ; i < +data+1 ; i ++) { for(let j = 1 ; j < +data+1 ; j ++) { if(j % i === 0) { arr[j][0] = !arr[j][0] } } } cons..

https://school.programmers.co.kr/learn/courses/30/lessons/77885 생각한 풀이과정은 다음과 같다. numbers 의 요소가 짝수인 경우, 2진수로 변환했을 때 마지막 비트는 무조건 0이다. '4'를 예로 들면, 4의 이진수가 '1000' 일 때, 마지막 비트 0을 1로 수정하면 1001(5)가 되므로 비트가 1~2개 다른 수 중 가장 작은 수가 5임을 확인할 수 있다. 따라서 짝수일 경우는 n이 주어질 때 n+1. 하지만 numbers의 요소가 홀수인 경우는 직접 구해야 한다. 만약 '7'이 주어질 경우의 7의 이진수는 111인데, 조건이 이보다는 커야 하므로 비트 자릿수는 최소 4자릿수이어야 한다. 때문에, 홀수 n이 주어진 경우는 7을 이진법으로 바꾼 ..