'DFS' 태그의 글 목록

[JavaScript/section 9] 06 - 섬나라 아일랜드(DFS)

2022.11.24

📌 06 - 섬나라 아일랜드(DFS 활용) N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 문제이다. 만약 위와 같다면 섬의 개수는 총 5개이다. 📝 풀이 방법 미로 탐색 문제와 유사한 문제이므로 참고하면 좋을 듯하다. 이중 for 문을 돌면서 1이 나온다면 섬을 발견한 것이므로 배열에서 해당 좌표를 0으로 재할당하고 answer++을 한다. 해당 좌표에 대해 DFS를 돌면서 상하좌우와 대각선으로 연결된 좌표가 있는지 탐색한다. 연결된 좌표가 있다면 0으로 재 할당하고 연결된 좌표로 이동한다. 더 이상 연결된 좌표가 없다면 DFS 함수를 모두 종료하고 이중 for 문을..

Algorithm/인프런(inflearn)

[JavaScript/section 9] 03 - 미로 탐색

2022.11.20

📌 03 - 미로 탐색(DFS) 7*7 격자판 미로를 탈출하는 경로의 가짓수를 출력하는 문제이다. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7) 좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면 위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지 이다. 📝 풀이 방법 nx - 이동할 행, ny - 이동할 열 상하좌우로만 움직일 수 있으므로 움직일 수 있는 경우의 수는 4가지이다. 재귀를 돌면서 다음에 이동할 좌표가 격자판을 벗어나지 않는지 확인한 다음 이동이 가능한 통로가 맞는지 확인 해야 한다. board[nx][ny] (이동할 좌표)가 0이라면 이동이 가능한 것이므로 이동하고 이동했음을 나타내기 위해 b..

Algorithm/인프런(inflearn)

[JavaScript/section 9] 02 - 경로 탐색(인접 리스트)

2022.11.16

📌 02 - 경로 탐색(인접 리스트) 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다. 이전 문제와 같은 문제이지만 인접 행렬이 아닌 인접 리스트를 이용해보려고 한다. 정점이 적다면 인접 행렬로 풀어도 되지만 무수히 많다면 메모리 낭비, 시간 복잡도 증가와 같은 문제점이 발생한다. 💩💩 이를 해결할 수 있는 방법으로 인접 리스트를 이용하는 방식이 존재한다. v 정점(행)에서 이동 가능한 정점을 각각 배열에 추가한다. 📝 풀이 방법 v - 현재 정점, i - 배열의 인덱스, ch - 해당 정점을 지났는지 체크하는 배열 graph[v][i] - 현재 정점에서 이동할 ..

Algorithm/인프런(inflearn)

[JavaScript/section 9] 01 - 경로 탐색(인접 행렬)

2022.11.15

📌 01 - 경로 탐색(DFS-인접 행렬: 노드 개수가 적을 때) 방향 그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하세요. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지 입니다. 다음과 같이 방향 그래프가 주어지면 인접 행렬로 표현할 수 있어야 한다. v 정점(행)에서 i 정점(열)으로 가는 경로가 존재한다면 1, 존재하지 않으면 0으로 표시한다. 📝 풀이 방법 v - 현재 정점, i - 마지막으로 도달해야하는 정점 ch - 해당 정점을 지났는지 체크하는 배열 재귀를 돌면서 graph[v][i]는 1이고 ch[i]는 0이라면 v 정점에서 i 정점으로 이동할 수 있다는 것이므로 해당 정점으로 이동했음을 나타내기 위해 ch[i]..

Algorithm/인프런(inflearn)

[JavaScript/section 8] 15 - 수들의 조합

2022.11.14

📌 15 - 수들의 조합 N개의 정수가 주어지면 그 숫자들 중 K개를 뽑는 조합의 합이 임의의 정수 M의 배수인 개수는 몇 개가 있는지 출력하는 문제이다. 예를 들면 5개의 숫자 2 4 5 8 12가 주어지고, 3개를 뽑은 조합의 합이 6의 배수인 조합을 찾으면 4+8+12, 2+4+12로 2가지가 있다. 📝 풀이 방법 😵 나의 풀이 방법 if문 안에 2개의 조건을 같이 주어 L(레벨)이 k(뽑는 개수)와 같더라도 sum이 6의 배수가 아니라면 else문으로 이동한다. 이 과정에서 결과는 동일하게 나오지만 시간을 잡아먹을 수 있다.🤬 L이 k와 같다면 else 문으로 이동하는 것이 아닌 if문 내부에서 sum이 6의 배수인지를 확인하고 빠져나와야 한다. function solution(n, k, arr,..

Algorithm/인프런(inflearn)

[JavaScript/section 8] 14 - 조합 구하기

2022.11.12

📌 14 - 조합 구하기 1부터 N까지 번호가 적힌 구슬이 있다. 이 중 M개를 뽑는 방법의 수를 출력하는 문제이다. M개를 뽑는다고 했으므로 조합을 이용해야 한다. N이 4이고 M이 2인 경우를 생각해보자❗ 위 그림과 같이 L1이 정해지면 L2는 L1 + 1부터 N까지 for 문을 돌면서 정해진다. 📝 풀이 방법 s는 for문에서 초기값에 해당한다. 다음과 같이 그림으로 한번 이해하고 외우도록 하자(중요❗) L(레벨)이 m과 같다면 하나의 경우가 만들어진 것이므로 tmp를 얕은 복사(slice)하여 answer에 추가한다. function solution(n, m) { let answer = []; let tmp = Array.from({ length: m }, () => 0); function DFS..

Algorithm/인프런(inflearn)

[JavaScript/section 8] 12 - 조합의 경우 수

2022.11.08

📌 12 - 조합의 경우 수(메모이제이션) nCr = n! / (n - r)!r! 로 계산한다. 하지만 이 공식을 쓰지 않고 다음 공식을 사용하여 재귀를 이용해 조합 수를 구하는 문제이다. 입력설명 첫째 줄에 자연수 n(3

Algorithm/인프런(inflearn)

[JavaScript/section 8] 11 - 팩토리얼

2022.11.07

📌 11 - 팩토리얼(DFS) 자연수 N을 입력하면 N! 값을 출력하는 문제이다. N! = N * (N - 1) * (N - 2) * ... * 1이다. 만약 N이 5라면 5! = 5 * 4 * 3 * 2 * 1 = 120이다. 👍 풀이 방법 재귀를 돌면서 n이 1과 같다면 1을 return한다. function solution(n) { let answer; function DFS(n) { if (n === 1) return 1; else return n * DFS(n - 1); } answer = DFS(n); return answer; } console.log(solution(5));

티스토리툴바