알고리즘 (10) 썸네일형 리스트형 [동적계획법] 1.외발뛰기 종만북 8장 동적계획법. 8.1. JUMPGAME https://algospot.com/judge/problem/read/JUMPGAME 동적 계획법으로 풀었다. 그래프 문제로도 접근할 수 있다고 한다. 8.1. 외발뛰기(JUMPGAME) 코드 (정답, 20ms) ...더보기 /** * @name 8.1.외발뛰기 * @ID JUMPGAME * @date 2019-08-04 * @author Sunmon */ #include #include int n, board[100][100], cache[100][100]; using namespace std; //(y,x)부터 (n-1, n-1)까지 도달할 수 있으면 1, 아니면 -0 리턴 int jump(int y, int x) { if(y >= n || x >=.. [동적계획법] 0. 동적 계획법 종만북 8장 동적계획법. Dynamic programming 동적계획법vs분할정복법 문제를 나누는 방식의 차이 동적계획법 - 점화식으로 표현 가능 → 두 번 이상 계산되는 `중복문제`를 알아낸다. - `중복문제`를 해결하는 데 동적계획법 사용. 같은 문제를 또 계산할 필요 없잖아? - 중복문제 계산값을 어디다 담아두느냐? `캐시(cache)`에. 캐시에 저장해뒀다가 문제가 같으면 계산하지 않고 값만 꺼내 쓴다. - 이렇게 결과를 저장해두었다가 재사용 하는 방법을 `메모이제이션(memoization)`이라고 부른다. - 메모이제이션을 적용하려면 `참조적 투명성(referential transparency)`가 보장되어야 함 - 참조적 투명성이란? input이 같으면 같은 output이 나오는 것! 메모이제.. 이전 1 2 다음