Algorithm/Dynamic Programming (2) 썸네일형 리스트형 [DP] 정수 삼각형 문제 접근법 * 도형 형식으로 경로가 존재하고, 이동시 거쳐간 최댓값을 구하는 문제 = DP 유형 1) 가장 작은 문제의 정의를 점화식으로 구현한다. 코드 #include #include #include using namespace std;int solution(vector> triangle){ vector> C=triangle; int y_max= triangle.size(); for(int y=1;y [DP] N으로 표현 문제 접근법 - 주어진 숫자 N을 최소한의 횟수로 조합하여 number를 만들어야 하기 때문에, 최적 부분 구조와 중복되는 부분문제가 존재한다. 따라서 DP가 적합하다. * 최적 부분 구조란? - 중복되는 부분문제의 해결을 통해 문제의 해를 도출해 낼 수 있는 구조를 의미함. * 중복되는 부분 문제란? - 최적의 해를 찾기 위해서 반복되는 부분 문제가 존재할시, 해당 문제를 의미함. * 문제에서 얻을 수 있는 힌트 사칙 연산만 가능 -> 단순한 연산 조합을 반복하여 만들 수 있음최소 횟수를 구하는 문제 -> BFS 나 DP가 적합N을 여러번 조합하여 만들 수 있음 -> 작은 문제의 결과를 조합해 나갈 수 있음 -> DP 적용 가능. * 풀이 방법 DP 배열 dp[i]는 N을 정확히 i번 사용하여 만들 .. 이전 1 다음
