6. 동적 프로그래밍(Dynamic Programming)

# 소개

 

안녕하세요. 공상 개발입니다.

오늘은 동적 프로그래밍이 무엇인지 피보나치 예제를 통해 가볍게 다루어 볼 것입니다. 

동적 프로그래밍은 코딩 테스트에서 자주 언급되는 부분이기도 하고 처음 접하면 많이들 어렵다고 느낍니다.

천천히 같이 살펴봅시다. 

 

# 동적 프로그래밍 조건

 

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

동적 프로그래밍은 작은 문제를 먼저 해결하여 결과를 테이블에 저장한 후, 그 결과가 필요할 때마다 사용하여

상향식으로 해답을 구축합니다.

 

# 분할 정복 vs 동적 프로그래밍

 

 

지금까지 우리는 피보나치를 구현할 때 재귀 알고리즘으로 구현했습니다.

그 과정에서 문제를 분할하고, 부분 문제를 재귀적으로 해결한 후, 통합하는 하향식 접근 방법으로 문제를 해결했습니다. 

 

하지만 이런 접근 방식으로 문제를 해결하려 할 때 피보나치수열의 경우에는 시간 복잡도가 지수 시간이 걸립니다.

구하고자 하는 값이 커지게 되면 동작 시간이 오래 걸립니다.

그렇다 보니 좀 더 낮은 시간 복잡도로 문제를 해결하기 위해 상향식 접근 방법이 사용됩니다.

 

피보나치수열의 분할 정복 시간 복잡도는 지수 시간이지만, 동적 프로그래밍으로 구현할 시 시간 복잡도는 다차 시간입니다.  

---

어떻게 구현할까?

 

fib(0)과 fib(1)의 값을 구했다고 가정할 때, 우리는 fib(2)의 값을 구할 수 있습니다.

이때, 계산한 결과를 배열에 저장함으로써 나중에 동일한 계산을 해야 할 때는 저장된 값을 사용할 수 있습니다.

fib(2)를 구하고 저장했다면, fib(3)을 구할 때 fib(2)와 fib(1)이 필요합니다. 하지만 배열에 fib(2)와 fib(1)이 저장되어 있으므로 동일한 계산을 진행하지 않아도 됩니다. 이와 같은 과정을 통해 우리는 큰 문제의 해답을 구할 수 있습니다.

 

위의 설명들이 이해가 됐다면 아래의 소스코드의 이해는 어렵지 않다고 생각합니다.

 

피보나치 수열 상향식 구현

 

다음 시간에는 최적화 문제인 행렬 경로 문제에 대해 알아보는 시간을 가지도록 하겠습니다.

---

 

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, www.instagram.com/hong_.98/을 통해 말씀해 주시기 바랍니다.

좋은 하루 보내세요.