dvpzeekke

문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한사항 가로의 길이 n은 60,000이하의 자연수 입니다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 입출력 예 n result 4 5 ..

다이나믹 프로그래밍과 메모이제이션 알고리즘을 비교해보겠습니다. 다이나믹 프로그래밍은 모든 subproblem들을 전부 구해야하는 문제에 적용하면 좋습니다. 메모이제이션은 모든 subproblem들을 전부 구해야하는 경우, stack에서 왔다갔다하는 overhead가 있기 때문입니다. 반면, 메모이제이션은 subproblem을 전부 다 계산하지 않아도 되는 문제에 적용하면 좋습니다. 이전에 계산한 결과를 다시 계산할 필요가 없기 때문입니다. 코드를 통해 비교 및 이해를 해보도록 하겠습니다. 피보나치 수열을 다이나믹 프로그래밍과 메모이제이션으로 각각 구현해보겠습니다. 먼저 다이나믹 프로그래밍 기법을 이용한 피보나치 수열 구현 방법입니다. int fibonacci(int n) { if (n < 2) { ret..