Dynamic Programming(동적 프로그래밍)

설명:

아래의 설명은 유튜브 동빈나님의 다이나믹 프로그래밍 강의를 정리하였다. 정말 잘 설명 해주시니 다이나믹 프로그래밍이 무엇인지 잘 모른다면 꼭 확인 해보길 권한다.

다이나믹 프로그래밍(동적 프로그래밍은) 메모리를 적절히 사용하여 수행 시간의 효율성을 비약적으로 올리는 방법이다. 이미 계산 된 결과를 배열에 저장함으로 써 한번 더 수행하는 것을 방지하며 정답이 바로 나오도록 한다. 이렇게 한번 계산한 결과를 메모리 공간에 메모 하는 형식의 기법을 메모이제이션(memoization)/캐싱(caching)이라고 한다. 그렇다고 해서 메모이제이션은 다이나믹 프로그래밍에만 국한 된 것이 아닌 다른 기법에도 사용 될 수 있다는 것을 기억하자. 다이나믹 프로그래밍은 두 종류로 나뉜다:

탑 다운(Top-down): 위에서 아래로 내려온다는 뜻으로 하향식이라고도 한다. 재귀 함수를 사용하여 구현한다.
보텀 업(Bottom-up): 아래에서 위로 올라간다는 뜻으로 상향식이라고도 한다. for문을 사용하여 구현한다.

사용 조건:

최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제가 해결 가능할 때
중복되는 부분 문제(Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 해결 해야 될 시

예시:

다이나믹 프로그래밍을 설명할 때 제일 많이 드는 예시는 피보나치 수열이다. 피보나치 수열은 n번째 값이 n-1번째 값 더하기 n-2 번째 값인 수열을 뜻 한다. 다이나믹 프로그래밍이 피보나치 수열에서 사용 되는 방식은 n-1번째 값이나 n-2번째 값이 이미 계산이 한번 실행 되었을 경우 연산을 한번 더 하는 것이 아닌 배열에 저장 된 답을 불러오는 방식이다. 피보나치 수열은 보통 재귀함수를 사용하여 탑 다운 방식으로 풀지만 보텀 업 방식으로도 n번째까지 for문을 돌면서 활용 가능하다.

문제 풀이:

브론즈(Bronze):

실버(Silver):