DP 너무 어렵습니다.. 계단오르기, 평범한 배낭, 내리막길 모두 혼자 풀지 못해 다른 사람들의 풀이를 참고했습니다.
점화식 세우기, DP를 어떤식으로 접근할지 등에 대해 더 풀어보면서 익숙해져봐야겠습니다.
나동빈님의 책 예제문제들, 기타 문제들 풀면서 익숙해지겠습니다.
내리막길 문제의 경우 왜 dfs로 안되는가? 하고 많은 혼란이 있었습니다.
기존 dfs에서는 방문 장소에 대한 체크를 하기 때문에 총 시간 복잡도가 O(n^2)에 그치지만
이런 문제에서는 가능한 모든 케이스를 체크하기 때문에 O(4^(n**2)) 정도로 매우 큰 시간복잡도가 나오는 완전 탐색 유형이 된다
⚫ Issue Number
⚫️ 참고 사항
DP 너무 어렵습니다.. 계단오르기, 평범한 배낭, 내리막길 모두 혼자 풀지 못해 다른 사람들의 풀이를 참고했습니다. 점화식 세우기, DP를 어떤식으로 접근할지 등에 대해 더 풀어보면서 익숙해져봐야겠습니다. 나동빈님의 책 예제문제들, 기타 문제들 풀면서 익숙해지겠습니다.
내리막길 문제의 경우 왜 dfs로 안되는가? 하고 많은 혼란이 있었습니다. 기존 dfs에서는 방문 장소에 대한 체크를 하기 때문에 총 시간 복잡도가 O(n^2)에 그치지만 이런 문제에서는 가능한 모든 케이스를 체크하기 때문에 O(4^(n**2)) 정도로 매우 큰 시간복잡도가 나오는 완전 탐색 유형이 된다