문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 풀이 BFS는 큐를 이용한다. BFS는 각 레벨을 모두 살펴보고 다음 레벨로 내려가는 레벨 탐색을 사용하기 때문에 출발점에서 도착지로 가는 최단 거리를 구할 때 사용한다. ⭐⭐⭐ 레벨 탐색을 하게 되면 한 번만에 갈 수 있는 레벨의 정점을 모두 탐색한 후에 두 번만에..
문제 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다. 풀이 function solution(arr) { const n = arr.length; const dx = [-1, 0, 1, 0]; const dy = [0, 1, 0, -1]; let answer = 0; function DFS(x, y) { if (x === n - 1 && y === n - 1) { answer += 1; } else { for (let i = 0;..
문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프 로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6 가지입니다. 풀이 function solution(n, arr) { let ch = Array.from({ length: n + 1 }, () => 0); let graph = Array.from({ length: n + 1 }, () => []); let answer = 0; for (let [a, b] of arr) { graph[a] = [...graph[a], b]; } console.log(graph); function DFS(v) { if (v === n) answer += 1; else { for (let i..
문제 N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 프로그램을 작성하세요. 예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을찾으면 4+8+12 2+4+12로 2가지가 있습니다. 풀이 function solution(n, k, arr, m) { let answer = 0; function DFS(L, s, sum) { if (L === k && sum % m === 0) answer += 1; else { for (let i = s; i < n; i++) { DFS(L + 1, i + 1, sum + arr[i]); } } } DFS(0, 0, 0); return answer; } 1..
문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요. 풀이 조합의 경우는 간단하게 아래로 가지를 뻗을 때 현재 숫자 뒤부터 확인한다고 생각하면 된다. 조합에서는 현재까지 포함한 숫자를 다음 경우를 생각할 때 모두 제외하는 것이 중요하기 때문에 DFS 함수는 각 레벨을 나타내는 L과 각 L 자리에 들어갈 요소를 모두 확인하는 for문의 시작점인 start를 매개변수로 넘겨준다. 즉, for문을 돌 때 초기값인 start를 넘겨주어 이전에 사용한 값을 다시 사용하지 않도록 한다. function solution(n, r) { let c = Array.from({ length: r }); let answer = []; function DFS(L, s..
문제 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이그려진다. 3 1 2 4 4 3 6 7 9 16 N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. 풀이 #1 function countCombs(n, r) { let memo = Array.from({ length: n + 1 }, () => Array.from({ length: r + 1 }, () => 0) ); funct..
문제 다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요. nCr = n-1Cr-1 + n-1Cr 🤔 이 공식은 어떻게 성립하는 걸까? 예를 들어, 5C3 = 4C2 + 4C3을 살펴보자. 5C3은 {1, 2, 3, 4, 5} 중 3가지를 뽑는 경우의 수이다. 이것을 5의 기준에서 살펴보자면, (1) 5 자기 자신을 포함하는 경우와 (2) 5를 포함하지 않는 경우로 나눌 수 있다. (1)의 경우 이미 {⬜, ⬜, 5} 의 상태이므로 빈 자리에 {1, 2, 3, 4} 중 2개만 뽑으면 된다 → 4C2 (2)의 경우 {⬜, ⬜, ⬜} 세 자리 모두 비었으므로 {1, 2, 3, 4} 중 3개를 뽑는다. → 4C3 따라서 5C3 = 4C2 + 4C3 이다. 풀이 #1 function so..
문제 자연수 N을 입력하면 N!값을 구하세요. N! = n(n-1)(n-2).....21입니다. 만약 N=5라면 5!=5432*1=120입니다. 풀이 팩토리얼과 같이 값을 전달해야 하는 문제의 경우, 재귀를 돌 때 return을 통해 각 DFS가 값을 전달하고 이를 통해 구해진 하나의 값을 반환하여 해결한다. #1 function solution(n) { let answer = 1; function DFS(L, fact) { if (L === 1) { answer = fact; } else { DFS(L - 1, fact * (L - 1)); } } DFS(n, n); return answer; } #2 function solution(n) { function DFS(n) { if (n === 1) re..
