Algorithm/DP2 [Algorithm] DP-1 public class DynamicProgramming { // DP // 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 // 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산되지 않도록 한다. // 일반적으로 탑다운과 보텀업으로 구성된다. 1. 최적 부분 구조(작은 문제를 모아서 큰 문제 해결 가능), 2. 중복되는 부분 문제(동일한 작은 문제를 반복적으로 해결해야 할 때) // 위에 1, 2 조건 모두 만족하면 DP로 풀 수 있다. // 탑다운(재귀 함수), 보텀업(반복문) // 피보나치 수열을 예로 들 수 있다. // 점화식을 만들 수 있는지 확인 필요 // 피보나치 수열의 점화식 : an = an-1 + an-2, a1 = 1, a2 = 1 // .. 2022. 11. 27. [Algorithm] DP 이해하기 DP(Dynamic Programming)는 완전 탐색, DFS, BFS와 같이 수많은 경우를 따져봐야 할 때 속도가 느려지는 문제를 개선하고자 수행 시간 단축을 목적으로 만들어진 알고리즘이다. 프로그래머스의 정수 삼각형 문제를 예로 들어보자 DP 삼각형의 11이 16으로 갱신되었으므로 이제 11을 만들었던 7-3-1 조합은 고려하지 않아도 된다. 여기서 DP의 장점을 확인할 수 있다. DP 삼각형을 활용하면 세 번째 줄의 값을 구할 때 두 번째 줄의 값만 확인하고, 첫 번째 줄의 값은 확인하지 않아도 된다. 왜냐하면 두 번째 줄에는 두 번째 줄까지의 모든 조합들 중 최고의 값만 남겨놨기 때문이다. (이전의 정보를 확인할 필요가 없게 됨) 다섯 번째 줄까지의 최댓값은 30이며 이 값은 7-3-8-7-5 .. 2022. 11. 27. 이전 1 다음
