<Udemy 동적 프로그래밍> TIL-69

  오늘은 동적 프로그래밍에 대해서 공부했다. 동적 프로그래밍이란 문제 해결 방법 중 하나이다. 모든 문제에 사용할 수는 없지만 특정 조건들이 만족되었을때 동적 프로그래밍을 활용해서 문제를 해결하면 효율을 높일 수 있다. 동적 프로그래밍을 활용하기 위한 문제의 조건은 첫 번째는 중복되는 하위 문제가 있어야 하고, 두 번째 조건은 최적 부분 구조를 가져야 한다는 것이다. 중복되는 하위 문제란 말 그대로 똑같은 처리를 해야하는 반복되는 작은 단위의 문제들이 있어야 한다는 것이고 최적 부분 구조란 하위 문제에서의 답들이 집합이 결국 해결하고자 하는 문제의 해결 방법이 되어야 한다는 것이다. 대표적인 예로 피보나치 수열이다. 피보나치 수열을 일반 함수로 만들어 해결하고자 한다면 fib(5) = fib(4) + fib(3) = fib(3) + fib(2) + fib(2) + fib(1) = fib(2) + fib(1) + fib(2) + fib(2) + fib(1) 처럼 똑같은 처리가 계속해서 반복해서 과정을 반복해서 해결해야 하기 때문에, 동적 프로그래밍을 이용해서 fib(3)의 결과를 미리 저장해 놓고 그 다음 fib(3)을 계산할 때는 저장해 놓은 fib(3) 값을 이용해서 다시 반복 계산할 필요 없게 만들어 주는 것이다. 이 처럼 단순히 계산한 결과를 미리 저장해 놓고 이를 활용하는 방법만으로도 컴퓨터가 수행해야 할 작업량을 엄청나게 많이 줄여줄 수 있다. 우선 동적 프로그램을 활용해야 하는 상황들을 잘 숙지하는것이 중요할 것 같고 문제를 잘 분석하는 능력도 필요한 것 같다. 알고리즘을 공부하면서 새로운 효율적인 방법은 없는지, 더 창의적인 방법은 없는지를 계속해서 고민하고 생각하는 자세가 필요하다는것을 계속해서 느끼고 있다.

 

2022.08.21 - [언어 공부 및 정리/JavaScript [알고리즘 & 자료구조(Udemy강의)]] - 23 동적 프로그래밍

23 동적 프로그래밍