📌 02 - 돌다리 건너기(DP) 철수는 학교에 가는데 개울을 만났다. 개울은 N개의 돌로 다리를 만들어 놓았다. 철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있다. 철수가 개울을 건너는 방법은 몇가지일까? 📝 소스 코드 참고) 계단오르기 function solution(n) { let answer = 0; let dy = Array.from({ length: n + 2 }, () => 0); dy[1] = 1; dy[2] = 2; for (let i = 3; i

📌 01 - 계단오르기(동적 계획법) 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? 📝 풀이 방법(DFS, DP) DFS 알고리즘을 사용하여 문제를 풀어보았다. 정답은 훌륭하게도 잘 나온다 👍 하지만 n의 값이 커진다면...❓ 연산 횟수가 기하급수적으로 증가하게 된다. 이를 해결할 수 있는 방법으로 동적 계획법(dynamic programming, DP)이 존재한다. function solution(n) { let answer = 0; function DFS(sum) { if (sum > n)..

📌 07 - 섬나라 아일랜드(BFS 활용) N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어진다. 각 섬은 1로 표시되어 상하좌우와 대각선으로 연결되어 있으며, 0은 바다이다. 섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 문제이다. 만약 위와 같다면 섬의 개수는 총 5개이다. 섬나라 아일랜드(DFS) 문제와 같지만 이번에는 BFS 알고리즘을 이용해 풀어보았다. 영역을 탐색하는 문제의 경우에는 본인에게 편한 방법을 이용하여 풀면 될 것 같다..🤔 📝 풀이 방법 이중 for 문을 돌면서 1이 나온다면 섬을 발견한 것이므로 배열에서 해당 좌표를 0으로 재할당하고 answer++을 한다. 또한, 넓이 우선 탐색을 위해 큐에 해당 좌표를 추가한다. while 문을 돌면서 큐에서 shift 한 좌표에 대해 ..

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

📌 05 - 송아지 찾기(BFS : 상대트리탐색) 현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다. 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 문제이다. 📍 입력설명 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. 📍 출력설명 점프의 최소횟수를 구한다. 답은 1 이상이다. 문제를 해석하면 현수의 위치(출발 지점)에서 송아지의 ..

📌 04 - 이진트리 넓이우선탐색(BFS) 아래 그림과 같은 이진트리를 넓이우선탐색 하는 문제이다. 넓이우선탐색 : 1 2 3 4 5 6 7 언제 BFS를 사용하는가❓ 출발 지점에서 도착 지점까지의 최단 거리를 구할 때 노드 1이 출발 지점이므로 큐에 1을 추가한다. 큐가 모두 비워질 때 까지 while 문을 돌며 큐에서 shift 한 노드와 근접한 노드가 7보다 작거나 같으면 큐에 추가한다. 7보다 크다면 큐에 추가하지 않고 넘어간다. function solution() { let answer = ''; let queue = []; queue.push(1); while (queue.length) { let v = queue.shift(); answer += v + ' '; for (let nv of [..

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

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