Dynamic Programming [ 동적 계획법 ]

최근 AI프로그래밍을 듣던 중 Hill climbing 알고리즘이 나왔는데 파면 팔수록 동적계획법에 대한 얘기가 잔뜩 나와서

과제를 마무리하고 덤볐다.

 

이건 사실 지금까지 배운 연결리스트라던가 ???알고리즘과는 다르게 좀 더 general한 범위이다.

 

무슨 말이냐면 딱히 정해진 루트가 없다는 말이다.

 

그냥 상황에 따라 더 우선사항이 되는 루트를 찾아서 리턴하는건데

 

요새 잘나온 카카오맵,네이버지도 등 네비게이션 앱을 생각하면 되는데

 

길을 잘못들거나 먼 거리를갈때 이상하게 돌아가는 경우가 있는데 그건 네비가 중간에 막히는 도로가 있으니 좀 돌더라도 이 길이 더 빠르다고 느꼈기에 그렇게 알려주는것이다.

 

사실 Steepest Descent를 하면서도 neighbors값 중 목표치에 가까운 값을 채택하는걸 보고 대충 dynamic programming에 대해 감은 왔었는데 확실하게 와닿는건 없었고

 

결국 내 스스로 알아보게 되었다. (교수님이 안알려줌. 정확히는 훅 넘어감 ;)

 

문제를 검색하면 대표적으로 나오는 애는 피보나치 수열이다.

이 지긋지긋한놈을 다시보다니 재귀함수할때도 머리에 쥐가 나는줄 알았는데

이제 fractal의 개념에 대해 이해하니까 이젠 이걸 줄이란다.

 

백준 1003문제는 피보나치 수열을 동적 계획법으로 풀이하는것이다.

그래서 시간제한을 보면 0.25초다 ㅋㅋㅋ

 

일단 재귀함수의 단점을 명확히 알고 있으니 그 방법은 명백히 아닐거라 제외했고 for문을 이용해서 풀었다.

 

이땐 아직 감이 아예 없는 상태라 막 코딩했는데

 

역시나 값은 제대로 나오지만 시간 초과가 떴다.

 

그렇게 참다참다 다른이의 풀이 방법을 보니 논리 자체는 꽤 간단했다.

 

"갔던곳은 스킵"

 

파이썬 기준으로 리스트 두개를 두고 각 인데스별 값을 fibonacci의 N값으로 인식하고 채워놓고 풀면 된다.

 

쉽게 말해 fibonacci(3)의 경우

fibonacci(2) + fibonacci(1)

[fibonacci(1) + fibonacci(0)] + fibonacci(1) 

이렇게 풀리는데 현재 N은 3이니

zero[3] = zero[3-1] + zero[3-2]이며,

one[3] = one[3-1] + one[3-2]인데

 

여기까지보면 얘가 뭔 소리하나 싶은데 더욱 쉽게 풀어보자면,

fibonacci(0) = 0 (0은 1개, 1은 0개)

fibonacci(1) = 1 (0은 0개, 1은 1개)

fibonacci(2) = 1 0 ( 0은 1개, 1은 1개)

fibonacci(3) = 1 2 ( 0은 1개, 1은 2개)

 

여기서 0과 1의 개수를 일부러 적어놨는데 세로로 보자.

fibonacci의 계산법 자체가 n-1 + n-2라는 개념이 아닌가?

그럼 fibonaccl(3)이라는 가정하에, fibonacci(1)의 0과 1의 개수 + fibonacci(2)의 0과 1의 개수를 더하면 된다.

세로로 보자.

 

1은 0이 0개 1은 1개

2는 0이 1개 1이 1개

그래서 3인 경우 0은 1개 1은 2개가 된다.

 

이런식으로 n은 40으로 제한이 되었으니 값을 루프문으로 꽂아주고 그냥 찾으면 된다.

그 이후의 값 역시 그냥 조회하면 된다.

 

 

 

사실 난 기존의 방법으로 list에 pop과 append를 사용해서 풀이했었는데 시간이 기존 재귀보다는 짧지만 여전히 통과가 안되어서 쓴 방법이다.

 

문제는 대충 dynamic programming에 대한 감이 오긴 왔는데..

엄청나게 확 와닿는 느낌이 없다.

많이 풀어봐야할듯