2020/07/08 공부 - dynamic programming

 오늘은 LIS 쪽 문제를 풀었다.

 먼저 11053번. LIS의 제일 기본이 되는 문젠데, 이 문제는 n square로 풀어도 되지만 어차피 DP를 배우니까 nlogn으로 풀었다.

 다른 DP 문제와 동일하게, 일단 memoization을 위해 몇 가지 array를 만든다. 내 코드에서는 DP는 각 index별로 최대 length를 저장하는 곳, LIS_array에는 LIS를 저장하는 곳으로 두었다.

 DP[i]에는 input vector의 index i까지 LIS를 저장해 두었다고 가정하고, 새 index i+1을 볼 때는 2가지 경우의 수가 있다. 먼저 input[i+1]이 지금까지의 LIS_array의 마지막 항보다 큰 경우는 바로 LIS_array vector의 마지막에 추가하면 된다. 반면 마지막 항보다 작은 경우는 앞에서 계산한 값을 가져와야 한다. 이를 위해서 lower_bound라는 함수를 사용한다.

 lower_bound 함수는 간단하게 lower_bound(container_start, container_end, target)으로 만들며 container의 start부터 end지점까지 target값보다 '크거나 같은' 의 iterator를 return해 준다. 이게 왜 필요하냐면 LIS_array를 갱신해 주는 과정이 필요하기 떄문이다.

 만약 수열이 1 2 3 8 4 5로 주어졌다면 8까지 탐색했을 때는 LIS_array가 1 2 3 8일 것이다. 그런데 4를 탐색하면 LIS_array를 lower_bound 함수를 이용해 1 2 3 4로 갱신하겠다는 것이다. LIS_array는 실제 LIS를 담고 있는 것이 아니라 계산의 편리성을 위해 도입한 임시 저장소이기 때문에, 이렇게 해도 된다. 또한, 이 예시처럼 8이 4로 갱신된다면 어제 풀었던 '최대 부분합' 문제처럼 LIS의 중간점을 8이 아닌 4로 설정할 수 있게 된다.

 말로 풀어쓰자니 조금 난잡한데, 정확하게 이해 안 되면 그림 자료들을 조금 찾아 보는 것이 좋다. 필자는 바로 윗 문단의 내용을 1년동안 이해하지 못했었는데, 앞의 DP 개념을 조금 쌓은 호 '최대 부분합' 문제를 풀고 읽는다면 이해가 되리라 믿는다.

 아무튼, 코드는 다음과 같다.

 

int LIS(vector<int>& input, int N) {
	vector<int> DP(N + 1); // length 저장하는 곳
	vector<int> LIS_array; // LIS 저장하는 곳
	DP[0] = 0;
	LIS_array.push_back(0);
	for (int i = 1; i <= N; i++) {
		if (input[i - 1] > LIS_array.back()) {
			LIS_array.push_back(input[i - 1]);
			DP[i] = LIS_array.size()-1;
		}
		else {
			int found_index = lower_bound(LIS_array.begin(), LIS_array.end(), input[i - 1]) - LIS_array.begin();
			LIS_array[found_index] = input[i - 1];
			DP[i] = found_index;
		}
	}
	return *max_element(DP.begin(), DP.end());
}

 

 설명한 것과 같이 input[i]가 LIS_array의 마지막 항보다 크면 LIS_array에 바로 붙이고, DP[i]를 현재까지 최대 LIS 길이인 LIS_array()-1로 설정한다.
 그렇지 않다면 lower_bound 함수를 이용해 탐색한 후, LIS_array에 있는 그 원소를 방금 탐색한 input[i]로 바꾸고, DP[i]는 찾은 index로 설정해 준다. LIS_array에서 찾은 found_index라는 것 자체가 그 원소가 가지고 있는 LIS_array이기 때문이다.

 

void solve() {
	int N;
	cin >> N;
	vector<int> input(N);
	for (int i = 0; i < N; i++) {
		cin >> input[i];
	}
	cout << LIS(input, N);
}

 

 입/출력 해주면 끝.

 이 코드의 경우 nlogn이기 때문에 array size가 1,000,000인 12015번도 통과한다. 2의 20승이 대충 1,000,000이니까 총 연산 회수가 20,000,000으로 1억번도 안 되기 때문이다.



 다음, 11054번이다.

 앞에서 LIS, 뒤에서 LIS를 계산한 다음 합이 제일 커지는 부분을 보면 된다. LIS 함수는 앞과 동일하게 사용했다. 앞에서부터 LIS를 계산한 front vector, 뒤에서부터 LIS를 계산한 back vector를 이용해서 input vector의 i번째 index를 탐색했을 때 front와 back의 합이 바이토닉 수열이 될 것이다. 

 

int bitonic(vector<int>& input, int N) {
	vector<int> front = LIS(input, N);
	reverse(input.begin(), input.end());
	vector<int> back = LIS(input, N);

	int bitonic_max = -1;
	for (int i = 1; i <= N; i++) {
		bitonic_max = max(bitonic_max, front[i] + back[N - i + 1]);
	}
	return bitonic_max - 1;
}

 

 입/출력은 11053과 동일하니 패스.

​

 다음, 2565번이다.

 그렇게 안 생겼는데 이 문제도 LIS이다. 입력은 vector pair로 받는데, vector pair를 sort하면 first를 기준으로 sort되고, first가 같은 경우 second도 오름차순으로 정렬되기 떄문에 바로 sort하면 된다. 

 이렇게 first를 기준으로 sort했을 때, 그림을 보면 알겠지만 전기줄이 꼬이지 않을 조건은 second가 LIS여야만 한다는 것이다. 그러니까 그냥 sort한 후 second를 이용해 LIS를 구하고, 전체 size에서 LIS size를 빼면 된다.

 

int LIS(vector<pair<int, int>>& input, int N) {
	vector<int> DP(N + 1); // length 저장하는 곳
	vector<int> LIS_array; // LIS 저장하는 곳
	DP[0] = 0;
	LIS_array.push_back(0);
	for (int i = 1; i <= N; i++) {
		if (input[i - 1].second > LIS_array.back()) {
			LIS_array.push_back(input[i - 1].second);
			DP[i] = *max_element(DP.begin(), DP.begin() + i) + 1;
		}
		else {
			int found_index = lower_bound(LIS_array.begin(), LIS_array.end(), input[i - 1].second) - LIS_array.begin();
			LIS_array[found_index] = input[i - 1].second;
			DP[i] = found_index;
		}
	}
	return *max_element(DP.begin(), DP.end());
}

 

 입/출력하면 끝. sort를 LIS 함수에 넣었으면 더 좋지 않았을까 싶다.

 

void solve() {
	int N;
	cin >> N;
	vector<pair<int, int>> input(N);
	for (int i = 0; i < N; i++) {
		cin >> input[i].first>>input[i].second;
	}
	sort(input.begin(), input.end());
	cout << N - LIS(input, N);
}

 

​


 다음, 14002번이다. LIS의 크기가 아니라 LIS를 직접 구해보는 것이다.

 LIS를 구하는 알고리즘은 앞과 동일하다. 위 코드에서 DP[i]에 i번째 input까지 최대 LIS의 길이를 담아 두었다. 이를 이용해, DP[i]를 end부터 front까지 오면서 max LIS length가 큰 순서대로 1개씩 뽑아오면 된다. 답이 여러 개 있을 수 있지만 해당 문제는 1개만 제출하면 되기 때문에 그냥 뒤에서부터 뽑아온 것이다

 실수했던 건, end부터 front가 아닌 front부터 end까지 뽑아오도록 코드를 짰다. 이렇게 하면 1 5 2 3 4 같은 경우, DP는 1 2 2 3 4가 되어서 실제 가져오는 값이 1 5 3 4가 된다. LIS가 아니게 되는 것이다. 이를 방지하기 위해 뒤에서부터 가져와야 한다.

 

int LIS(vector<int>& input, int N) {
	vector<int> DP(N + 1); // length 저장하는 곳
	vector<int> LIS_array; // LIS 저장하는 곳
	DP[0] = 0;
	LIS_array.push_back(0);
	for (int i = 1; i <= N; i++) {
		if (input[i - 1] > LIS_array.back()) {
			LIS_array.push_back(input[i - 1]);
			DP[i] = *max_element(DP.begin(), DP.begin() + i) + 1;
		}
		else {
			int found_index = lower_bound(LIS_array.begin(), LIS_array.end(), input[i - 1]) - LIS_array.begin();
			LIS_array[found_index] = input[i - 1];
			DP[i] = found_index;
		}
	}
	int max_length = *max_element(DP.begin(), DP.end());
	cout << max_length << '\n';
	stack<int> s;

	for (int i = N; i > 0; i--) {
		if (DP[i] == max_length) {
			s.push(input[i - 1]);
			max_length--;
		}
	}
	while (!s.empty()) {
		cout << s.top() << ' ';
		s.pop();
	}
	return 0;
}

 

 LIS 구하는 부분은 다 똑같다.

 이러고 입/출력 해주면 끝.

 

void solve() {
	int N;
	cin >> N;
	vector<int> input(N);
	for (int i = 0; i < N; i++) {
		cin >> input[i];
	}
	LIS(input, N);
}

 

 그리고 오늘 마지막 문제, LCS이다.

 2개의 string에서 공통 sequence의 길이를 구하는 문제다. 이 문제는 data structure를 배울 때 배웠던 알고리즘이다. 어제 풀었던 knapsak 문제와 유사하게, row와 column에 두 string을 두고, DP[i][j]는 string A에서 i까지 탐색하고 string B에서 j까지 탐색했을 때 LCS의 길이라고 두자.

 그러면 A[i]와 B[j]가 같으면 DP[i-1][j-1]+1을, 다르다면 DP[i-1][j], DP[i][j-1] 중 큰 것을 취해주면 된다. 전자는 같아지는 character가 1개 늘었다고 볼 수 있으므로 직관적으로 받아들일 수 있다. 후자의 경우, string A와 B 중 1개를 1단계 더 탐색했는데 LCS가 늘어나지 않은 경우이므로, 위와 같은 점화식을 취한다.

 

int dynamic_programming(string A, string B) {
	vector<vector<int>> DP(A.length() + 1, vector<int>(B.length() + 1, 0));

	for (int i = 1; i <= A.length(); i++) {
		for (int j = 1; j <= B.length(); j++) {
			if (A[i-1] == B[j-1]) {
				DP[i][j] = DP[i - 1][j - 1] + 1;
			}
			else {
				DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
			}
		}
	}
	return DP[A.length()][B.length()];
}

void solve() {
	string A, B;
	cin >> A >> B;
	cout << dynamic_programming(A, B);
}

 

 이제 DP가 끝났다. 이제 greedy algorithm / math 3를 풀고 나면 감 찾는 게 대충 끝날 것이다. 그 이후부터는 진짜 써먹을 만한 알고리즘들, merge sort를 이용한 탐색(백준에는 분할 정복이라 언급되어 있다.), binary search를 풀 것이다. 분할 정복같은 경우에는 O(n)이 걸릴 만한 문제를 O(logn)으로 푸는데, 상당히 흥미롭다. binary search같은 경우도 기본적인 binary search가 아니라, 반반 쪼개서 탐색해 나가는 방식을 취해야만 하는 재밌는 문제가 많다. 그 다음에는 기본적인 graph의 내용인 BFS/DFS, shortest path, minimum spanning tree 같은 것들을 슬슬 보고 좀 더 어려운 DP같은 것들을 볼 것이다.

 이번 방학에 적어도 단계별로 풀기 끝은 봐 보고 싶다. 가능할지는 모르겠지만,,, 지금 속도라면 아슬아슬하게 가능할 것 같다.(불가능 할 것 같다는 말이다) ACM 터져버렸으니 SCPC나 UCPC나 코드잼 이런거나 좀 찾아서 나가봐야겠다.