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

문제 N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요. 풀이 DFS function solution(board) { let answer = 0; let n = board.length; let dx = [-1, -1, 0, 1, 1, 1, 0, -1]; let dy = [0, 1, 1, 1, 0, -1, -1, -1]; function DFS(x, y) { board[x][y] = 0; for (let k = 0; k = 0 && nx < ..

문제 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아 지의 위치가 수직선 상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 풀이 function solution(s, e) { let answer = 0; let ch = Array.from({ length: 10001 }, () => 0); let dis = Array.from({ length: 10001 }, () => 0); let..

너비 우선 탐색(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++) ..