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

[글에 앞서 공지사항] 취업 중단 이슈? 로 꽁꽁 숨겨둔(ㅋㅋㅋ) 댕강 떨어진,, 서류 지원서 (이력서 | 포트폴리오 | 자소서 중 제출한거 전부)를 800원에 제공하려고 합니다 ! 떨어진걸 누가 사겠나 ~ 싶다가 이렇게는 쓰지 말아야지 ㅋㅋㅋ 누군가 배울수도 있지 않나 해서 올립니다. 💳 결제 방법: 카카오페이 QR 코드로 3,000원을 송금해주세요.👉 아래 QR 코드를 스캔하여 결제 가능합니다.결제 후 댓글에 아래 정보를 남겨주세요:송금자 이름 (ex: 김취업)송금 시간 (ex: 오후 2:35)📩 파일 제공 방법:결제 확인 후, 구글 드라이브 URL을 23:00~24:00 사이에 제공드립니다.댓글 확인 후 빠르게 처리해 드릴게요! 😊🔒 주의사항:개인 정보를 포함하지 않으니 안심하세요.결제 후..

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

[글에 앞서 공지사항] 취업 중단 이슈? 로 꽁꽁 숨겨둔(ㅋㅋㅋ) 댕강 떨어진,, 서류 지원서 (이력서 | 포트폴리오 | 자소서 중 제출한거 전부)를 800원에 제공하려고 합니다 ! 떨어진걸 누가 사겠나 ~ 싶다가 이렇게는 쓰지 말아야지 ㅋㅋㅋ 누군가 배울수도 있지 않나 해서 올립니다. 💳 결제 방법: 카카오페이 QR 코드로 3,000원을 송금해주세요.👉 아래 QR 코드를 스캔하여 결제 가능합니다.결제 후 댓글에 아래 정보를 남겨주세요:송금자 이름 (ex: 김취업)송금 시간 (ex: 오후 2:35)📩 파일 제공 방법:결제 확인 후, 구글 드라이브 URL을 23:00~24:00 사이에 제공드립니다.댓글 확인 후 빠르게 처리해 드릴게요! 😊🔒 주의사항:개인 정보를 포함하지 않으니 안심하세요.결제 후..