문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 메모이제이션 (문단 편집) === 메모이제이션을 활용한 방법 === 이번에는 메모이제이션 기법을 활용해 피보나치 수열을 구해 보자. {{{#!syntax cpp #include #include using namespace std; // 피보나치 수는 94번째부터 8 byte의 자료형으로 표현할 수 없을 만큼 큰 값이다. // size_t는 표준 C++의 메모리 포인터 크기이며 32 bit 환경에서 4 byte, 64 bit 환경에서 8 byte이다. // 주로 메모리의 크기나 위치를 지정할 때 사용한다. // uint64_t는 표준 C++의 8 byte 크기의 부호 없는 정수형이다. // CPU의 연산 단위와 상관없이 고정된 크기이므로 64 bit 환경에서만 size_t와 크기가 같다. constexpr size_t array_size = 92; array memory = { 0, }; // 계산한 피보나치 수열을 메모이제이션할 고정된 크기의 배열 uint64_t fibonacci(size_t number) { uint64_t result; if(number < 2) { result = number; // 수열의 0번째와 1번째 수는 명백하므로 계산할 필요가 없다. } else { size_t index = number - 2; if(memory[index]) // 이미 계산해서 기억하고 있는 피보나치 수열이라면... { result = memory[index]; // ...메모리에서 꺼내서 돌려주자. } else // 한 번도 계산한 적이 없다면... { result = memory[index] = fibonacci(number - 1) + fibonacci(number - 2); // ...계산한 후 배열 memory에 기억해 두자 } } return result; } int main(int argc, const char *argv[]) { size_t number; cout << "본 예제는 0번째부터 93번째까지의 피보나치 수열만 계산 가능하도록 설계되었습니다\n몇 번째: "; cin >> number; cout << fibonacci(number); return 0; } }}} 혹은 {{{#!syntax cpp #include #include using namespace std; // 피보나치 수는 94번째부터 8 byte의 자료형으로 표현할 수 없을 만큼 큰 값이다. // size_t는 표준 C++의 메모리 포인터 크기이며 32 bit 환경에서 4 byte, 64 bit 환경에서 8 byte이다. // 주로 메모리의 크기나 위치를 지정할 때 사용한다. // uint64_t는 표준 C++의 8 byte 크기의 부호 없는 정수형이다. // CPU의 연산 단위와 상관없이 고정된 크기이므로 64 bit 환경에서만 size_t와 크기가 같다. constexpr size_t array_size = 94; array memory = { 0, 1, }; // 계산한 피보나치 수열을 메모이제이션할 고정된 크기의 배열 uint64_t fibonacci(size_t number) { uint64_t result; if(!number < || memory[number]) // 이미 계산해서 기억하고 있는 피보나치 수열이라면... { result = memory[number]; // ...메모리에서 꺼내서 돌려주자. } else // 한 번도 계산한 적이 없다면... { result = memory[number] = fibonacci(number - 1) + fibonacci(number - 2); // ...계산한 후 배열 memory에 기억해 두자. } return result; } int main(int argc, const char *argv[]) { size_t number; cout << "본 예제는 0번째부터 93번째까지의 피보나치 수열만 계산 가능하도록 설계되었습니다\n몇 번째: "; cin >> number; cout << fibonacci(number); return 0; } }}} 미리 구한 f(n)의 값을 메모리에 저장해서 다음에 또다시 f(n)을 계산해야 할 경우 그 과정을 생략할 수 있도록 설계한 위의 코드는 [[시간복잡도]]를 O(N)으로 줄인다. 메모리(Memo[])를 더 사용한 대가로 계산 시간을 획기적으로 단축한 것이다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기