반응형 DP2 [Coding Test][Python][백준] BOJ #17484 진우의 달 여행 문제)우주비행이 꿈이였던 진우는 음식점 '매일매일싱싱'에서 열심히 일한 결과 달 여행에 필요한 자금을 모두 마련하였다! 지구와 우주사이는 N X M 행렬로 나타낼 수 있으며 각 원소의 값은 우주선이 그 공간을 지날 때 소모되는 연료의 양이다.진우는 여행경비를 아끼기 위해 조금 특이한 우주선을 선택하였다. 진우가 선택한 우주선의 특징은 아래와 같다.1. 지구 -> 달로 가는 경우 우주선이 움직일 수 있는 방향은 아래와 같다. 2. 우주선은 전에 움직인 방향으로 움직일 수 없다. 즉, 같은 방향으로 두번 연속으로 움직일 수 없다.진우의 목표는 연료를 최대한 아끼며 지구의 어느위치에서든 출발하여 달의 어느위치든 착륙하는 것이다.최대한 돈을 아끼고 살아서 달에 도착하고 싶은 진우를 위해 달에 도달하기 위해 필요.. 2025. 2. 5. [Coding Test][Python] Dynamic Programming(DP) 개념 및 예제 ※ Dynamic Programming(DP, 동적 프로그래밍) 란?DP는 큰 문제를 작은 문제로 나누고, 작은 문제의 결과를 재사용하여 큰 문제를 해결하는 알고리즘이다. 즉, 동일한 하위 문제가 반복되는 문제에서 효율적이다. DP 주요 개념Optimal Substructure(최적 부분 구조)문제를 작은 하위 문제들로 나눌 수 있으며, 하위 문제의 최적 해를 사용하여 전체 문제의 최적 해를 구할 수 있어야한다.ex) 피보나치 수열 : $F(n) = F(n-1) + F(n-2)$Overlapping Subproblems(중복 부분 문제)동일한 하위 문제가 여러번 반복해서 나타나는 경우, 이를 저장해 재사용하면 계산량을 줄일 수 있다.ex) 피보나치 수열의 $F(5)$를 계산할 때 $F(4), F(3)$을.. 2025. 1. 27. 이전 1 다음 반응형
