동적 계획법(DP)에 대해서..

내가 가장 못하는 DP가 나왔다.

 

동적 계획법의 의의는

1. 점화식을 통해 최적화된 풀이 가능
2. Memorization을 사용하여, 답들을 미리 계산

정도로 볼 수 있다.

 

개인적으로 점화식을.. 정말 못 세우는 편이라 난이도 있는 DP문제를 많이 버거워한다.

 

DP문제 풀이의 감을 잡으면 DP만큼 쉬운 문제가 없다고들 하는데, 나는 감이 아직도 안온다;;

 

앞으로 단순 점화식만 소개하는 것이 아니라, 어떻게 그 점화식을 떠올리게 되었는지도 적을 예정이니 재미삼아 읽어보는 것도 좋을 것 같다.

 

DP를 구현하는 방법은 크게 두 가지가 있다. 재귀를 이용한 Top-Down 방식과 for문을 이용한 Bottom-Up방식이 있다.자세한 내용은 동적 계획법1의 첫번째 문제인 피보나치 문제에서 설명해보겠다.

 

아 ! 한가지 Tip을 드리자면, 가끔 문제를 풀 때 \(1,000,000,009\)같이 매우 큰 소수로 나눈 나머지를 답으로 내라는 문제들이 있다.이럴 땐, 꼭!!!! DP나 Memorization쪽을 고려해보자. 왜냐하면, 저렇게 큰 소수로 나눈 나머지가 답으로 나오는 문제들은 적어도 저 소수보다 많은 경우가 나온다는 말인데... 그 경우를 하나하나 세면 무조건 시간초과일 것이다.