TIL] 동적 프로그래밍

알고리즘

Nerd 2021. 5. 3. 21:43

동적 프로그래밍

동적 프로그래밍은 이름부터 생소하다.

동적 프로그래밍은 다이내믹 프로그래밍이라고도 부르고

동적 계획법이라 부르기도한다.

동적 프로그래밍의 원리는 주어진 문제를 풀기 위해서

문제를 여러 개의 하위 문제로 나누어 푼 다음

그것을 결합하여 최종적인 답을 구하는 것이다.

동적 프로그래밍의 장점으로는 하위 문제의 해결을 계산한 뒤

그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우

저장된 해결책을 재활용하여 간단하게 해결하여 내려가므로

계산 횟수를 줄일 수 있다.

저장된 해결책을 재활용하는 것을 메모 이제이 션이라고 부른다.

또한 프로그램을 구현할 때에 필요한 모든 가능성을 고려해서 구현하게 되기 때문에

동적 계획법을 이용하여 항상 최적의 결과를 얻을 수 있다.

동적 프로그래밍의 단점으로는 모든 가능성에 대한 고려가 불충분할 경우 최적의 결과를 보장할 수 없다.

또한 다른 방법론에 비해 많은 메모리 공간을 요구한다.

오늘은 토이 프로젝트를 진행하고 동적 프로그래밍에 대한 공부를 해보았다

확실하게 공부가 더 필요한 부분인 것 같다.

동적 프로그래밍은 장단점이 확실한 것 같다.

우선 하위 문제의 해결을 계산한 뒤 그 해결책을 저장한다는 것은

하위 문제를 적어도 한 번씩은 해결해야한다는 뜻이고

그 한번씩 해결한 해결책을 저장해 야하기 때문에 다른 방법론에 비해

많은 메모리 공간을 요구하고 모든 가능성을 고려해서 구현하는 방식인 만큼

모든 가능성을 고려하여 구현하게 되면 최적의 결과를 얻을 수 있지만

모든 가능성에 대한 고려가 불충분할 경우 최적의 결과를 보장할 수 없다는 것은

정말 장단점이 확실하게 딱 대비돼서 나타나는 것 같다.

알고리즘에 대한 공부도 필요하단 생각에 찾아보았지만

정말로 어려운 것 같다!

하지만 어렵다고 해서 피할 순 없다!

열심히 공부해야겠다✍️!!파이팅!!