동적계획법-메모이제이션 사용 질문드립니다..!

Question

2 x n 의 타일의 알고리즘 문제인데요.메모이제이션을 활용해 문제를 푸려고합니다.혹시, 아래처럼 푼 방식이 동적계획법 - 메모이제이션을 활용한 코드라고 볼 수 있나요?public class Solution { public int tiling(int num) { // 예외 if (num &#61;&#61; 1) return 1; int[] dp &#61; new int[num &#43; 1]; // 초기값 설정 dp[1] &#61; 1; dp[2] &#61; 2; // 점화식 기반으로 계산값 적용 for (int i &#61; 3; i <&#61; num; i&#43;&#43;) { dp[i] &#61; dp[i - 1] &#43; dp[i - 2]; } // 특정 입력값에 따른 결과 return dp[num]; } }

songline · Accepted Answer

작성하신 풀이는 Memoization은 아니고 Tabulation을 적용한 풀이입니다. 필요한 만큼 미리 값들을 계산해놓고 필요할 때 참조하는 방식을 의미하죠. Memoization은 하향식으로 풀어나가며 그 때 그 때 확인된 값들을 기록, 재사용하는 기법을 의미합니다. 위 코드를 Memoization을 이용한 풀이로 바꾸면 다음과 같습니다. (java는 익숙치 않아서 c&#43;&#43; 규격으로 작성하였습니다. 양해 바랍니다.)int memo[10000] &#61; {0, }; int tiling (num) { if (memo[num] &#61;&#61; 0) { int result &#61; 0; if (num &#61;&#61; 1) { result &#61; 1; } else if (num &#61;&#61; 2) { result &#61; 2; } else { result &#61; tiling(num-1) &#43; tiling(num-2); } memo[num] &#61; result; } return memo[num]; }

assign · Answer

점화식 자체가 이전항을 기반으로 다음항을 계산하는것이므로 대표적인 동적계획법 풀이입니다.

동적계획법-메모이제이션 사용 질문드립니다..!

2개의 답변

기타 목록