동적 프로그래밍 (DP) 해결 방법
Step 1 : n이 가장 작을 때부터 하나하나 그려가보면서 규칙성을 찾는다
Step 2 : 규칙성이 보이기 시작하면 일반화하고, 점화식을 구한다.
Step 3 : 탑다운 or 바텀업 중 좀 더 편한 방법으로 구현 (물론 연습할 때는 둘 다 해보기)
탑다운의 필수 요구사항, 바텀업의 필수 요구사항 꼭 숙지하기
탑 다운 필수요구사항
1. 값이 한없이 작아지는 것을 방지하기 위한 탈출조건 (n이 0이거나 1 정도에서 return 하고 끊는 조건이 필요)
2. memoization (시간 초과 방지)
3. 과거의 상태값을 불러올 때는 인덱스를 이용한 배열 직접 접근보다는 재귀함수를 이용한다. Example) dp[n-1] (X) => solve(n-1) (O)
바텀 업 필수요구사항
1. n이 가장 작을 때부터 시작하는 것이니까, 초기값을 설정한다.
2. 과거의 상태값을 불러올 때는 반복문과 인덱스를 이용한 배열 직접 접근을 이용한다. Example) dp[n-1]
'Data Structure & Algorithm' 카테고리의 다른 글
그래프 구현과 DFS 탐색하기 (C) (0) | 2020.05.29 |
---|---|
파이썬으로 연결 리스트(Linked List) 구현해보기 (0) | 2020.03.25 |
python 을 활용한 자료구조와 알고리즘 공부 - (5) (0) | 2020.03.10 |
python 을 활용한 자료구조와 알고리즘 공부 - (4) (0) | 2020.03.09 |
python 을 활용한 자료구조와 알고리즘 공부 - (3) (0) | 2020.03.05 |