Algorithm 공부 #03 - 자료구조(투 포인터와 슬라이딩 윈도우)

 

Algorithm 공부 #03 - 자료구조(투 포인터와 슬라이딩 윈도우)

 

 

투 포인터

    ● 2개의 포인터로 알고리즘의 시간 복잡도를 최적화함

 

 

백준2018번 연속된 수들의 합

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

 

※ start_index와 end_index를 1로 초기화해주고 count도 1로 초기화(N만 고를 때의 경우의 수를 미리 더해놓기) ※

    ● 투 포인터 이동 원칙에 따라서 반복문 시행하기

        sum > N : sum = sum - start_index; start_index++;

        sum == N : end_index++; sum = sum + end_index; count++; 

        sum < N : end_index++; sum= sum + end_index;

 

#include<iostream>
using namespace std;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int start_index = 1;
	int end_index = 1;
	int sum = 1;;
	int count = 1; // N만 뽑는 경우는 제외하고 미리 더해주기

	int N;
	cin >> N;

	while (end_index != N) { // end_index가 N을 넘어가게 되면 항상 sum이 N보다 커지게 됨

		if (sum == N) { // sum == N일 때
			end_index++;
			sum = sum + end_index;
			count++;
		}

		else if (sum < N) { // sum < N일 떄
			end_index++;
			sum = sum + end_index;
		}

		else { // sum > N일 때
			sum = sum - start_index;
			start_index++;
		}

	}

	cout << count;
}

 

 

백준 1940번 주몽

https://www.acmicpc.net/problem/1940

1940번: 주몽

 

※ N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용해도 문제가 없음. ※

    ● 일반적인 정렬 알고리즘의 시간 복잡도는 O(nlogn)

    ● 자료 데이터를 배열 A[N]에 저장한 후 오름차순으로 정렬하기

    ● 투 포인터 i와 j를 양끝에 이동시킨 후 문제의 조건에 적합한 포인터 이동 원칙을 활용해 탐색을 수행하기

    ● 투 포인터 이동 원칙

        A[i] + A[j] < M : i++;

        A[i] + A[j] = M : i++; j--; count++;

        A[i] + A[j] > M : j--; 

 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	cin >> N >> M;

	vector<int>A(N, 0); // N개의 크기의 배열을 생성
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}

	sort(A.begin(), A.end()); // 정렬 알고리즘으로 벡터 정렬, 사용하기 위해서는 algorithm헤더파일 불러오기

	int count = 0;
	int i = 0; // 벡터의 좌측 끝
	int j = N - 1; // 벡터의 우측 끝

	while (i < j) { // i가 j보다 크면 의미가 없어짐

		if (A[i] + A[j] < M) // 투 포인터 이동 원칙			
			i++;

		else if (A[i] + A[j] == M) { // 투 포인터 이동 원칙
			count++;
			i++;
			j--;
		}

		else { // 투 포인터 이동 원칙
			j--;
		}
	}

	cout << count;
}

 

 

백준 1253번 좋다

https://www.acmicpc.net/problem/1253

1253번: 좋다

 

※ N이 최대 2000이므로 시간 복잡도는 최소 O(nlogn)이 되어야 하므로 투 포인터 알고리즘 사용하기 ※

    ● 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함시키면 안 됨

    ● 수를 입력받아 배열에 입력받은 후 정렬

    ● 투 포인터 i,j를 배열 A 양끝에 위치시키고 적합한 투 포인터 이동원칙을 활용, 판정이 되는 수를 K라고 지정

    ● 투 포인터 이동 원칙

        A[i] + A[j] < K : i++;

        A[i] + A[j] == K : count++(i!=K&&j!=K일 때); break;

        A[i] + A[j] > K : j--

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	vector<int>A(N, 0); // N개의 크기만큼 벡터 생성 후 0으로 초기화

	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	
	sort(A.begin(), A.end()); // 벡터 정렬, 시간 복잡도 O(nlogn)
	int result = 0;

	for (int k = 0; k < N; k++) {
		long find = A[k]; // 판정 수 정하기
		int i = 0;
		int j = N - 1;

		while (i < j) {
			
			if (A[i] + A[j] == find) { // 투 포인터 이동 원칙
				
				if (i != k && j != k) {  // 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함시키면 안 됨
					result++; // 그런 경우가 아니므로 ++
					break; // 더 이상 볼 필요가 없기 때문에 break
				}
				
				else if (i == k) { 
					i++;
				}
				
				else if (j == k) {
					j--;
				}

			}
			
			else if (A[i] + A[j] < find) { // 투 포인터 이동 원칙
				i++; 
			}
			
			else { // 투 포인터 이동 원칙
				j--;
			}
		}
	}
	cout << result;
}

 

 

 

슬라이딩 윈도우

    ● 2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘

 

 

백준 12891번 DNA 비밀번호

https://www.acmicpc.net/problem/12891

12891번: DNA 비밀번호

 

※ P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘을 사용해야 함 ※

  ● 슬라이딩 윈도우 알고리즘을 이용해서 문제 접근

  ● 배열 S와 비밀번호 체크 배열을 지정하기

  ● 윈도우에 포함된 문자로 현재 상태 배열을 만든 후에 현재 상태 배열과 비밀번호 체크 배열을 비교하여 유효성 판단

  ● 윈도우를 한 칸씩 이동하며 현재 상태 배열을 업데이트하면서 비밀번호 체크 배열과 비교하며 연산

#include<iostream>
using namespace std;

int checkArr[4]; // check배열 A,C,G,T 초기 값
int myArr[4]; // 부분 배열의 A,C,G,T 값
int check = 0; // check배열과 myArr배열의 인덱스 값이 같을 때 ++
void Add(char c); // 부분배열에서 문자 한 개 추가
void Remove(char c); // 부분배열에서 문자 한 개 삭제

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int S, P;
	cin >> S >> P;

	int result = 0; // 결과값

	string A;
	cin >> A;

	for (int i = 0; i < 4; i++) {
		cin >> checkArr[i];
		if (checkArr[i] == 0)
			check++; // 0이면 무조건 성립하므로
	}

	for (int i = 0; i < P; i++) {
		Add(A[i]); // P길이만큼 부분배열 생성
	}

	if (check == 4)
		result++;

	for (int i = P; i < S; i++) { // 크기를 유지하며 부분배열 옮기기
		int j = i - P; // 
		Add(A[i]);
		Remove(A[j]);

		if (check == 4)
			result++;
	}
	cout << result;
}

void Add(char c) {
	switch (c) {
	case 'A' :
		myArr[0]++;
		if (myArr[0] == checkArr[0])
			check++;
		break;

	case 'C':
		myArr[1]++;
		if (myArr[1] == checkArr[1])
			check++;
		break;

	case 'G':
		myArr[2]++;
		if (myArr[2] == checkArr[2])
			check++;
		break;

	case 'T':
		myArr[3]++;
		if (myArr[3] == checkArr[3])
			check++;
		break;
	}
}

void Remove(char c) {
	switch (c) {
	case 'A':		
		if (myArr[0] == checkArr[0])
			check--;
		myArr[0]--;
		break;

	case 'C':		
		if (myArr[1] == checkArr[1])
			check--;
		myArr[1]--;
		break;

	case 'G':		
		if (myArr[2] == checkArr[2])
			check++;
		myArr[2]--;
		break;

	case 'T':		
		if (myArr[3] == checkArr[3])
			check--;
		myArr[3]++;
		break;
	}
}

 

 

백준 11003번 최솟값 찾기

https://www.acmicpc.net/problem/11003

11003번: 최솟값 찾기

 

※ N과 L이 5,000,000이하 이므로 일반적으로 O(nlogn)의 시간복잡도를 가지는 정렬 알고리즘을 사용할 수 없음 ※

    ● O(n)의 시간 복잡도로 해결해야 하므로 슬라이싱 윈도우를 덱으로 구현하기

    ● 덱의 마지막 위치에서부터 now보다 큰 값은 덱에서 제거

    ● 덱의 마지막 위치에 now값 저장   

    ● 덱의 첫 번째 위치에서부터 L의 범위를 벗어난 값(now index - L <= index)을 덱에서 제거

#include<iostream>
#include<deque>
using namespace std;
typedef pair<int, int>Node; //사용자 정의형으로 pair쌍 생성(인덱스와 입력 받는 값)

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, L;
	cin >> N >> L;
	deque<Node>mydeque; // Node형의 덱 생성
	
	for (int i = 0; i < N; i++) {

		int now;
		cin >> now;

		while (mydeque.size() && mydeque.back().first > now) { // 덱의 사이즈가 0보다 크고, 덱의 맨 마지막 부분의 숫자가 now보다 크다면 덱의 마지막 부분을 삭제시켜줌
			                                                   // 값이 들어올 때마다 정렬하는 방식보다 효율적이고 시간 복잡도를 줄일 수 있음
			mydeque.pop_back();
		}
		
		mydeque.push_back(Node(now, i)); // 다 정렬 후 입력 받은 값을 덱의 마지막 위치에 삽입

		if (mydeque.front().second <= i - L) { // 덱의 첫 번째 위치에서 L의 범위를 벗어난 값(now index - L <= index)을 덱에서 제거, 덱의 마지막 위치는 이제 값이 들어왔으므로
			                                   // 덱의 첫 번째 위치에서 삭제하는 게 맞음
			mydeque.pop_front();
		}
		
		cout << mydeque.front().first << ' '; 
	}	
}