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

문제 출처https://www.acmicpc.net/problem/1013 정답 풀이 - 정규식을 이용한 문자열을 판별해야겠다는 생각을 했다. - ^는 문자열의 시작을, $는 문자열의 끝을 의미한다. 이로써 문자열이 패턴과 완전히 일치하는지 확인할 수 있다. - |로 패턴 `100+1+`와 `01`을 선택적으로 매칭하고, 이를 반복해서 사용할 수 있도록 `+`를 사용한다.  정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const n = Number(input.shift()); function solution(n, input){ for(let i=0; i

문제 출처 https://www.acmicpc.net/problem/2293 정답 풀이 주의 : js로는 메모리 초과가 난다.  아래와 같이 2차원 그래프를 만들어줄 것이다. 세로 줄에는 동전의 가치 가로 줄에는 가치의 합이다. 그리고 각 그래프 안에는 해당 동전과 이전 동전으로 해당 합을 만들 수 있는 경우의 수를 구할 것이다.  우리는 저 빨간 부분을 return 해주면 된다.    아래 같은 경우에는 1 동전으로 1의 가치를 만들 수 있는 경우의 수는 1이다. (1 동전 1개)1 동전으로 8의 가치를 만들 수 있는 경우의 수는 8이다. (1 동전 8개)  그리고 아래와 2동전으로 가치의 합의 경우의 수를 구할 때, 가치의 합 2부터 생각해주면 된다. 왜냐하면 동전 2로는 가치 1을 만들 수 없기 때..

문제 출처 https://www.acmicpc.net/problem/2293 정답 풀이 알아보니, 이 문제는 js언어로 메모리 초과가 나는 문제인 것 같다.  이 분의 풀이를 보면 이해가 더 쉬울 것 같다. https://www.youtube.com/watch?v=LBOQikSpfNg 정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); const [n,k] = input.shift().split(' ').map(v => +v); const arr = []; for(let i=0; i틀린 코드 완전탐색의 방법밖에 떠오르지 않았다.. 메모리 초과... 가 될 걸 알았지만 작성한 이유는, 요즘에는 ..

문제 출처 https://www.acmicpc.net/problem/2638 정답 풀이 정답 코드 const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');const [n, m] = input.shift().split(' ').map(v => +v);const arr = [];for (let i = 0; i +v));}function solution(n, m, graph) { let answer = 0; bfs(n, m, graph); // 초기 외부 공기(-1)로 표시 while (true) { let hasCheese = false; // 치즈가 남아있는지 확인 l..

문제 출처 https://www.acmicpc.net/problem/12865 정답 풀이 풀이 보니까, dp로는 유명한 문제라는데 아직도 못 푸는 나 자신 머리 한대 때리고 시작하자.  이해하면 코드는 간단하나, 이해하기 생각보다 빡셌다. 다른 분들의 블로그를 봐도 잘 이해가 안갔고, 그래서 내가 이해한 방식대로 글을 작성해볼 예정이다.  ## dp 그래프 생성 아래와 같이 2차원 그래프 dp를 생성해줄 것이다. 세로 의미: 각 물건의 무게와 가치 가로 의미: 준서가 버틸 수 있는 무게  그렇다면 dp 그래프의 의미는 어떻게 될까? 각 물건을 넣고, 안넣고에 따라서 + 준서의 배낭 각 무게에 따라의 '가치'를 계속 update 해줄 것임. (이해가 안가도 아래 쭉 예시를 읽어보자 !) ## 초기화 아래 ..