동적 계획법 - 12. 폴리오미노 & 메모이제이션

문제 : 폴리오미노 (난이도 : 中)

 

https://www.algospot.com/judge/problem/read/POLY

 

 분석

일단 poly(n) = n개의 정사각형으로 만들 수 있는 세로 단조 폴리오미노의 수를 반환한다고 하자.

그러나 매개변수 n 하나로 폴리오미노의 위치를 정하기가 애매하고 어렵다.

 

따라서 1st row에 있는 정사각형 수 별로 나머지 rows의 폴리오미노 반환을 받아야 한다.

1st row의 정사각형 개수를 firsts라고 할 때, poly(n, first) 함수를 정의하자. poly 함수는  n개의 정사각형을 포함하되, 1st row에 first개의 정사각형이 들어가는 폴리오미노의 수를 반환한다.

 

1st row에 first개의 정사각형이 있고, 2nd row에 second개의 정사각형이 있다고 하자. 이때 이들을 붙일 수 있는 방법의 수는 first + second -1 이다. 이를 바탕으로 점화식을 세우면 다음과 같다.

 

poly 함수 점화식

※ 중간 중간 overflow가 발생하지 않도록 주의해야 한다!

 

 구현

const int MOD = 10000000;
int cache[101][101];
// n개의 정사각형으로 이루어졌고, 맨 위 가로줄에 first개의
// 정사각형을 포함하는 폴리오미노의 수를 반환한다.
int poly(int n, int first)
{
	//base case : n == first
	if (n == first) return 1;
	//memoization
	int& ret = cache[n][first];
	if (ret != -1) return ret;
	ret = 0;
	for (int second = 1; second <= n-first; second++)
	{
		int add = first + second - 1;
		add *= poly(n - first, second);
		add %= MOD;
		ret += add;
		ret %= MOD;
	}
	return ret;
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		memset(cache, -1, sizeof(cache));
		int n;
		cin >> n;
		int ans = 0;
		for (int i = 1; i <= n; i++)
		{
			ans = (ans + poly(n, i)) % MOD;
		}
		cout << ans << '\n';
	}
	return 0;
}

 

메모이제이션 (Memoizaiton) : cache 초기화에 대한 고찰

※ Memoizaiton의 기본 개념 :

2020/11/26 - [알고리즘 문제 해결 전략] - 동적 계획법 & 메모이제이션

동적 계획법 & 메모이제이션

 

글을 쓰고 복기하던 중 문득 필자가 이 문제에 메모이제이션을 적용하는 부분이 이상하다고 느꼈다.

이상하다고 느낀 점은 cache를 시행할 때마다 초기화해주는 부분이다.

메모이제이션의 장점은 이미 한번 계산한 값을 재활용한다는 것이다.

그래서 단일 시행 내에서만 사용하는 것이 아니라, 매시 행마다 앞서 계산한 값을 재활용하면 속도가 빨라질 것이라는 가정을 세웠다. (앞서 계산한 값들이 현재 계산한 값보다 큰 경우)

 

즉, 이 문제 같은 경우 cache를 매 시행 초기화하는 것이 아니라 딱 1번만 초기화해도 된다는 것이다.

 

그래서 위 문제로 테스트를 해봤다.

int main()
{
	high_resolution_clock::time_point t1, t2;
	duration<double> time_span;

	int c;
	cout << "매번 cache를 초기화하는 방식" << '\n';
	cin >> c;
	while (c--)
	{
		memset(cache, -1, sizeof(cache));
		int n;
		cin >> n;
		int ans = 0;
		t1 = high_resolution_clock::now();
		for (int i = 1; i <= n; i++)
		{
			ans = (ans + poly(n, i)) % MOD;
		}
		t2 = high_resolution_clock::now();
		time_span = duration_cast<duration<double>>(t2 - t1);
		cout << "답 : "<< ans << ", 소요시간 : " << time_span.count() << '\n';
	}

	cout << "한 번만 cache를 초기화하는 방식" << '\n';
	cin >> c;
	memset(cache, -1, sizeof(cache));
	while (c--)
	{
		int n;
		cin >> n;
		int ans = 0;
		t1 = high_resolution_clock::now();
		for (int i = 1; i <= n; i++)
		{
			ans = (ans + poly(n, i)) % MOD;
		}
		t2 = high_resolution_clock::now();
		time_span = duration_cast<duration<double>>(t2 - t1);
		cout << "답 : "<< ans << ", 소요시간 : " << time_span.count() << '\n';
	}
	return 0;
}

테스트 결과

생각한 대로 결괏값이 나왔다. 이로써 Memoizaiton을 적용할 때 referential transparent function 조건뿐만 아니라 추가적으로 입력하는 값들이 이 문제처럼 단순?한 경우 cache를 딱 한 번만 초기화해줘도 된다는 것을 알 수 있다. 입력단이 단순하다는 말은 입력 값에 의해 문제 환경이 바뀌지 않은 것을 말한다. 예시를 들면 다음과 같다.

2021/01/02 - [알고리즘 문제 해결 전략] - 동적 계획법 - 9. 삼각형 위의 최대 경로 개수 세기

동적 계획법 - 9. 삼각형 위의 최대 경로 개수 세기

위 문제는 입력 단에 따라 문제의 board가 달라진다. 따라서 위 문제 같은 경우에는 매 시행마다 cache 초기화를 해야 한다.

 

결론을 내자면 cache를 한 번만 초기화해도 되는 조건을 정리하자면 다음과 같다.

 

0. Referential transparent function. - (memoizaiton 기본 조건)

1. 입력 값에 의해 문제 환경이 바뀌지 않은 경우. (추가 조건)