[기초] 1차원 다이나믹 / 연속과 관련된 다이나믹

1차원 다이나믹

다이나믹 프로그래밍을 진행하는데, 이 강의에서 가장 크게 와닿았던 부분은

끝에 무엇이 오느냐를 생각하는 것이다.

11726 / 11727 (2xn 타일링 문제) / 9095 (1,2,3 더하기) 문제 모두 끝에 무엇이 오느냐를 생각하는 것으로써, 점화식을 생각해 볼 수 있었다.

카드 구매하기

---

연속과 관련된 다이나믹

문제를 풀어보면서 개인적으로 top down 방식보다는 bottom up 반복문 방식이 더 어울리고 편하다고 생각하였다.

1,2,3 더하기 5

맨 처음에 들었던 강의에서의 문제들은 말 그대로 1차원 배열을 활용한 것이 었다면, 이것은 2차원 배열을 이용한 점화식을 구현할 뿐이다. 결국 본질은 같다. 끝에 무엇이 오느냐를 생각하는 것 이다.

이친수

쉬운 계단 수

점화식을 언제나, 문제에 써있는대로 바로 구할수는 없다. 조건에 맞게 점화식을 구성해야 하며, 그것은 곧 배열을 정의하는 것과 같다 고 생각하였다. cache 배열을 어떻게 선언하느냐가 풀이를 좌지우지 했다.

---

가장 긴 증가하는 부분 수열

LIS 4

LIS

연속합

결국 cache 배열을 어떻게 정의하느냐의 싸움이다. cache 를 잘 정의하고도 추가적인 배열이 필요한 경우. LIS 4 문제가 그러했다.