[ALGOS STUDY] 2023-SUMMER DAY3 슬라이딩 윈도우, 투포인터, 누적합

슬라이딩 윈도우

- 개념 : 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해서 문제를 풀이하는 알고리즘

- 특징

• 1차원 배열에서 O(N*M)의 시간복잡도로 해결해야 할 일을 O(N)으로 해결할 수 있음
• 한 번 구한 값을 버리지 않고 재사용
• 구간의 넓이가 고정되어 있음.

- 문제 풀이 예시 : 백준 21921 블로그 (https://www.acmicpc.net/problem/21921)

#include <iostream>
using namespace std;

int daysum[250001];

int main()
{
	int n, x, result, max, cnt = 1, day;
	cin >> n >> x;
	cin >> day;
	daysum[0] = day;

	for (int i = 1; i < n; i++)
	{
		cin >> day;
		daysum[i] = day + daysum[i - 1];
	}

	result = daysum[x - 1];
	max = result;
	for (int i = x; i < n; i++)
	{
		result = daysum[i] - daysum[i - x];
		if (max < result)
		{
			max = result;
			cnt = 1;
		}
		else if (max == result) cnt++;
	}

	if (max == 0) cout << "SAD";
	else cout << max << "\n" << cnt;
	return 0;
}

 

투포인터

- 개념 : 1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 조작해서 원하는 값을 얻는 알고리즘

- 특징

• 1차원 배열에서 O(N*M)의 시간복잡도로 해결해야 할 일을 O(N)으로 해결할 수 있음
• 한 번 구한 값을 버리지 않고 재사용
• 구간의 넓이가 조건에 따라 유동적으로 변함.

- 문제 풀이 예시 : 백준 2003 수들의 합 2 (https://www.acmicpc.net/problem/2003)

#include <iostream>
using namespace std;

int main()
{
	int n, m, start=0, end=0, nsum, cnt=0;
	cin >> n >> m;
	int* v = new int[n];

	for (int i = 0; i < n; i++) cin >> v[i];

	nsum = v[0];
	while (start <= end && end < n)
	{
		if (nsum < m) nsum += v[++end];
		else if (nsum == m)
		{
			cnt++;
			nsum += v[++end];
		}
		else if (nsum > m)
		{
			nsum -= v[start++];

			if (start > end)
			{
				end = start;
				nsum = v[start];
			}
		}
	}

	cout << cnt;
	return 0;
}

 

누적합

- 개념 : 구간의 누적합을 저장하는 특정한 배열이 있을 때 해당 배열까지의 합을 나타내는 말

- 특징

• start에서 end까지의 구간합을 sum[end] - sum[start-1]의 식으로 O(1)로 계산 가능함.
• 인덱스 내부의 값이 음수가 되지 않도록 값을 저장할 때 0번째 요소부터가 아닌, 첫 번째 요소부터 사용

 

---

ALGOS 스터디의 경우 팀원들이 만든 자료를 바탕으로 스터디를 진행합니다. 해당 일시 자료는 제가 스터디 자료를 만들지 않았기 때문에 팀원의 자료 내 출처가 표기되었을 경우, 표기된 모든 출처를 옮겨 작성합니다. 

 

ALGOS 2023 여름방학 캠프의 경우 저는 주제 총정리 영상을 담당하였습니다. 5일동안의 주제를 간단히 정리하는 영상을 제작하였으며, 해당 글과 발표자료 제작 시 참고한 내용의 출처는 다음과 같습니다.

 

<출처>

파이썬으로 배우는 자료구조 프로그래밍 (유석종)

https://ji-musclecode.tistory.com/37

https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0

https://book.acmicpc.net/algorithm/prefix-sum