자료구조 & 알고리즘

[JS] 백준 11053번 - 가장 긴 증가하는 부분 수열

✨ 문제 링크 백준 11053번 - 가장 긴 증가하는 부분 수열 해당 문제를 최장 증가 부분 수열 (LIS : Longest Increasing Subsequence)이라고 한다. 최장 증가 부분 수열도 동적 계획법(DP)으로 구한다. 사실 이 문제는 구글링해서 찾은 설명을 보고도 잘 이해가 안 돼서 며칠 묵힌 뒤에야 겨우 풀 수 있었다...🥲 ❗️자바스크립트(node.js) 로 풀었습니다. 1. 코드 const fs = require("fs"); const filePath = process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt"; const [n, arrStr] = fs.readFileSync(filePath).toString()..

[JS] 동적 계획법 (Dynamic Programming, DP)

1. Dynamic Programming 이란? 주어진 문제를 여러 개의 작은 문제로 나누어 풀고, 작은 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 방법 하위 문제를 계산한 뒤 그 해결책을 저장 → 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍! 2. 다이내믹 프로그래밍 조건 ❗️다이내믹 프로그래밍은 다음 두 가지 가정이 만족할 때 사용한다. Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다. Optimal Substructure : 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다. 3. 예제 🧩 피보나..