[ZBF] 6월 9일 코딩테스트

이 글은 네이버 블로그에 2024년 6월 8일에 올렸던 것을 그대로 옮겨온 것입니다.

동적 계획법 (Dynamic Programming)

https://school.programmers.co.kr/learn/courses/30/parts/12263

프로그래머스 스쿨 - 온라인 IT 특화 교육 전문 플랫폼 — 프로그래머스 스쿨은 IT 분야 교육 전반의 과정을 제공하는 온라인 교육 플랫폼입니다. 프로그래밍, 데이터, 인공지능 등의 학습부터 코딩 테스트, 과제 테스트 연습까지, 프로그래머스 스쿨과 함께 성장해 보세요!

동적 계획법 (Dynamic Programming)

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 해결하기 위해 간단한 부분 문제로 나누어 해결하고, 이 부분 문제의 결과를 저장하여 전체 문제의 해결에 활용하는 알고리즘 설계 기법입니다. 동적 계획법은 문제를 단계적으로 해결해 나가는 방식으로, 이전 단계에서 얻은 결과를 활용하여 다음 단계를 해결합니다. 이를 통해 중복 계산을 피하고 효율적으로 문제를 해결할 수 있습니다.

동적 계획법의 핵심 개념

중복 부분 문제(Overlapping Subproblems): 문제를 해결하는 과정에서 동일한 부분 문제가 여러 번 재사용되는 경우를 의미합니다. 이러한 중복된 부분 문제를 한 번만 계산하고, 그 결과를 저장하여 재사용합니다.
최적 부분 구조(Opitmal Substructure): 문제의 최적 해결 방법이 그 부분 문제들의 최적 해결 방법으로 구성되는 경우를 의미합니다. 즉, 전체 문제의 최적해가 부분 문제의 최적해로 구성될 수 있어야 합니다.
메모이제이션(Memoization): 이미 해결한 부분 문제의 결과를 저장해두고, 동일한 부분 문제가 다시 나타날 때 저장된 결과를 재사용하는 기법입니다. 이를 통해 불필요한 계산을 피하고 효율성을 높입니다.
탑다운(Top-Down) vs. 바텀업(Bottom-Up):

탑다운 방식: 재귀 호출과 메모이제이션을 활용하여 문제를 상위에서 하위로 쪼개며 해결하는 방식입니다.
바텀업 방식: 반복문을 사용하여 문제를 하위에서 상위로 해결하는 방식으로, 주로 테이블을 사용하여 부분 문제의 결과를 저장합니다.

피보나치 수열

피보나치 수열은 동적 계획법의 대표적인 예시입니다. 일반적인 재귀적 방식은 중복 계산이 많아 비효율적이지만, 동적 계획법을 사용하면 효율적으로 계산할 수 있습니다.

탑다운 방식 (메모이제이션)

// 피보나치 수열을 구하는 탑다운 방식
function fibonacci(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}

바텀업 방식 (반복문)

// 피보나치 수열을 구하는 바텀업 방식
function fibonacci(n) {
if (n <= 1) return n;
let dp = [0, 1];
for (let i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}