서론

이번 코딩테스트 알고리즘에 들어가며,, 나를 가장 머리 아프게 하는 이것.
Dynamic Programming에 대해 적어보겠다.
사실 아직도 명확하게 알고 있는 것은 아니지만 그래도 정리할 겸 적어보려고 한다.

Dynamic?

다이내믹하다.
아마 다양한 영화, 드라마 등의 매체 속에서 정말 많이 들어봤을 법한 단어이다.

명사로는 역학, 동력학 등으로 사용되며 형용사로는 역동적인 이라는 의미가 있다.

다이내믹 프로그래밍의 해결 과정이 재귀함수처럼 계속 도는 것이 아닌 스스로 계획을 세우고 이를 해결하는 모습처럼 보이는 걸 생각하면 참으로 걸맞는 이름이다.

동적계획법 (Dynamic Programming)

동적 계획법을 사용하는 이유는 일반적인 재귀의 문제로 부터 시작된다.

재귀함수를 배울 때 거의 최초로 배우게 되는 피보나치 수열을 생각해보자.

return f(n) = f(n-1) + f(n-2) 하였을 경우.
만약 내가 f(10)을 구한다고 가정하면.

f(10)
= f(9) + f(8)
= f(8) + f(7) + f(7) + f(6)
...

으로 뻗어나가 수없이 많은 계산과정이 이루어지게 된다.

만약 전의 값을 저장하여 뻗어나갈 수 있다면?

f(10)을 구하기 위해서
f(0), f(1), f(2) ... 으로 차근차근 풀어나가면 될 것이다.

즉, O(n^2) 에서 O(n)의 빠른 속도로 바뀌게 된다.

동적계획법의 구조

동적계획법은 두가지의 경우에서 특히 빛을 발한다.

1. 최적 : 전체 문제를 해결하기 위해 문제를 쪼개고쪼개는 경우
2. 중복 : 동일한 계산이 필요할 떄, 이를 메모이제이션하는 경우

두가지 경우가 모두 해당한다면 동적계획법을 사용하는것이 정말 좋을 것이다.

그러나

압도적인 성능 효과로 인해 큰 장점으로만 보인 이 동적계획법에는 압도적인 문제가 있다.

문제가 굉장히 어렵기 때문이다.
명확한 식을 설계하는 데 너무 큰 시간과 소요가 들어간다면, 차라리 해당 문제를 푸는 것보다 다른 알고리즘 문제를 푸는게 좋을 것 같다는 생각이 들었다.

최대한 미리 문제를 많이 풀어보고 외운다면 효과적일 수도..? 있겠다는 생각 또한 들었다