28강 다이나믹 프로그래밍 개요

수행시간 효율성을 비약적으로 향상시키는 방법이라는 점입니다

영역에 저장해 두었다가

다이나믹 프로그래밍은

동적 계획법

분야에서의 동적이란

정리 다이다믹 프로그래밍을 다른 말로 동적 계획법이라고 하는데 그대로 번역해서 그런것임

일반적인 프로그래밍 분야의 동적 이라는 의미와 차이가 있음 일반적인 프로그래밍 분야에서

동적 or 다이나믹 이라고 하는 것은 프로그램이 실행되는 도중에 라는 의미를 가지는 경우가 많습니다 정확하게 말하면 프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법

반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어임

반면에 알고리즘에서 다이나믹 프로그래밍에 사용되는

옵티멀 섭 스트럭처 라고도 하구요

가진다고 표현합니다

같은 형태의 수열인데여

특정 번째의

다른 항들간의 관계식으로 점화식을 이용해서

점화식으로

점화식으로

기작부분에 항에대한 값을 알고 있으면 이러한 값을 토대로

첫번째 항의 값이 1이고 두번째 항의 값이 1이라고 했을때

우리는 이때 이 점화식을 통해서 세번째 항의 값이 2고

그리고 네번째 항을 구할때는 이 세번째 항과 두번째 항의 값을 이용할 수 있게 되게 때문에

결과적으로 이 N이 얼마나 큰수가 된다고 하더라도 모든 피보나치 수를 다 구할 수있음

재귀함수를 이용해 특징또한

존재합니다

피보나치 수열에

이렇게 1+1 을 더해서 이 세번째 항인 2를 만드는걸 확인할수 있고

다시 이렇게 2번째 항과 3번째 항을 더해서 4번째 항인 3을 만드는걸확인할수 있습니다

그다음 항을 만드는걸

수열을

라고 표현하고요

수열에 대한

어떠한 수열에 대한 정보를

배열이나 리스트를

다이나믹 프로그래밍에서

n번째 피보나치 수를 f of (N)이라고 했을때 네번째 피보나치 수 에프오브 4를 구하는 과정은 바로 다음과 같이 트리형태로 표현 할수 있는데요

다만 이 3번째 피보나치 수 또한 마찬가지로

재귀 함수를

함수 에프오브4를 노출했을때 재귀적으로 에프오브 3을 호출하고 에프오브 2를 호출해서

이떄또 에프오브 3을 호출할때도 에프오브 2와 1을 호출한 값을 더해서

그결과가 담기도록 만들수 있습니다

재귀함수

이 재귀함수가

구현하는 것이

재귀함수가 재귀적으로 호출되지 않고

수는 각각 1이기 때문에

피보나치수를 호출할때 1이라는 값을 내보내도록

이와 같이 점화식그대로

실제 점화식과 재귀적으로 호출되는

구현 할수 있습니다

재귀함수를 이용해서 피보나치 수열을

점화식에 맞게

n에 값이

반복적으로 호출 되는것을

에프 오브 2가 여러번

이 과정에서만

이러한 지수시간 복잡도는

매우높은 수행시간을

1000이라고 두겠습니다 이때 2의 30제곱은 천을 3번 곱한 10억이 되겠죠

것을 알수가 있고요

그냥 간단히 생각해보아도 이 1000을 열번 곱한것이기 때문에 0이 30개가 되겠죠

실제로 우리의 컴퓨터가 1초에 1억번씩 연산을 처리할수 있다고 가정해도

피보나치 수

네번째 피보나치 수 를 구하고자 할때

이 작은 문제 2개를

최적 부분 구조라고 할수 있고요

점을 확인할 수 있습니다

이 두번째 피보나치 수는

피보나치 수열 문제가

다이나믹 프로그래밍을 사용할수 있습니다

메모하는

구한 메모해 놓았다가

그대로 가져올수 있도록합니다

표현하기도

메모, 테이블 아니면 dp, 그냥 d라고 설정하기도 합니다

dp. d라고

탑다운 = 하양식 (재귀함수 이용) 메모이제이션 방법 사용

결과 저장용 리스트(배열)을 dp, 테이블 이라고 부름

다이나믹 프로그래밍에 국한된 개념은 아니고

담아 놓기만 하고 다이나믹 플고그래밍을 위해서

좋을것 같습니다

사용할 수 있는 겁니다

메모이제이션

모두 0으로 초기화 할수 있도록 합니다

방식으로

그 값을 반환할수 있도록 하기 위해서

즉 이미 계산

바로 앞에있는 피보나치 수와 두번째 앞에있는 피보나치 수를 구한 값을 더해서

그값을 리스트에 기록 할수 있도록 하고 최종적으로 이 x번째 피보나치 수를 리턴

할수 있도록 하면 됩니다

그 값은 무엇인지를 기록 할수 있도록 하여 다이나믹 프로그래밍을 구현 한것을 확인할 수 있습니다

각 원소의 값이 0이도록

재귀 함수가 아니라 반복문이 사용되기 때문에 이와 같이

이 점화식에서의 시작항의 대한 값들을 먼저 초기화 할수 있도록 합니다

즉 첫번재 , 두번째 피보나치수에 값은 1이 될수 있도록

이 점화식을 그대로 기입하여

그 작은 문제들을 조합해서

구한 값은 확인했던 코드의 결과와 동일한 것을 확인할 수 있습니다

dp테이블을 초기화 하는걸

구하기 까지

하나씩 구해나가는걸

이 n번째

이 c++에서

작성 할수 있고요

보텀업 방식을 이용해서

자 이미 계산된 결과를

재귀적으로 호출하게 되면 6번째 수를 구하기 위해 5번째 를 호출 하게되고

이또한 마찬가지로 4번째를 호출 4도 마찬가지로 3번째를 호출 하게 됩니다

세번째 값이 구해지게 되고요

그 값을 반환 하기 때문에

다음과 같이 색칠된

5번째 피보나치 수를 구하기 위해서는 4, 3 번째 값을 각각 더해야 하는데

3번째를 구할때는 이미 앞서 3번재 피보나치 수에 대란 값이 구해진 뒤기 때문에 바로여기에서

이경우 피보나치 수열함수의 시간복잡도는 O(N)으로 줄어들게 됩니다

줄일수 있는 겁니다

n이 아무리 커진다 하더라도

리턴할수 있도록 만들어지기 때문에

시간은 O(N)이 될것을 기대할수 있습니다

소개와 원리

분할 정복 아이디어와 비교했을때 이러한 다이나믹 프로그래밍은 어떤

다이나믹 프로그래밍 과 분할정복은

이 작은 문제의 답을 모아서

중복되는가 혹은 중복되지 않는가

영향을 미치며 부분 문제가 중복된다는 점이 특징입니다

예를들어

반복적으로 호출 되는것을

퀵정렬에서는 한번 기준 원소 즉 피벗이

않습니다

해당 피벗을 다시 처리하는 부분문제는

피벗으로 설정한 뒤에 전체 범위에 대해서 퀵정렬을 수행하게 되면

기존 피벗값인 5가 전체 배열에

이제 이 5의 위치는 더이상 바뀌지 않습니다

각각 재귀적으로 퀵정렬을 수행하며

재귀적으로 호출 되는 과정이 모두 종료가 되었을때 전체 범위에 대해서 모두 정렬이 수행됩니다

부분 문제가

정렬등 분할정복

다이나믹 프로그램인지 파악하는것이

즉 예를 들어 완전 탐색을

소요 된다고 판단이 들면

그때 다이나믹 프로그래밍을 사용할수 있는지 고려해 보는 것이 좋습니다

가진다고 하면

그대로 사용될수 있다면

담기도록하여

방법으로 문제를 해결할수도 있습니다

프로그래밍에는

서로다른 점화식을

다이나믹 프로그래밍 문제가 출제될때는

더욱더 쉬운난이도로

그문제의 맞는 점화식을 많은 시간이 소요가 될수 있기 때문에

문제에 대해서 물어보는

익숙해 질수 있으며

실제 코딩테스트에서 좋은 결과 받으실수 있을겁니다