명왕성의 공전기록

https://school.programmers.co.kr/learn/courses/30/lessons/49189 해당 문제는 문제 제목 말마따나, 루트 노트인 1에서 가장 먼 노드의 갯수를 찾는 문제다. 가장 거리가 먼 노드를 찾는 것이기에, DFS보다는 BFS가 더 문제 의도와 적합하다고 생각해 BFS로 접근했다. 2023.06.01 - [개발/algorithm] - 프로그래머스 - 타겟넘버 / 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 구현 방식 비교 생각한 풀이 방식은 다음과 같다. 각 노드끼리 이어진 그래프를 구현하고, [노드 번호, 거리] 를 인자로 하는 배열을 queue로 활용해 BFS 로직을 구현한다. 소스 코드 및 풀이 function solution(n, edge) { // 그..

https://www.acmicpc.net/problem/2910 이 문제는 그 말마따나 등장 빈도가 높은 순서대로 정렬, 등장 빈도가 같을 시 등장 순서대로 정렬하는 문제다. 문제를 해결하기 위해 객체에 각 숫자의 등장 빈도를 기록하고, 해당 객체를 정렬하는 방식으로 답을 구했다. // 입력값 // 5 2 // 2 1 2 1 2 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 = {} const a..

https://www.acmicpc.net/problem/1969 해당 문제를 쉽게 말하면, 주어지는 문자열 중 각 인덱스마다 가장 많은 빈도로 등장하는 알파벳(같은 빈도일 경우 사전순)을 채택하여 문자열을 만들며, (DNA) 문자열을 만들 때마다 (문자열의 갯수 - 채택된 문자열의 빈도 수) 를 누산하여 출력하는 문제다. (Hamming Distance) 나는 이를 단순하게 하기 위해, 먼저 배열 안에 객체를 넣어주었다. 이후 이중 반복문에서 들어오는 알파벳과 인덱스에 따라, 해당 인덱스를 가진 객체에 알파벳의 갯수를 추가할 수 있도록 구현했다. // 이때 M 은 문자열의 길이 = 8 const table = [] // 각 인덱스마다 배열 생성 for(let i = 0 ; i < M ; i ++) ta..

https://www.acmicpc.net/problem/11725 해당 문제는 그 말마따나 각 노드의 부모 노드를 구하는 문제다. 이 문제를 해결하기 위해 먼저 그래프를 구현한 다음, 너비우선탐색(BFS) 방식을 활용하여 1번 노드부터 차근차근 정답을 찾아나가고자 하였다. 그래프 구현 로직은 다음과 같다. // 노드의 갯수만큼 배열을 생성하고 const graph = Array.from({length : +N+1}, ()=> []) data.forEach((el)=> { // 연결된 노드를 그래프에 추가한다 const [to,from] = el.split(' ').map(Number) graph[to].push(from) graph[from].push(to) }) // 입력 예시대로 입력했을 경우 출력..

https://www.acmicpc.net/problem/1759 해당 문제는 몇 가지 알파벳을 제시한 후, 특정 조건(모음 1개 이상, 자음 2개 이상)을 만족하는 암호를 출력하는 문제다. 나는 산출할 수 있는 모든 조합을 만들 수 있는 백트래킹 로직과, 만들어진 조합을 검증하는 검증 로직 두 가지를 구현하여 문제를 해결하였다. const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim().split('\n') // 검증 로직 const verify = (arr) => { // 모음 배열 const vowels = ['a','e','i',..

https://school.programmers.co.kr/learn/courses/30/lessons/68645 이 문제는 2차원의 배열에 반시계 방향으로 숫자를 채운 뒤, 배열 순서대로 숫자를 반환하는 문제다. 처음 문제를 보았을 때는 풀지 못했던 문제인데, 백준에서 다양한 알고리즘 풀이 방식에 대해 공부하게 되면서 풀 수 있게 되었다. 생각한 로직은 다음과 같다. 먼저 다음과 같은 2차원 배열을 생성한다. 이때, 해당 배열은 삼각형 형태를 띄어야하므로, 인덱스에 따라 커지게 만들었다. 이후 하, 우, 좌상으로 이동하며 빈칸을 채우는 로직을 구현한다. 이때 해당 칸이 채워져 있을 경우나, 범위를 벗어나는 경우 이를 처리할 수 있는 함수도 함께 구현한다. (BFS나 DFS에서 사용하는 방식을 응용하였다..

해당 문제 풀이는 구글에 자바스크립트 풀이 방법이 존재하지 않길래 포스팅하게 되었다. https://www.acmicpc.net/problem/14940 풀이 방식은 다음과 같다. 1. 먼저 "2"로 표현된 목표 지점을 찾는다. 그리고 이를 찾는 과정에서 "원래갈 수 있는 땅인 부분 중 도달할 수 없는 위치"는 "-1"로 표현되어야 하므로, 전체적인 배열 matrix에서 "1"로 표현되어 있는 값을 미리 모두 -1로 수정한다. (findStarting 함수) 2. BFS 함수를 구현한다. 로직은 [이동거리, 위치] 를 요소로 갖는 queue를 사용하여 구현했고, visited 배열을 통해 이미 방문한 곳은 다시 방문하지 않도록 했다. 이때, 상하좌우로 이동하였을 때 이동이 가능한지를 확인하여("0"이 아..

https://www.acmicpc.net/problem/12865 문제는 최대로 담을 수 있는 무게와 담으려는 물품이 주어질 때, 배낭에 넣을 수 있는 물건들의 가치합의 최대값 요하는 문제다. // limit = 5 // data = [ [ '6', '13' ], [ '4', '8' ], [ '3', '6' ], [ '5', '12' ] ] const fs = require('fs') const input = fs.readFileSync(process.platform === "linux" ? "/dev/stdin":"입력.txt") .toString().trim().split("\n").map((x)=> x.split(" ")) const [_, limit] = input.shift().map(el=>..