전형적인 DP문제에 대한 생각 전개 방식과 템플릿을 짜기 위해 작성하는 글.
이 글을 참고했다.
class Solution {
public:
int ans;
void bt(string& s, int pos){
if(pos >= s.size() || (pos == s.size()-1 && s[pos] != '0')){
ans++;
return;
}
if(s[pos] == '0') return;
dp(s, pos+1);
if(s[pos] == '1' || (s[pos] == '2' & s[pos+1] >= '0' && s[pos+1] <= '6')){
dp(s, pos+2);
}
}
int numDecodings(string s) {
ans = 0;
bt(s, 0);
return ans;
}
};처음에 작성했던 코드.
backtrack을 하면 되겠다(잘못된 생각)고 생각을 해서, backtracking을 하는 식으로 접근을 했는데, 조건설정에서 잘못 생각한 부분이 있어서 애를 좀 먹었었다. 다음부터는 조건을 조금 더 생각하고서 코드를 작성하는것이 필요해보인다.
각설하고,
내가 주로 사용하는 Backtracking에 대한 기본 템플릿은 다음과 같다.
// Return value는 void
void backtracking(현재 상태, 현재 위치등..){
if(Base Case){
// Count the answer
return
}
for(...){
// Call another backtracking function recursively.
}
}위 문제에 이 방식을 사용했을 경우, Time complexity가 O(2^n)이 된다.
각각 char에 대하여 Backtracking function을 재귀적으로 2번씩 호출할 수 있으므로... 따라서 비교적 적은 input이 주어진다고 한들 TLE가 날 수 있다.
이때 거의 모든 Backtracking을 DP문제로 전환할 수 있는 단서인, 반복된 subproblem에 대한 계산이 이루어지고 있다는 점을 발견하면, 간단하게 DP구조로 변경을 해 볼 수 있다.
DP에는 Memoization과 Tabulation이 있는데, Backtracking -> DP로 우선적으로 변경하게 된다면 Memoization 방식을 사용할 가능성이 높다.
Memoization에 대한 기본 템플릿은 다음과 같다.
// Return value는 최종 return 해야하는 type
vector<int> table(n, -1); <- Dp table을 전역지정하거나, 함수 파라미터에 참조형 변수로 넣어줌.
int memoization(현재 위치(pos)등, dp table (or not)){
// 이미 계산된 값이면,
if(table[pos] != -1){
// 해당 값 그대로 return
return table[pos];
}
// 그렇지 않은 경우
int ret = //something from another dp function ex ) memoi(po1+1);
// 마지막으로 그 계산된 값을 현재 자리에 넣으면서 return
return table[pos] = ret;
}신경써야하는 점
1. Backtracking에서는 base case를 함수 안에서만 다뤘는데, Memoization을 할 때는, dp table 자체에 base case에 대한 값을 넣어두어야 함.
2. 선 계산 -> 후 대입이 이루어 진다는 점.
3. return value.
물론 어떤 문제냐에 따라서 세부적인 구현이나 return 조건이 달라질 수는 있는데, 전체적인 틀은 위와같이 유지한다는 점이 중요하다.
그렇게 풀이한 풀이는 다음과 같다.
class Solution {
public:
// table 전역 지정
vector<int> dp;
int solve(string& s, int pos){
// 이미 계산했으면 그 값을 return
if(dp[pos] != -1) return dp[pos];
// 또 다른 base case. 이렇게 두지 않고, int res = 0 으로 두고, 마지막에 한번에 return 처리해도 가능.
if(s[pos] == '0') return dp[pos] = 0;;
// 다음 memoization으로부터 가져온 값.
int res = solve(s, pos+1);
// 추가해주는 조건.
if(pos<s.size()-1 && (s[pos] == '1' || (s[pos] == '2' & s[pos+1] >= '0' && s[pos+1] <= '6'))){
res += solve(s, pos+2);
}
// table에 넣으면서 return
return dp[pos] = res;
}
int numDecodings(string s) {
int ans = 0;
// 왜 size가 n+1이여야 하는가? 에 대한 생각을 먼저 해보면, size가 n인 경우에도 가능하긴 한데, 그러면 nth index에 대한 초기화를 조건에 따라서 해주어야 하기 때문에, 중복된 코드를 사용하게 됨.. 그래서 모든것을 backtracking안에서 해결하기 위함임.
dp = vector<int>(s.size()+1, -1);
dp[s.size()] = 1;
solve(s, 0);
return s.size() ? solve(s, 0) : 0;
}
};이렇게 작성을 할 수 있다.
Memoization보다 Tabulation이 더 빠르다는것을 이용하면, 재귀 없이 for문을 통해서도 만들 수 있는데,
int numDecodings(string s) {
int n = s.size();
vector<int> dp(n+1);
dp[n] = 1;
for(int i=n-1;i>=0;i--) {
if(s[i]=='0') dp[i]=0;
else {
dp[i] = dp[i+1];
if(i<n-1 && (s[i]=='1'||s[i]=='2'&&s[i+1]<'7')) dp[i]+=dp[i+2];
}
}
return s.empty()? 0 : dp[0];
}사실상 Memoization에서 복사 붙여넣기를 통해서 만들 수 있는 코드이긴 하지만, backtracking에서 이곳으로 넘어오기는 쉽지않아 보인다.
아무튼 이 3단계에 대해서 매번 고민하면서 풀면 좋을듯.
