다이나믹 프로그래밍
- 작은 문제의 답이 큰 문제의 답을 계산할 때 활용
- 두 가지 풀이 방법이 있음
- 상향식 풀이: for 문 돌면서 작은 문제부터 답을 계산
- 하향식 풀이: 분할정복 형태로 문제를 쪼개면서 재귀로 구현
- 점화식을 세울 때
- 작은 문제의 답부터 생각해볼것
- 큰 문제의 답을 작은 문제 답으로 계산할 수 있는지 생각해볼것
- 메모이제이션
- 초기값 설정을 잘 해야 함 (메모리를 한칸 더 크게 잡는다던가)
노트
- 파이썬 재귀 구현은 recurssion 제한때문에 런타임 에러가 날 수 있음
(아래와 같이 recursion limit 수정)
import sys
sys.setrecursionlimit(10**6)풀이
1) 그래프 탐색 문제다
2) 최장 길이를 구하는 문제이므로, DFS 알고리즘으로 탐색하면 된다
3) DFS 는 재귀 형태로 구현 할 수 있다
문제점
1) 다음 노드로 이동하는 방향이 오른쪽이면 다음 노드에서는 왼쪽 방향으로 탐색을 못하게 막아야 한다고 생각함
2) 하지만, 문제에서 주어진 조건은 '항상 대나무가 많은 방향으로 이동' 이기 때문에, 다음 노드 입장에서 이전노드는 무조건 자기 자신보다 대나무 수가 적을 것이라서, 이전 노드로 돌아갈 일이 없음
3) 따라서, 이전 노드를 방문하지 못하게 하는 로직은 필요 없음 (노드 진입 방향 같은)
4) 탐색 문제에서 이전 노드 방문 조건 체크를 해야 하는지 확인하고 문제를 풀어야 함
