오늘의 문제

주요 개념

Dynamic programming

주요개념

1. recursion solution
2. store (memoize)
3. bottom-up

하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다.

피보나치 수열과 연관성이 있는데 피보나치 수열은 앞의 두 수를 합한 값이 그 다음 요소가 되는 것으로 예를 들어 [1, 1, 2, 3] 이렇게 1+1 = 2이고 1+2 = 3, 2+3 = 5 가 된다.

이렇게 피보나치 수열은 분할정복기법을 이용할 경우 반복되는 부분이 많아져 문제가 생긴다.

그리하야

다이나믹 프로그래밍을 사용하게 되는데 이는 다음의 가정 하에 사용할 수 있다.

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

이 과정에서 메모이제이션을 사용한다는 점에서 분할 정복과 다름.

이후 정리해야 할 개념

#메모이제이션, #recursion

풀이

더 깊게 공부해야할 개념이 많지만 시간상의 제약으로 오늘은 바로 풀이로!

오른쪽과 아래로만 움직일 수 있다는 것은 가로와 세로를 (i,j)로 정했을 때 오른쪽은 (i, j+1)이고 아래는 (i+1, j)이다.

오른쪽과 아래의 값을 비교해서 작은 값을 찾아가는 것이 포.인.트

The time complexity : O(2**N)

오늘은 시간초과로 다음번에 풀이 첨부하겠습니다.