Memoization

https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

  • 동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법
  • DP의 핵심이 되는 기술로서 결국 메모리라는 공간 비용을 투입해 계산에 소요되는 시간 비용을 줄이는 방식
  • 피보나치 수열 계산이 대표적 예시
  • http://mrl.kr/jungol2133/
  • 위의 문제 참고
#include <iostream>
using namespace std;
#define MAX_SIZE 31

long long cache[MAX_SIZE];

long long tile(int n){
    if (n % 2 == 1)return 0;
    else{
        if (n == 0) return 1;
        if (n == 2) return 3;
        long long& ret = cache[n];
        if (ret != -1) return ret;

        ret = 3 * tile(n - 2);

        for (int i = 0; i <= n - 4; i += 2){
            ret += 2 * tile(i);
        }

        return ret;
    }
}

int main(){
    int n; cin >> n;
    for (int i = 0; i < MAX_SIZE; ++i) cache[i] = -1;
    cout << tile(n) << endl;;
    return 0;
}
  • http://tcpschool.com/cpp/cpp_cppFunction_reference
  • 이때 & 연산자는 주소 연산자가 아닌 타입을 식별하기 위해 사용하는 식별자로 사용. 즉, int&는 int형 변수에 대한 참조를 의미.
  • 이렇게 선언된 참조자는 대상 변수와 같은 메모리 위치를 참조

 

Musicals, Travel, Photo, Coding