알고리즘 스터디 1주차 - 투 포인터 (two pointer)

이건 동빈나 prefix sum보다가 우연히 보게 됐는데 이번주 스터디 숙제에도 껴있었다.

youtu.be/rI8NRQsAS_s

이건 쉬워서? 맞나? 바로 이해함 오홍 

단조 증가 / 감소해야지 투 포인터를 쓸 수 있는 것 같다. 그래야 특정 값이 나오면 end를 멈춰버리고 start를 갱신!

 

백준 2003번 수들의 합2 (www.acmicpc.net/problem/2003) 

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

vector<int> arr;

int main() {
	int n, m , number;
	cin >> n >> m;
	arr.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &number);
		arr[i] = arr[i - 1] + number;
	}
	int count = 0;
	for (int start = 1; start <= n; start++) {
		for (int end = start; end <= n; end++) {
			if (arr[end] - arr[start - 1] == m) {
				count++;
				break;
			}
			else if (arr[end] - arr[start - 1] > m)break;
		}
	}
	cout << count;
}

누적합을 배열에 저장하는데 특정 배열값이 내가 구하는 값과 같다면 하나 카운팅해주고 멈춘다.

만약 내가 구하는 값을 최초로 넘어갔다면 어차피 그 이후의 값은 내가 구하는 값보다 더욱 커질테니 여기서도 그냥 멈춰준다. 

 

백준 부분합 1806번(www.acmicpc.net/problem/1806)

#include<iostream>
#include<iostream>
#include<vector>
using namespace std;
vector<int> arr;
int main() {
	int n, m, number ,temp ;
	cin >> n >> m;
	arr.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &number);
		arr[i] = arr[i - 1] + number;
	}
	int count = 0;
	int min_temp = n;
	if (arr[n] < m) cout << 0;
	else {
		for (int start = 1; start <= n; start++) {
			for (int end = start; end <= n; end++) {
				if (arr[end] - arr[start - 1] >= m) {
					temp = end - start + 1;
					if (temp < min_temp) min_temp = temp;
					break;
				}
			}
		}
		cout << min_temp;
	}
}

특정 값 이상의 구간의 길이가 가장 짧은 것을 구하는 게 답이다.  

만약 맨 처음 나온 구간의 길이가 5라면 사실 그 이후 end는 끝까지가 아니라 start + 5까지만 가야된다. 

구간의 합이 특정 값 이상이 나오더라도 길이가 가장 짧은 게 아니라 의미가 없기 떄문이다. 

근데 마땅한 코드가 생각이 안나서 그냥 조건문을 쓰긴 했지만 다시 풀어보고싶다.

 

백준 1644번 소수의 연속합(www.acmicpc.net/problem/1644)

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
vector<int> arr;

//소수판정 함수
int prime(int n) {
	if (n == 2) return true;
	else {
		for (int i = 2; i <= sqrt(n)+1; i++) {
			if (n % i == 0) return false;
		}
		return true;
	}
}

int prime(int);

int main() {
	int n, size = 1;
	scanf("%d", &n);
	arr.resize(n + 1);
	if (n == 1) printf("0");
	else {
		for (int i = 2; i < n; i++) {
			if (prime(i)) { //i가 소수가 맞다면
				arr[size] = i + arr[size - 1];//소수의 누적합 저장
				if (size > 1 && arr[size] - arr[size - 2] >= n) break;
				size++;

			}
		}
		int count;
		if (prime(n)) count = 1;
		else  count = 0;

		for (int start = 1; start <= size; start++) {
			for (int end = start; end <= size; end++) {
				if (arr[end] - arr[start - 1] > n) break;
				if (arr[end] - arr[start - 1] == n) {
					count++;
					break;
				}
			}
		}
		printf("%d", count);
	}
}

소수판정 문제 엄청 오랜만이다.ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ이 문제를 풀면서 여러번 시간초과가 났는데 

내가 생각했을 때 시간초과가 났을 거라고 생각한 이유는 3가지다. 

 

1. 소수판정을 할 때는 자기보다 작은 숫자로 자신을 나눠서 소수인지 확인하는 작업을 한다. 

그때 n-1이 아니라 sqrt(n)+1까지만 진행해서 시간을 단축할 수 있다.

 

2. 주어진 숫자 n에 대해서 n보다 작은 소수들의 합으로 n을 만들 수 있냐 이게 우리가 풀어야 할 문제이다. 

굳이 소수를 n보다 작은 값들을 모두 배열에 저장할 필요 없이 두 소수의 합이 n보다 커진다면  소수를 거기까지만 구해도 된다. 어차피 우리가 하는 건 양의 정수의 '합'이기 떄문에 두 소수의 합이 n보다 크다면 뭘 더해도 어차피 n보다 클 거기 때문이다. 

 

3. 이렇게 풀게 되면 n보다 작은 소수들을 저장하는 배열의 크기가 불분명하다. n에 따라 다르기 떄문이다. 

그래서 처음에는 n만큼 resize해줬는데, 배열이 저장될 때마다 카운팅을 해서 그 크기만큼만 for문을 돌려 확인했다.