글 읽기 - map을 이용한 DP의 시간복잡도?

newdeal 4년 전 0

이 문제를 읽고 먼저 생각난 풀이는 map <string,int> cache를 통한 DP였습니다.

문제의 문자열 길이는 최대25여서 충분히 map을 사용해 메모이제이션을 할 수 있을 것 같았지만 어김없이 시간 초과가 떴습니다.

연관 배열을 통한 캐시를 구현하는 것은 map에 접근하는데 걸리는 시간과 string과 같은 컨테이너를

비교하는데 걸리는 시간이 매우 크기 때문에 계산량이 아주 작은 문제에서만 쓸 수 있다고는 알고있었지만, 25길이의 문자열도

큰 시간이 걸리는 것은 몰랐습니다. map을 이용한 DP의 대략적인 시간복잡도를 어떻게 구할까요?

이 복잡도를 구하기 어렵다면 대략 사이즈가 얼마일때 map을 사용할 수 있을까요..😢

chogahui05 4년 전 0

map이 들어간다면

찾는 데, 추가하는 데, 삭제하는 데, 걸리는 시간이 O(len * logn)의 시간이 걸린다고 생각하시면 편할 듯 싶네요.

newdeal 4년 전 0

@chogahui05

답변 감사합니다. 그렇다면 밑의 코드에서는 38번줄에 ret이 변화 할때마다 O(len * logn)의 시간이 추가로 소요되는걸까요?

만약 그렇다면 25길이의 문자열일때 이 코드의 시간복잡도는 큰폭으로 증가하지는 않을 것 같은데 시간초과가 뜬 이유는

테케가 많아서 시간초과가 뜬 것일까요?..

map <string, int> cache;

bool can_pop(string s)
{
	if (s.size() == 1)
		return false;
	for (int i = 0; i < s.size() - 1; i++)
		if (s[i] != s[i + 1])
			return false;
	return true;
}

string subS(string s, int start, int fin)
{
	string ret;
	for (int i = 0; i < s.size(); i++)
	{
		if (i >= start && i <= fin)
			continue;
		ret.push_back(s[i]);
	}
	return ret;
}

int f(string s)
{
	if (can_pop(s))
		return 1;

	int&ret = cache[s];
	if (ret != 0)
		return ret;

	ret = -1;
	for (int start = 0; start < s.size() - 1; start++)
		for (int fin = start + 1; fin < s.size(); fin++)
			if (can_pop(s.substr(start, fin - start + 1)))
				ret = max(ret, f(subS(s, start, fin)));
	return ret;
}

rookel 4년 전 0

unordered_map 써보세요

newdeal 4년 전 0

@rookel

unordered_map 또한 시간초과가 납니다😢

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

map을 이용한 DP의 시간복잡도?

newdeal 4년 전 0

chogahui05 4년 전 0

newdeal 4년 전 0

rookel 4년 전 0

newdeal 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말