📌 동적 계획법(DP)
- 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법
◾ 동적 계획법 핵심 이론
1. 큰 문제를 작은 문제로 나눌 수 있어야 한다.
2. 작은 문제들이 반복 되어 나타나고 작은 문제들의 결과값은 항상 같아야 한다.
3. 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하여 추후 재사용할 때에는 이 DP 테이블을 이용한다.
위와 같은 방법을 메모이제이션 기법이라고 한다.
4. 동적 계획법은 톱-다운 방식과 바텀-업 방식으로 구현 할 수 있다.
◾ 피보나치 수열 공식을 통한 예시
D[N] = D[N-1] + D[N-2]
//N번째 수열 = N-1번째 수열 + N -2번째 수열- 만약 [ 1, 1, 2, 3, 5 ] 라는 수열이 있고, 6번째에 Data를 넣고 싶을 때 , 4번째와 5번째 수열을 더한 값을 넣어준다. → [ 1, 1, 2, 3, 5, 8 ]
1. 동적 계획법으로 풀 수 있는지 확인하기
- 큰 문제를 작은 문제로 나눌 수 있고 그 값이 항상 일정한지 본다.
예를들어 [ 1, 1, 2, 3, 5 ] 에서 6번째 피보나치 수열을 구하고 싶다면, 5번째, 4번째를 구하는 작은 문제로 쪼개질 수 있다.
그리고 5번째 4번째의 값이 항상 일정하다.
2. 점화식 세우기
- 점화식을 세울 때에는 논리적으로 전체 문제를 나누고 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요하다.
→ 조합 이론을 통해 가능
3. 메모이제이션 원리 이해하기
- 메모이제이션 : 부분 문제를 풀었을 때 이 문제를 DP 테이블에 저장 해 놓고 다음에 같은 문제가 나왔을 때 재계산 하지 않고 DP 테이블의 값을 이용하는 것
4. 톱-다운 구현 방식 이해하기
- 위에서 부터 문제를 파악해 내려오는 방식 주로 재귀함수 형태로 코드를 구현
- 코드의 가독성이 좋고 이해하기 편하다는 장점이 있음.
5. 바텀-업 구현 방식 이해하기
- 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장
- 주로 반복문의 형태로 구현
- 톱-다운 방식과 바텀-업 방식 중 더 안전한 방식은 바텀-업
톱-다운 방식은 재귀함수의 형태로 구현되어 있기 때문에 재귀 깊이가 깊어질 경우 런타임 에러 발생
