동적 계획법

[JavaScript/section 10] 02 - 돌다리 건너기

2022.12.19

📌 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

Algorithm/인프런(inflearn)

[JavaScript/section 10] 01 - 계단오르기

2022.12.17

📌 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)..

[JavaScript/section 10] 02 - 돌다리 건너기

[JavaScript/section 10] 01 - 계단오르기

티스토리툴바