23.04.14. 풀었둔 문제들

Leetcode 516. Longest Palindromic Subsequence

 subsequence 중 가장 긴 palindrome을 찾는 문제다. LCS를 찾는 것처럼 DP를 이용해야 한다는 것을 직관으로 알았다.

• dp[i][j]를 index i부터 index j까지 longest palindrome length라고 두자.
• base case : s[i], 길이가 1인 substring은 palindrome이다. 모든 i에 대해 dp[i][i]를 1로 초기화한다.
• dp[i][i]부터 길이를 한 칸씩 늘려가면서 탐색할 것이다. 아래 표를 참고하자. 

	0	1	2	3
0	1번째 탐색	2번째 탐색	3번째 탐색	4번째 탐색
1		1번째 탐색	2번째 탐색	3번째 탐색
2			1번째 탐색	2번째 탐색
3				1번째 탐색

• 대각선으로 탐색해 나가면 길이를 1씩 늘릴 수 있다. 이 때, dp[i][j]는 인접해 있는 dp[i+1][j]와 dp[i][j-1], 그리고 dp[i+1][j-1]에 영향을 받는다. (LCS와 아주 유사하다!)
• s[i] == s[j]면 dp[i][j] = dp[i+1][j-1] + 2. palindrome이 만들어지기 때문이다.
• 그렇지 않다면 palindrome이 만들어지지 않으므로 기존에 있던 값의 max값을 취한다. dp[i][j] = max(dp[i+1][j], dp[i][j-1])

// Runtime 124 ms Beats 69.24%
// Memory 73 MB Beats 36.29%

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.length();
        vector<vector<int>> dp(len, vector<int>(len, 0));
        
        // initialize
        for(int i = 0; i<len; i++) dp[i][i] = 1;
        
        // dp
        for(int d = 1; d<len; d++){
            for(int i = 0; i<len - d; i++){
                int j = i + d;
                if(s[i] == s[j]) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }

        return dp[0][len-1];
    }
};

 

시간복잡도

 len * len으로 이루어진 2d vector를 순회하므로 O($n^2$)이다.

 

공간복잡도

 len * len으로 이루어진 2d vector를 할당하므로 O($n^2$)이다.