(C++) 코딩테스트 2. 자료구조(투포인터, 슬라이딩 윈도우)

참고도서 : Do it! 알고리즘 코딩테스트 C++편 . 김종관 .  이지스퍼블리싱 . 2022 

using namespace std를 사용하지 않습니다.

---

투 포인터

2개의 포인터로 알고리즘의 시간 복잡도를 최적화 하는 것을 말한다.

2018번: 수들의 합 5 (acmicpc.net)

2018번: 수들의 합 5

 

연속된 자연수들의 합으로 나타낼 수 있는가? 예를 들어 15는  7 + 8 혹은 1 + 2 + 3 + 4 + 5 이런식으로 나타낼 수 있는가? 있다면 몇가지를 가지는가? 에 대한 문제

책에서 언급해주는 코딩테스트의 팁은 시간제한이 2초이고, 최댓값이 10000000이라면 O(nlogn)의 시간복잡도는 안되니, O(n)의 시간복잡도를 사용하는 알고리즘을 생각해내어야한다고 합니다.

이전의 문제까지는 어떻게 접근할지 감이 잡혔는데, 이 문제는 감이 잡히질 않는군요.. 브루트포스 알고리즘을 사용해서 무식하게 풀이하는 방법밖에 생각이 들지않습니다.

근데, 자세히보니 그냥 브루트포스 알고리즘 같은 느낌이긴합니다. 뭔가 어렵게 설명이 되어있지만 그림으로 설명하면 이겁니다.

만약에 15라는 숫자가 있을때, 그림판을 보면서 가봅시다

1부터 시작을 합니다. Start 부분은 1을 가리키고 있고 end가 1 2 3 4 5를 순서대로 가리킵니다. 5까지 더하면 15가 됩니다. 그러면 count를 1더해야합니다. 

그러면 start가 2를 가리킵니다. 2 3 4 5 6 을 했을때 15를 넘어가니 start가 3을 가리킵니다.

이런식으로 알고리즘을 작성해나가면 풀립니다.  또한 이 문제는 따로 1~15까지 저장할 메모리를 할당하지 않아도 된다.

 

다음처럼 코드를 작성할 수 있습니다.

#include<iostream>

int main() {
	int t; std::cin >> t;
	int start = 1;
	int end = 1;
	int sum = 0;
	int count = 0;

	for (int i = 0; i <= t; i++) {
		while (true) {
			sum += end;
			end++;
			if (sum > t) {
				sum = 0;
				start++;
				end = start;
				break;
			}
			else if (sum == t) {
				sum = 0;
				count++;
				start++;
				end = start;
				break;
			}
		}
	}
	std::cout << count;
}

실행결과는 잘 나온다

 

다음문제로 넘어갑니다.

1940번: 주몽 (acmicpc.net)

1940번: 주몽

문제가 뭔소리를 하는건지..

그러니까 첫째줄에 총 재료의 수를 표시하고, 두 번째 줄에 값을 세번째 적힌 숫자들을 조합해서 만든다는거 아닌가 싶은데

우선 벡터로 저장을 하고나서,start와 end로 찾으면 될 것 같다는 생각

아.. 중요한걸 빼먹었는데, 2개의 재료만 사용한다.. 뭐 이러면 문제는 쉽게 풀릴 듯.

그러면 정렬을 하고 맨앞에 숫자를 start로 놓고, 맨뒤의 숫자를 end로 놓고 계속 비교해나가면 될 것 같다는 생각.

#include<iostream>
#include<vector>
#include<algorithm>

int main() {
	std::vector<int> v;
	int N; std::cin >> N;
	int M; std::cin >> M;

	int temp;
	while (N--) {
		std::cin >> temp;
		v.push_back(temp);
	}
	sort(v.begin(), v.end());

	int count = 0;
	for (int start = 0; start < v.size()-1; start++) {
		int end = v.size() - 1;
		while (true) {
			if (v[start] + v[end] == M) {
				count++;
				break;
			}
			else{
				end--;
				if (start == end) {
					break;
				}
			}
		}
	}

	std::cout << count;
}

아무래도 작은수와 큰수를 더하는 것이 시간면에서는 빠를 것이다. 그러니 정렬을 하고 나서 처음과 끝을 더하는 식으로 더하는게 빠를 것이라 생각했다.

 

이 다음의 골드문제는 나중을 위해 넘기도록 하겠다. 우선은 실버문제를 다 풀어보고 건들일 생각..

 

 

슬라이딩 윈도우 

슬라이딩 윈도우는 위에서 언급한 투포인터와 같은 원리라고 합니다. 

12891번: DNA 비밀번호 (acmicpc.net)

12891번: DNA 비밀번호

문제가 너무 길어요...

DNA는 A, C,G, T인 문자열로 구성이 되어 있다. 근데, 민호가 이걸로 비밀번호를 만들 생각을 했는데, AAAA같은거 너무 보안에 취약하니까 ACGT가 몇개이상 등장해야하는지를 제시한다고 했다.

그래서 문자열 길이 알려주고, 부분문자열의 길이를 알려준다. 

부분문자열은 문자열에서 뚝 때는거라 A가 몇개있고 C가 몇개있고는 중요하지 않은거 같다. 

그러면  AAACCTGCCAA 이런상태에서 그냥 4개씩 순서대로 계속 때서 보는거 같은데 그래서 슬라이딩 윈도우라는 표현을 쓰는거 같다. 바로 문제를 풀어보도록 하자

#include<iostream>

int main() {
	std::string inputstr;
	int strlength; std::cin >> strlength;
	int sublength; std::cin >> sublength;
	std::cin >> inputstr;

	int DNA_A, DNA_C, DNA_G, DNA_T;
	std::cin >> DNA_A >> DNA_C >> DNA_G >> DNA_T;

	int DNA_A_temp=0, DNA_C_temp=0, DNA_G_temp=0, DNA_T_temp=0;
	int count = 0;
		
	for (int i = 0; i <= strlength - sublength; i++) {
		for (int j = 0; j < sublength; j++) {
			if (inputstr[i + j] == 'A')
				DNA_A_temp++;
			else if (inputstr[i + j] == 'G')
				DNA_G_temp++;
			else if (inputstr[i + j] == 'C')
				DNA_C_temp++;
			else if (inputstr[i + j] == 'T')
				DNA_T_temp++;
		}

		if (DNA_A_temp >= DNA_A && DNA_G_temp >= DNA_G && DNA_C_temp >= DNA_C && DNA_T_temp >= DNA_T)
			count++;

		DNA_A_temp = 0; DNA_G_temp = 0; DNA_C_temp = 0; DNA_T_temp = 0;
	}

	std::cout << count;
}

흐음.. 일단 시간초과가 나왔다.

이렇게 푸는게 아니라는 것 같다. 슬라이딩 윈도우에서는 하나의 영역에서 새롭게 추가되는 친구와 빠지는 친구로 관리를 해야한다고 합니다. 그러면 매순간 모든 경우를 계산하는 것이 아닙니다.

#include<iostream>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::string inputstr;
	int strlength; std::cin >> strlength;
	int sublength; std::cin >> sublength;
	std::cin >> inputstr;

	int DNA_A, DNA_C, DNA_G, DNA_T;
	std::cin >> DNA_A >> DNA_C >> DNA_G >> DNA_T;

	int DNA_A_temp=0, DNA_C_temp=0, DNA_G_temp=0, DNA_T_temp=0;
	int count = 0;

	// 첫 번째 슬라이딩 윈도우 제작 및 판단까지
	for (int i = 0; i < sublength; i++) {
		if (inputstr[i] == 'A')
			DNA_A_temp++;
		else if (inputstr[i] == 'G')
			DNA_G_temp++;
		else if (inputstr[i] == 'C')
			DNA_C_temp++;
		else if (inputstr[i] == 'T')
			DNA_T_temp++;
	}
	//std::cout << DNA_A_temp << " " << DNA_G_temp << " " << DNA_C_temp << " " << DNA_T_temp << " " << std::endl;

	if (DNA_A_temp >= DNA_A && DNA_G_temp >= DNA_G && DNA_C_temp >= DNA_C && DNA_T_temp >= DNA_T)
		count++;

	// 두번째 슬라이딩 윈도우는 첫번째 원소가 빠지고 마지막 원소가 추가된다.
	int start = -1; int end = sublength-1;

	for (int i = 1; i <= strlength - sublength; i++) {
		if (inputstr[start+i] == 'A')
			DNA_A_temp--;
		else if (inputstr[start+i] == 'G')
			DNA_G_temp--;
		else if (inputstr[start+i] == 'C')
			DNA_C_temp--;
		else if (inputstr[start+i] == 'T')
			DNA_T_temp--;

		if (inputstr[end+i] == 'A')
			DNA_A_temp++;
		else if (inputstr[end+i] == 'G')
			DNA_G_temp++;
		else if (inputstr[end+i] == 'C')
			DNA_C_temp++;
		else if (inputstr[end+i] == 'T')
			DNA_T_temp++;

		//std::cout << DNA_A_temp << " " << DNA_G_temp << " " << DNA_C_temp << " " << DNA_T_temp << " " << std::endl;

		if (DNA_A_temp >= DNA_A && DNA_G_temp >= DNA_G && DNA_C_temp >= DNA_C && DNA_T_temp >= DNA_T)
			count++;
	}


	std::cout << count;
}

다음처럼 코드를 작성하면 됩니다. 

 

즉 모든 윈도우를 지속적으로 매번 계산하는 것이 아니라, 영역에 들어온 놈을 포함시켜주고, 영역에서 나가는 놈을 빼주는게 핵심이였습니다.