대엉코딩

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

1. 풀이방법

- N의 숫자의 범위가 큰편입니다.

- O(N^2)은 100,000,000 시간제한 0.5초에 타임리밋 걸릴 수 있습니다.

- 투포인터를 이용해 한번의 순회로 해결했습니다.

- 단, 이는 A[i]가 자연수 (음수 아님) 조건이 있기 때문에 사용할 수 있습니다.

2. 주의사항

- 문제 조건을 정확히 파악해야 합니다.

3. 나의코드

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

int N, M;
vector<long long> arr;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> M;
	long long tt;
	for (int i = 0; i < N; i++) {
		cin >> tt;
		arr.push_back(tt);
	}
	int tmpsum = arr[0];
	int resultcount = 0;
	int sp = 0;
	int ep = 0;
	while (1) {
		if (tmpsum == M) {
			resultcount++;
			tmpsum -= arr[sp];
			sp++;
			ep++;
			if (ep == N) break;
			tmpsum += arr[ep];
		}
		else if (tmpsum < M) {
			ep++;
			if (ep == N) break;
			tmpsum += arr[ep];
		}
		else if (tmpsum > M) {
			tmpsum -= arr[sp];
			sp++;
		}
	}
	cout << resultcount;
	return 0;
}

0. string

- character의 sequence 이다.

- string의 예시로서는

  -> HTML문서

  -> DNA sequence

  -> 등등....매우 많다.

- 아스키코드, binary alphabets, DNA alphabets( {A,C,G,T} )

- 보통 TEXT에서 PATTERN과 일치하는 SubString(그 위치)를 찾는 문제가 많다.

- 검색엔진, 텍스트 에디터, 생물학적 조사 등 을 할 때 주요하게 사용된다. 

1. 개요

- 가장 간단하고 naive한 방식의 알고리즘 이다.

- 텍스트의 위치 가능한 모든 자리에 PATTERN을 매치시켜 비교과정을 거친다.

- 비교과정 중 완벽하게 매치하거나 남은 텍스트의 길이보다 패턴의 길이가 더 길어질 경우 비교를 멈춘다.

2. 시간복잡도

- 워낙 간단해서 의사코드를 기재하진 않았지만 복잡도 분석을 해보면

- 텍스트의 길이 (m) 패턴의 길이 (n)  이라 하면 시간 복잡도는 O(n*m)

- m의 위치 가능한 모든 자리에서 n을 비교하기 때문에 최악의 경우 O(n*m) 이다.

- 최악의 경우 중 간단한 예시를 들어보면

 -> TEXT: AAAA........B

 -> PATTERN: AAAB

-이경우 불일치가 패턴의 맨 끝에 존재하므로 패턴을 매번 비교할 때 마다 끝문자가 나타날 때 까지 비교를 해야한다.

3. 장점 및 단점

- 장점은 알고리즘 자체가 매우 간단하다.

- 패턴이나 텍스트를 Preprocessing하는 과정이 없다.

- 알파벳의 범위가 좁을 경우 (위의 경우 처럼 a,b) 성능이 떨어진다.

- 영어나 한국어처럼 글자의 종류가 매우 많을경우는 나름 brute-force도 성능이 괜찮을 수 있다.