문제 현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니 다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다. 선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정합니다. 만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 합니다. M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지 출력하는 프로그램을 작성하세요. 풀이 // 학생들이 각각 멘토, 멘티가 될 수 있는지 확인 ex) (1, 2) (3, 4) function solution(arr) { const N = arr[0].len..
문제 N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌 우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 풀이 #1 DFS function solution(arr) { const n = arr.length; const dx = [-1, -1, 0, 1, 1, 1, 0, -1]; const dy = [0, 1, 1, 1, 0, -1, -1, -1]; let answer = 0; function DFS(x, y) { for (let i = 0; i = 0 && nx < n && ny..
문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 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..
문제 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6 가지입니다. 풀이 function solution(n, arr) { let graph = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0)); let ch = Array.from({ length: n + 1 }, () => 0); let answer = 0; // 인접행렬 for (let [a, b] of arr) { graph[a][b] = 1; } function DFS(v) { if (v === n) answer += 1; else { for (let i = 1; 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..
