DP3 프로그래머스 | Python | DP:테뷸레이션 | 등굣길 (Lv.3) https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr📌 문제 분석이 문제는 격자(Grid)에서 최단 경로 개수를 찾는 테뷸레이션(Tabulation, Bottom-Up 방식)을 사용하는 동적 계획법(DP) 문제입니다.특정 위치(집)에서 출발하여 목표 위치(학교)까지 이동하는 경우의 수를 구해야 합니다.✅ 핵심 요소:격자 이동: 오른쪽과 아래쪽으로만 이동 가능장애물 고려: 물웅덩이(puddles)가 있는 경우 해당 위치로 이동 불가MOD 연산: 결과가 매우 클 수 있으므로 1,000,000,007.. 2025. 3. 4. 프로그래머스 | Python | DP:테뷸레이션 | 거스름돈 (Lv.3) https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제는 동전으로 특정 금액을 만드는 방법의 수를 구하는 문제이며, 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있습니다.📌 문제 분석n: 거슬러 줘야 할 총 금액.money: 사용할 수 있는 동전의 종류 리스트.목표: n원을 만들 수 있는 방법의 수를 찾는 것.단, 정답이 커질 수 있으므로 1,000,000,007로 나눈 나머지를 반환해야 합니다.📌 핵심 알고리즘 - 동적 계획법(DP:테뷸레이션(Bott.. 2025. 3. 3. 동적 계획법 (Dynamic Programming: DP) 이란? 1️⃣ 동적 계획법(DP)이란?정의:동적 계획법(Dynamic Programming, DP)은 큰 문제를 여러 개의 작은 부분 문제로 나누어 그 해를 저장하면서 해결하는 방법입니다. 이를 통해 반복적인 계산을 줄이고, 문제를 효율적으로 해결할 수 있습니다.핵심 아이디어:부분 문제의 결과를 저장해서 같은 계산을 반복하지 않는 것이 핵심입니다.DP는 최적화 문제에 주로 사용되며, 주어진 문제를 최적 부분 구조와 중복되는 부분 문제로 나눌 수 있을 때 사용됩니다.2️⃣ DP가 필요한 이유는?일반적인 재귀 방식은 같은 부분 문제를 반복해서 계산하기 때문에 비효율적일 수 있어요. 동적 계획법은 이러한 중복 계산을 제거함으로써 시간 복잡도를 크게 줄일 수 있습니다.❌ 재귀만 사용하는 경우:피보나치 수열과 같은 문제.. 2025. 2. 12. 이전 1 다음
