YG - 96년생 , 강아지 있음, 개발자 희망

너비 우선 탐색(BFS, Breadth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. Ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다. 너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색 너비 우선 탐색(BFS)이 깊이 우선 탐색..

문제 7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격 자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다. 풀이 function solution(board) { let answer = 0; let dx = [-1, 0, 1, 0]; let dy = [0, 1, 0, -1]; function DFS(x, y) { if (x === 6 && y === 6) { answer++; } else { for (let i = 0; i < 4; i++) { let nx = x + dx[i];..

문제 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 총 6 가지입니다. 풀이 function solution(n, arr) { let answer = 0; let graph = Array.from(Array(n + 1), () => Array()); let ch = Array.from({ length: n + 1 }, () => 0); let path = []; for (let [a, b] of arr) { graph[a].push(b); } function DFS(v) { if (v === n..

문제 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 1 2 3 4 5 1 2 5 1 3 4 2 5 1 3 4 5 1 4 2 5 1 4 5 총 6 가지입니다. 풀이 function solution(n, arr) { let answer = 0; let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); // console.log(graph); let ch = Array.from({ length: n + 1 }, () => 0); let path = []; for (let [a, b] of arr) { graph[a][b] =..

1. 무방향 그래프 양방향이라고 생각할수 있고 그래프를 행렬로 표현하였을 때 다음과 같습니다. 2. 방향 그래프 한 방향으로만 이동 가능한 그래프를 행렬로 나타낸 그림입니다. 3. 가중치 방향그래프 방향에 가중치까지 나타냈을때 그래프[a][b] = c를 행렬로 나타낸 그림입니다.

문제 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; let tmp = Array.from({ length: k }, () => 0); function DFS(L, s, sum) { if (L === k) { console.log(tmp); if (sum % m === 0) { answer++; } } else { for (let i = s; i < n; i++) ..

문제 1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그 램을 작성하세요. 풀이 function solution(n, m) { let answer = []; let tmp = Array.from({ length: m }, () => 0); function DFS(L, s) { if (L === m) { answer.push(tmp.slice()); } else { for (let i = s; i

문제 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다. N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하 시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. 풀이 function solution(n, f) { let answer, flag = 0; let dy = Array.from(Array(11), () => Array(11).fill(0)); let ch = Array.from({ length: n + 1 }, ..