문제 출처 https://www.acmicpc.net/problem/1405 정답 풀이 dfs를 활용해서 풀었다.  임의로 그래프를 생성해서 방문한 위치인지 확인해줘야 하는데 이때 그래프 크기는, 세로 가로 N*2+1 크기로 두면 된다.  그리고 처음 위치는 [N,N]으로 둔다  확률은, 해당 방향으로 이동했을 때 확률을 계속 곱해준후, N만큼 이동했을 때 총 단순환 확률에다가 더해준다.  정답 코드 const [N, e,w,s,n] = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(v => +v); let simple = 0 const dx = [0, 0, 1, -1] //동서남북const dy = [1,-1, 0, ..

문제 출처 https://www.acmicpc.net/problem/2458 정답 풀이순위를 확신할 수 있는 학생은자기보다 작은 학생 수 + 자기보다 큰 학생 수에서  -1 한 값이 n과 같은 학생이다.  +총 학생 수가 6명일 때 나보다 작은 학생이 3명이고, 나보다 큰 학생이 2명이면 나는 4번째 순서라는 것을 알 수 있음  dfs 탐색을 통해서 나보다 몇명이 큰지 계산하고, 나보다 작은 학생이 몇명인지 계산한다.  그 후, 그 합에서 -1 한 값이 n과 같으면 answer+= 1 을 한다. ! 정답 코드  let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n,m] = input[0].sp..

문제 출처 https://www.acmicpc.net/problem/1516 정답 풀이 위상 정렬 (Topological Sort)을 사용하여 해결할 수 있다. 문제에서 각 건물을 짓기 위해 필요한 시간과 그 건물의 선행 조건을 만족해야 하는 다른 건물들이 제시된다.  - 위상 정렬을 통해 건설 순서를 찾고, - 각 건물이 건설되기까지 걸리는 시간을 계산한다.  기본 과정 1. 각 건물마다 걸리는 건설 시간 저장 2. 각 건물에 대해 먼저 지어야 하는 건물의 관계를 그래프로 저장 3. 위상 정렬을 수행하면서, 각 건물의 최대 건설 시간을 계산 ### 위상 정렬이란? 위상 정렬은 방향성이 있는 비순환 그래프 에서 각 노드를 순서대로 나열하는 방법이다. 즉, 선행 조건을 가지는 작업들을 그 조건에 맞게 처리..

문제 출처 https://www.acmicpc.net/problem/3584 정답 풀이 이거는 사실 입력처리 하는 것이 까다로웠던 것 같다.  문제를 푸는 핵심은 - 각 노드의 부모를 배열에 저장을 한다. - 하나 노드의 모든 부모를 배열 (= 조상 배열)로 정리한다.   - 함수로 만들 것 - 비교해야 하는 노드 두개의  조상 배열을 비교한다. - 뒤에서부터 비교해서 일치하지 않을 때 그때의 조상이 답이 된다.   readline 모듈을 사용하여 입력을 한 줄씩 받아 배열 input에 저장한다. 입력이 완료되면 on('close') 이벤트가 실행되어 본격적으로 문제를 처리한다. const readline = require('readline');const rl = readline.createInterfa..

문제 출처 https://www.acmicpc.net/problem/13325 정답 코드 const fs = require('fs');const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');let k = Number(input[0]); // 트리의 높이let size = Math.pow(2, k + 1) - 1; // 트리의 전체 노드 수let arr = new Array(size + 1).fill(0); // 노드의 가중치를 저장하는 배열// 트리의 가중치 입력let weights = input[1].split(' ').map(Number);for (let i = 2; i = size) { ans += arr..

문제 출처 https://www.acmicpc.net/problem/4256 정답 풀이 정답 코드 const fs = require('fs');const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');let idx = 0;const T = parseInt(input[idx++]); // 테스트 케이스 수let sb = '';function findPostOrder(rootIdx, begin, end, N, preOrder, inOrder) { if (rootIdx >= N) return; // base case: 루트 인덱스가 배열 범위를 벗어나면 리턴 const rootValue = preOrder[rootIdx];..

문제 출처 https://www.acmicpc.net/problem/2225 정답 풀이 핵심 아이디어:dp[k][n]은 K개의 수로 N을 만드는 방법의 수를 의미합니다. 이를 구하기 위해서, 두 가지 상황을 고려합니다:dp[k][n-1]: K개의 수로 N-1을 만드는 경우에, 추가로 1을 더한 경우입니다. 즉, N을 만들기 위해 마지막에 1을 추가하는 방법입니다.dp[k-1][n]: K-1개의 수로 N을 만드는 경우에, 추가로 0을 하나 추가하는 방법입니다. 즉, N을 만들기 위해 마지막 수로 0을 더하는 방법입니다.이 두 가지를 더하면 dp[k][n]이 구해집니다.예시:N = 5, K = 3인 경우를 생각해보겠습니다. 즉, 숫자 5를 3개의 숫자의 합으로 나타내는 경우의 수를 구하는 문제입니다.1. d..

문제 출처 https://www.acmicpc.net/problem/1941 정답 풀이 dfs로 상하좌우 이동하면서 조건에 맞는 (Y가 3이하) 학생으로 채우는 7명을 탐색한다면, 틀린다. 왜냐하면 아래와 같이 T자 모양은 DFS로 만들지 못한다.   따라서 , 2 부분으로 나눠서 구현해야 한다. 1. DFS를 통한 7명의 학생 선택 2. 선택된 7명의 학생이 인접한지 확인하는 BFS 정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');const graph = input.map(el => el.split(''));function solution(graph) { let answer = 0; ..

문제 출처 https://www.acmicpc.net/problem/1240 정답 풀이 - 트리 구조 정의 : 입력으로 주어지는 간선 정보를 이용한다. - dfs 를 사용하여 탐색한다.  정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')let [n,m] = input[0].split(' ').map(v => +v); let tree = Array.from({length: n+1}, () => [])for(let i=1; i +v) tree[a].push([b,dis]) tree[b].push([a,dis]) }function dfs(node, target, distance, v..

문제 출처 https://www.acmicpc.net/problem/2661 정답 풀이 dfs 함수로 temp 배열을 채워나간다. 그리고, 채워나갈 때 조건은 check 함수를 통해 좋은 수열인지 체크할 때의 값이 true 여야만 다음 수를 채워나갈 수 있다.  정답 코드 //체크하는 함수 //dfs로 123 계속 채우는 함수 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')const n = Number(input[0]); function solution(n){ let temp = new Array(n).fill(0) function dfs(L){ if(L === n){ ..