전체 글 (19) 썸네일형 리스트형 [ 백준 1890번 점프 ] Python 코드 (DP) 1. 문제 백준 1890번 점프 2. 풀이 백트래킹, 메모이제이션, DP을 모두 적용시킬 수 있는 아주 흥미로운 문제이다. (아물론 제약조건 때문에 DP를 적용한 코드만 통과했다.) 3가지 풀이방법 모두 완전탐색을 기반으로 한다. 다만 그 효율성을 어떻게 높였는지에 따라 알고리즘이 분류된 것일 뿐이다. 백드래킹은 가지치기 코드를 통해 유효하지 않은 상태트리(경우의 수)를 더이상 탐색하지 않는다. 메모이제이션은 탑다운 방식으로 탐색을 이어나가는 중, 중복되는 상태트리를 만나는 경우 저장된 값을 불러온다. DP는 바텀업 방식으로 탐색을 하되, 이전 탐색의 값을 기억해두었다가 적절하게 재활용하여 완전탐색을 만족시킨다. 개인적으로 백트래킹과 메모이제이션은 어느 정도 코드의 정형화가 가능하기에 상대적으로 쉬운 반.. 이전 1 ··· 4 5 6 7 다음
