다이나믹 프로그래밍 개념 . 1

다이나믹 프로그래밍이란 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 해

수행 시간 효율성을 비약적으로 향상시키는 알고리즘이다.

 

다이나믹 프로그래밍은 동적 계획법이라고도 부른다
자료구조에서 동적 할당의 '동적' 은 '프로그램이 실행되는 도중에' 라는 뜻을 담고 있지만
알고리즘에서 다이나믹 프로그래밍의 '다이나믹' 은 별다른 의미 없이 사용된 단어이다.

 

 

 

1. 문제를 작은 문제로 쪼갤 수 있고,  2. 중복되는 문제들이 있다면  DP 를 활용할 수 있다. 

 

 

 

 

피보나치 수열은 다아나믹 프로그래밍을 활용해서 풀 수 있는 대표적인 문제이다

 

 

1) 재귀함수를 이용한 피보나치 수열

 

피보나치 수열 점화식 :  An = An-1 + An-2

재귀적으로 호출되는 부분 :  An-1 + An-2
종료조건 :  A1 =1 , A2 = 1

 

 

 

단순 재귀 함수로 피보나치 수열을 구현하면 같은 문제를 계속 중복으로 계산해서 
지수 시간 복잡도를 가지므로 입력값이 조금만 커져도 출력값이 기하급수적으로 커진다

 

 

 

 

다이나믹 프로그래밍은 2가지 조건을 만족할 때 사용해야 한다

 

 

 

 

메모이제이션 / 캐싱(Caching) : 한 번 계산한 결과를 메모리 공간에 기록해 놓는 기법

 

 

 

다이나믹 프로그래밍으로 문제를 해결할 때 쓰는 배열 이름을 보통 
cash , memo , table , dp , d 등으로 선언한다

 

탑다운 방식은 구현 과정에서 재귀함수를 사용하고 
큰 문제를 해결하기 위해 작은 문제들을 재귀적으로 호출하여 

작은 문제가 모두 해결되었을 때 큰 문제의 답을 얻을 수 있게 코드를 작성하는 방식이다
그리고 그런 과정에서 한 번 계산된 결과값을 기록하기 위해서 메모이제이션 기법을 이용한다

 

보텀업 방식은 아래서부터 작은 문제들을 해결한 뒤 먼저 계산했던 값들을 활용해서 그 다음 문제까지 
해결하는 방식이다 그래서 보텀업 방식에서는 반복문을 활용한다.

 

 

 

 

 

 

보텀업 방식 코드에서 C++ 은 long long 자료형 ,  Java 는 long 자료형을 쓰기 때문에 
50번째 피보나치 수까지만 계산함  (자료형의 표현 가능 크기 때문에)
(C++ 코드는 생략)

 

 

 

메모이제이션 / 캐싱의 강력함

 

 

 

시간 복잡도를 획기적으로 줄임 (O(2^^N)에서  O(N)으로 줄임)

 

 

 

분할정복 알고리즘 :  하나의 문제를 동일한 유형의 작은 문제들로 분할한 다음에 작은 문제에 대한 결과를 조합해서 큰 문제를 해결하는 방식의 알고리즘
분할 정복 알고리즘은 보통 재귀 함수로 구현된다는 특징이 있다.

 

다이나믹 프로그래밍고 분할 정복의 차이점은 부분 문제의 중복이 있는지 없는지 이다.