1 3 1 5 1 1 1 1 5 3 3 5 1 5 이 문제를 보고 바로 점화식을 세워야겠다는 어떻게 하는 걸까? 점화식은 참 신기하다. 항들의 관계로 답을 풀어간다는 게 참 나에게는 아직 어렵다. 그럼에도 한번 더 풀어본다. 이 문제에서는 i번째를 골랐을 때 i-2번째의 값과 더한 값과 i-1번째 값 하나만 골랐을 때 이 둘중에 큰 것이 d[i]의 값이 되게 풀었다. 내가 생각한 점화식의 핵심은 이렇다. 가정을 최소한으로 만들어서 3가지 가정을 만든 후에 일일히 대입해보는 것이다. 그렇다면 4번쨰 가정을 공식에 대입했을 때 풀리면 점화식이다. 논리적으로 답이 도출안될 때 이렇게 풀이하면 될 것 같다. 하지만 우리는 논리적으로 구하는 연습을 해야한다. i번째까지의 최대값을 d[i]에 저장하는 것 제일 중요..

다이나믹 프로그래밍 다이나믹 프로그래밍이란 무엇일까? 나는 다이나믹 관련 문제를 계속해서 풀고 있지만, 처음부터 풀지못하고 계속 답지를 보고 풀고있다. 이게 과연 실력이 늘긴 하는걸까? 바닥공사 문제를 풀다가 도저히 이해가 가지 않아 블로그에 처음 개념부터 다시 정리해 보려고 한다. 다이나믹 프로그래밍은 보통 연산속도를 빠르게하거나 메모리공간을 최대한으로 활용하기 위해 사용하는 알고리즘이다. 흔히 이를 '점화식'이라고도 부른다. 대표적인 예시는 '피보나치 수열'이다. 피보나치 수열은 n번째 숫자를 알고 싶어할 때 n번째 숫자는 n-1번째 숫자와 n-2번째 숫자를 더한 값이되고 이러한 규칙을 따르는 수열이다. 다음은 피보나치 수열의 재귀적인 소스코드이다. def fibo(n) : if n ==1 or n=..