23.07.31. 풀었던 문제들 복기

백준 2252. 줄 세우기

 topological sort 문제. 처음에는 어떻게 풀지.. 생각했는데, 문제가 topological sort임을 깨달았다. 예전에 포스팅도 했었는데...

 일단 topological sort의 핵심은, incoming edge가 0개인 vertex에서 연결된 모든 edge를 삭제하는 과정을 n번 반복하면 된다. 만약 n번 반복이 끝나기 전에 incoming edge가 0개인 vertex가 없다면, 어딘가에 cycle이 있다는 것이다. 또, edge를 직접 지우기에는 낭비가 심하니 incoming edge 개수 정보를 저장하고, edge를 삭제할 때 여기서 빼면 된다.

vector<vector<int>> edges; // edges[i] : src가 i인 edge array
vector<int> incoming_edge_nums; // incoming_edge_nums[i] : dest가 i인 edge 개수
queue<int> q; // incoming_edge_nums[i]가 0인 vertex들이 들어감. (다음 topological sort 대상)

void solve(){
	// input
	int N, M; cin>>N>>M;
	edges.resize(N+1);
	incoming_edge_nums.resize(N+1);
	fill(incoming_edge_nums.begin(), incoming_edge_nums.end(), 0);
	int src, dest;
	while(M--){
		cin>>src>>dest;
		edges[src].push_back(dest);
		incoming_edge_nums[dest]++;
	}

	// topological info setup
	for(int i = 1; i<=N; i++){
		if(incoming_edge_nums[i] == 0) q.push(i);
	}
	vector<int> result(N);

	// topological sort
	for(int i = 0; i<N; i++){
		if(q.empty()) return;

		int cur = q.front(); q.pop();
		result[i] = cur;
		for(int next : edges[cur]){
			if(incoming_edge_nums[next] == 0) continue;
			else{
				incoming_edge_nums[next]--;
				if(incoming_edge_nums[next] == 0) q.push(next);
			}
		}
	}

	// print result
	for(int i : result) cout<<i<<' ';
}

 

시간복잡도

 topological sort는 O(V + E)이다.

 

공간복잡도

 edges vector O(V + E), incoming_edge_nums가 O(V), queue가 worst O(V)이므로 O(V+E)이다.

 

 

 

Leetcode 712. Minimum ASCII Delete Sum for Two Strings

첫 접근

 제일 처음에는, 문제를 좀 덜 이해했던 것 같다. LCS 문제임을 눈치챘고, DP로 LCS를 구현했다. 이후 backtracking으로 LCS에 해당하는 ASCII code 합을 구하고, 전체에서 뺐다.

 그러나 WA였다. 이 경우 구한 LCS의 ASCII code 합이 최대가 아닐 수 있기 때문에 발생한 문제였다.

 

Solution - 1

 dp[i][j]를 s1의 i까지, s2의 j까지 봤을 때 답이라고 하자.

 LCS인 부분.. 겹치는 부분은 이전 값에서 더하지 않아도 되므로 LCS와 같은 방법으로 DP를 세워 풀 수 있다.

// Runtime 32 ms Beats 85.55%
// Memory 15.3 MB Beats 14.89%

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        // dp
        int len1 = s1.length(), len2 = s2.length();
        vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
        for(int i = 1; i<=len1; i++) dp[i][0] = dp[i-1][0] + s1[i-1];
        for(int j = 1; j<=len2; j++) dp[0][j] = dp[0][j-1] + s2[j-1];

        for(int i = 1; i<=len1; i++){
            for(int j = 1; j<=len2; j++){
                if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1];
                else dp[i][j] = min(dp[i-1][j] + s1[i-1], dp[i][j-1] + s2[j-1]);
            }
        }
        
        return dp[len1][len2];
    }
};

 

 

Solution - 2

 그러나 첫 번째 solution의 경우에는 떠올리기도 힘들고, 추가 계산도 있다.

 dp[i][j]를 정답이라고 두고 답을 구할 수 있다는 것은 거꾸로 생각하면 LCS의 합계를 최대로 만드는 dp를 설정할 수 있다는 것이다.

 그러면 dp[i][j]를 s1의 i, s2의 j까지 봤을 때 LCS의 합계 최댓값이라고 두고, LCS와 같이 풀면 된다.

// Runtime 26 ms Beats 88.95%
// Memory 15.1 MB Beats 68.25%

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        // dp
        int len1 = s1.length(), len2 = s2.length();
        vector<vector<int>> dp(len1+1, vector<int>(len2+1, 0));
        for(int i = 1; i<=len1; i++){
            for(int j = 1; j<=len2; j++){
                if(s1[i-1] == s2[j-1]) dp[i][j] = dp[i-1][j-1] + s1[i-1];
                else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }

        // calculate
        int answer = 0;
        for(char c : s1) answer += c;
        for(char c : s2) answer += c;

        return answer - 2*dp[len1][len2];
    }
};

 

시간복잡도

 s1 길이를 M, s2 길이를 N이라고 할 때 2중 for문이므로 O(MN)이다.

 

공간복잡도

 size MN 2차원 vector를 할당하므로 O(MN)이다.

 

후기

 너무 LCS라는 것에 얽매여 있었던 것 같다. 조금 편하게 바라보자,,