DP3 백준 Class3 핵심 알고리즘 개념 정리 📌 들어가며백준 Class3부터는 본격적인 알고리즘 문제들이 등장해요. DP, DFS, 힙 등 핵심 알고리즘을 확실히 이해해야 문제를 풀 수 있답니다!📚 1. 다이나믹 프로그래밍 (Dynamic Programming, DP)🤔 DP가 뭐야?큰 문제를 작은 문제로 나누어 푸는 기법이에요. 한 번 계산한 결과를 저장해두고 재사용하는 게 핵심!💡 비유: 피보나치 수열을 계산한다고 생각해보세요.F(5)를 구하려면 F(4)와 F(3)이 필요하고,F(4)를 구하려면 또 F(3)과 F(2)가 필요해요.F(3)을 두 번 계산하지 말고 한 번만 계산해서 저장해두면 빠르겠죠?✅ DP를 쓸 수 있는 조건 (2가지)1️⃣ Overlapping Subproblems (중복되는 부분 문제)• 같은 작은 문제가 여러 번 반.. 2025. 9. 20. 백준 1463번 1로 만들기 (JavaScript 풀이) [백준 1463] 1로 만들기 - 동적 프로그래밍📖 동적 프로그래밍(DP) 정의: 큰 문제를 작은 문제들로 나누어 해결하는 알고리즘특징: 작은 문제들의 답을 저장해두고 재사용핵심: "큰 문제 = 작은 문제들의 조합"🔄 문제 해결 과정큰 문제: N을 1로 만들기 ↓ (나누기)작은 문제들: N/3을 1로 만들기, N/2를 1로 만들기, N-1을 1로 만들기 ↓ (조합)답: 작은 문제들의 답 중 최솟값 + 1📌 문제 요약정수 N에 세 가지 연산을 사용해서 1을 만드는 최소 연산 횟수를 구하는 문제.연산 1: 3으로 나누어떨어지면 3으로 나누기연산 2: 2로 나누어떨어지면 2로 나누기연산 3: 1 빼기입력: N (1 ≤ N ≤ 1,000,000)출력: 최소 연산 횟수출처: https://ww.. 2025. 9. 6. 백준 1003번 피보나치 함수 (JavaScript 풀이) [백준 1003] 피보나치 함수 - 동적 프로그래밍📖 동적 프로그래밍(DP)이란?정의: 중복되는 부분 문제를 한 번만 계산하고 저장해서 재사용하는 알고리즘특징: 같은 계산을 반복하지 않음 (메모이제이션)핵심: "이미 계산한 건 다시 계산하지 말자!"재귀 vs DP 비교일반 재귀: fibonacci(5) → fibonacci(4) + fibonacci(3) → fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1) → 같은 계산을 계속 반복! (비효율적)DP: fibonacci(0), fibonacci(1) 계산 → 저장 fibonacci(2) = fibonacci(.. 2025. 9. 5. 이전 1 다음
