2-S의 dfs에 메모이제이션 기법을 사용할 수 있을까요?

작성한 질문수 7

0

안녕하세요 상목님 ㅎㅎ

해당 문제는 이미 메모이제이션이 들어간거에요. 사실 메모이제이션은 dp에서의 용어로도 쓰이지만

그냥 메모리에 저장 >> 반복수행을 제거한다. 라는 의미로도 쓰입니다.

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

이 문제의 해설코드를 보면

	for (int i = 1; i <= n; i++) {
		memset(visited, 0, sizeof(visited));
		dp[i] = dfs(i); 
		mx = max(dp[i], mx);
	} 

이런식으로 dp에다가 값을 담고 있죠? 이렇게 해당 dfs로 돌린 값을 담고 있어서 이미 메모이제이션을 쓰고 있구요.

또한,

이 문제는 "중복되는 탐색"이 일어나지 않아요.

overlapping subproblems

가 없다는 뜻입니다.

int dfs(int here) {  
	visited[here] = 1;
	int ret = 1; 
	for(int there : v[here]){
		if(visited[there]) continue;
		ret += dfs(there); 
	} 
	return ret;
}
 

앞의 코드처럼 방문한 정점은 다시 방문하지도 않으니까요.

즉, 이이상 최적화를 할 수는 없습니다.

물론 이문제는 SCC라는 알고리즘을 기반으로 풀 수 있습니다.

다만.. 어려운 개념이기 때문에 그렇게 풀 필요는 없습니다. ㅎㅎ

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.