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

동적 계획법(dynamic programming, DP)이란? 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 문제를 보며 예시를 들어 보겠습니다. 문제 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? 먼저 1번 계단을 오르는 방법의 수는 1가지입니다. 그리고 2번째 계단을 오르는 방법의 수는 2가지이고요 그렇다면 3번째는 어떨까요? 3번째에 다다르는 방법은 1번째에서 오던가 혹은 2번째 계단에서 오던가 2가지입니다. 그런..

문제 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를 행렬로 나타낸 그림입니다.