동적계획법 (11) 썸네일형 리스트형 [동적계획법] 3. 삼각형 위의 최대 경로 https://algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 줄로 내려가는 경로를 만들려고 합니다. 경로는 아래 줄로 내려갈 때마다 바로 아래 숫자, 혹은 오른쪽 아래 숫자로 내려갈 수 있습니다. 이 때 모든 경로 중 포함된 숫자의 최대 합을 찾는 프로그램을 작성하세요. 입력 입력의 첫 줄에는 테 algospot.com 컨셉 점화식을 만들었다. path(y,x) //(y,x)에서 시작하여 맨 아래줄까지.. [동적계획법] 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 다음