문제 출처 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/2565 정답 풀이 문제의 핵심은,  최장 증가 부분 수열을 이용하여 교차하지 않는 전깃줄의 최대 개수를 구하고, 나머지 전깃줄을 제거하는 방식 이다 !  - 두 전깃줄이 교차하는 조건은, 한쪽 끝이 연결된 A 전봇대에서의 순서와 다른 쪽 끝이 연결된 B 전봇대에서의 순서가 교차할 때이다. - 전깃줄이 교차하지 않게 하기 위해서는 B 전봇대에 연결된 번호가 증가하는 부분 수열이어야 한다.   A 전봇대에서의 순서를 기준으로 정렬한 후, B 전봇대에서의 최장 증가 부분 수열을 구하는 문제다. 최장 증가 부분 수열의 길이를 구하면, 그만큼의 전깃줄은 제거할 필요가 없으므로 전체 전깃줄에서 이 수를 뺀 값이 답이 된다.   정답 코드 cons..

문제 출처 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){ ..

문제 출처 https://www.acmicpc.net/problem/1949 정답 풀이 백준의 "우수마을" 문제는 트리 DP(dynamic programming on trees)를 사용하는 전형적인 문제입니다. 이 문제는 트리를 기반으로 우수 마을을 선정하여 마을 주민 수의 최대합을 구하는 문제입니다.문제 접근 방법:각 마을이 트리 형태로 연결되어 있다는 점을 이용해 DFS 탐색을 기반으로 DP를 적용해야 합니다.각 마을은 우수 마을이 될 수도 있고, 아닐 수도 있습니다.우수 마을이 될 경우, 이 마을과 연결된 다른 마을은 우수 마을이 될 수 없습니다.각 마을을 우수 마을로 선정하는 경우와 그렇지 않은 경우를 나눠서 DP로 해결합니다.알고리즘트리에서 DP를 사용하기 위해 DFS로 각 노드를 탐색합니다.각..

문제 출처 https://www.acmicpc.net/problem/11054 정답 풀이  increaseDP 배열:앞에서부터 현재 원소까지의 가장 긴 증가 부분 수열의 길이를 저장합니다.각 원소에 대해, 이전 원소들과 비교하여 자신보다 작은 값을 만나면 그 길이에 1을 더해 더 긴 수열로 갱신합니다.decreaseDP 배열:뒤에서부터 현재 원소까지의 가장 긴 감소 부분 수열의 길이를 저장합니다.각 원소에 대해, 이후 원소들과 비교하여 자신보다 작은 값을 만나면 그 길이에 1을 더해 더 긴 수열로 갱신합니다.결과 계산:각 인덱스에서 증가 부분과 감소 부분 수열을 더한 값을 구하고, 이 값 중 가장 큰 값을 선택합니다.증가 부분과 감소 부분에서 현재 원소가 두 번 더해지므로 마지막에 1을 빼줍니다.  각 ..

문제 출처 https://www.acmicpc.net/problem/2239 정답 풀이 다른 분의 풀이를 참고했는데, 오 어떻게 이런 생각을? ..? 기가 막히다  1. 먼저 주어진 스도쿠, 즉, board에서 0인 좌표를 zero 배열에 넣자. 2. 해당 zero 를 dfs 로 탐색을 한다. 3. 모든 zero 좌표를 다 돌았을 때의 board를 출력한다. 4. dfs 함수는 zero idx를 하나씩 올린다. 5. - 조건은 check 함수에 해당 좌표와 숫자를 넣었을 때 true 값이 출력되야 한다. 6. check 함수는 해당 좌표의 행과 열을 확인해서 같은 숫자가 있으면 false, 해당 작은 3*3 좌표에서 같은 숫자가 있으면 false 정답 코드 const board = require('fs'..

문제 출처https://www.acmicpc.net/problem/15681 정답 풀이 뭘 구하라는건지 이해가 안갔는데, 서브트리 개수를 구하는 문제이다.   뜬금없이 쿼리? 이랬는데, 해당 문제에서 쿼리는 5,4,8 의 서브트리를 구하라는 3개의 쿼리가 있다.  서브트리는 뭘까?=> 해당 노드를 루트로 하고, 그 아래 속하는 모든 자식 노드들을 포함하는 트리이다. !    정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n,r,q] = input[0].split(' ').map(v => +v)const graph = Array.from({length: n+1}, () => [..

문제 출처https://www.acmicpc.net/problem/15683 정답 풀이 다른 분의 코드를 참고했다.. !좋은 문제다. 정답 코드const [nums, ...arr] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n,m] = nums.split(' ').map(v => +v); let board = arr.map(el => el.split(' ').map(v => +v));const dir = [[-1,0],[0,1],[1, 0],[0,-1]]const dirType = [0,[0], [0,2], [0,1], [0,1,2], [0,1,2,3]]const cctv = []; let minSize..

문제 출처 https://www.acmicpc.net/problem/9663 정답 풀이 N-Queen 문제에서 체스 큐칙은 아래와 같다. - 퀸은 한행, 한 열에 하나씩만 놓을 수 있다. - 서로 같은 대각선상에 있으면 안된다.  아래 그림에서 빨간 부분은 피해서 다음 퀸을 놓아야 한다는 뜻 ! 가로나 세로는 피할 수 있겠고, 대각선은 어떻게 피할 수 있을까?  먼저 대각선 방향은 두개를 생각해줘야 한다. - 오른쪽 대각선 밑으로. - 왼쪽 대각선 밑으로.  먼저 왼쪽 대각선 밑 방향 좌표들의 공통점은?=> x좌표와 y좌표의 합이 같다 !!!  n=4일 때 x좌표 + y좌표의 합의 - 최솟값은 0이고  - 최댓값은 n*2-2 이다. 이를 배열로 표현하면 let diag1 = new Array(n*2-1)..