그러니까
갯수라면 d["asdfnews"] = d["asdfnew"] * n["s"] +
d["asdfne"] * n["ws"] + ...
와 같이 뒤에 한글자씩 떼어 낼수 가 없습니다. 한글자씩 뗄수 있는
경우도 있고 2,3,4글자씩 atomic하게 떼어내야만 하는 경우도 있고요.
제가 예를든 사전에
a 0.01
abc 0.003
bcde 0.23
d 0.2
...
라고 들어있으니까 a 만 뗄수도 있고 abc를 동시에 뗄수도있고요.
가능한 모든 조합을 생각하면서 최종적으로 가장 확률 높은 구성을
찾으려는 거지요.
---
근무시간 중에 답글단거라 답변이 좀 대충이었던 점은 죄송함다.
원래 말하고 싶었던 것은 아래 알고리즘입니다.
짜기 귀찮아서 DP 말고 memoization으로 해결했습니다만 조금 개선하면
훨씬 더 효율적으로 만들 수 있을 겁니다.
#include <iostream>
#include <string>
#include <map>
using namespace std;
class FindMax
{
private:
map<string, double> dict;
map<string, double> memo;
public:
// FIXME: use position instead of full string!
double go(const string &str)
{
if(str == "") return 1;
map<string,double>::iterator it = memo.find(str);
if(it != memo.end()) return it->second;
double ret = 0;
// FIXME: juse trie instead of map iteration!
for(it = dict.begin();it != dict.end(); ++it) if(str.size() >= it->first.size())
{
if(str.substr(0, it->first.size()) == it->first)
{
double tmp = it->second * go(str.substr(it->first.size()));
if(tmp > ret) ret = tmp;
}
}
return memo[str] = ret;
}
void setdict(const map<string, double> &dict)
{
this->dict = dict;
memo.clear();
}
};
int main(void)
{
map<string, double> dict;
dict["ab"] = 2;
dict["cde"] = 200;
dict["abc"] = 5;
dict["de"] = 5;
FindMax mm;
mm.setdict(dict);
cout << mm.go("abcde") << endl;
return 0;
}
짜놓고 보니 중요도 값을 0이나 음수로 넣었을 때 커트해주는 걸 깜박했군요.