정리해야 기억에 남는다.

시간 복잡도를 생각하지 않고 (알고리즘을 생각하지 않고) 직관적인 로직을 구현했다.

#include <iostream>

using namespace std;

int main()
{
	int N, M;

	cin >> N >> M;
	int array[100001] = {};
	
	for (int i = 0; i < N; i++)
	{
		cin >> array[i];
	}

	for (int j = 0; j < M; j++)
	{
		int min, max;
		cin >> min >> max;

		int sum = 0;
		for (int i = min - 1; i <= max - 1; i++)
		{
			sum += array[i];
		}

		cout << sum << endl;
	}
	

	return 0;
}

N, M 이 1 부터 시작하므로 배열의 index와 맞춰주기 위해 min과 max에 -1을 추가했다.

그 후 이중 반복문으로 구간의 합을 구했고 출력하는 로직을 완성했다.

<시간 제한: 1초> <데이터 크기: 100,000>

그러나 이중 반복문으로 시간 복잡도는 (O(n^2))이므로 O(100,000^2) = 10,000,000,000

즉 100억 > 1억 이므로 매우 비효율 적인 로직이라는 것을 알 수 있다.

따라서 시간 복잡도를 획기적으로 줄일 수 있는 로직을 찾아야 한다.

구간 합 알고리즘을 사용하기로 한다.

아이디어: 구간 합 배열을 만들어 시간 복잡도를 획기적으로 줄인다.

#include <iostream>

using namespace std;

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

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

	int S[100001] = {};

	for (int i = 1; i <= N; i++)
	{
		int temp;
		cin >> temp;
		S[i] = S[i - 1] + temp;
	}

	for (int i = 0; i < M; i++)
	{
		int min, max;
		cin >> min >> max;
		cout << S[max] - S[min - 1] << "\n";
	}

	return 0;
}

이렇게 작성하면 시간 복잡도를 줄일 수 있기 때문에 문제를 해결할 수 있다.

계속 시간 초과가 발생해서 여러 블로그를 보니 맨 처음 false와 null로 버퍼를 지우는 과정을 생략하여 속도를 빨라지게 한다고 나와있다. (이 처리를 하지 않으면 아무리 빠른 로직을 사용해도 통과가 되지 않는다..)

또한 마지막에 \n가 아닌 endl 를 사용하면 시간 초과가 발생한다.. 아마 endl 가 포함한 기능들 때문일 것이다..

알고리즘에서 시간 복잡도는 연산 횟수를 의미한다.

C++에서는 1억 번 연산을 1초 수행 시간으로 예측할 수 있다.

일반적으로 코딩 테스트에서는 빅-오 표기법 (O(n))을 기준으로 수행 시간을 계산한다.

코딩 테스트에서 가장 먼저 보이는 것이 시간 제한이다.

만약 시간 제한이 1초라면 1억 번 이하의 연산 횟수, 2초라면 2억 번 이하의 연산 횟수로 문제를 해결해야 한다.

따라서 문제를 보고 어떤 알고리즘을 사용해야 하는지 판단해야 한다.

예를 들어, <제한 시간: 1초> <데이터 수: 1000000> 라면 

O(n^2) 인 시간 복잡도를 가진 알고리즘을 사용한다고 가정

-> (1000000)^2 > 1억 으로 부적합 하다는 것을 알 수 있다.

결론적으로 시간 제한과 데이터 크기를 바탕으로 알고리즘을 선택하여 문제를 해결해야 한다.

시간 복잡도 계산

반복문을 기준으로 계산한다.

1. 반복문이 한 개라면 N

2. 반복문이 네 개라면 4N

3. 이중 반복문이 한 개라면 N^2

코딩 테스트에서는 상수를 무시하므로 1과 2는 O(n)으로 같다.

그러나 3은 이중 반복문이 있으므로 O(n^2)으로 계산한다.

받은 점수 중 최댓값을 찾고 저장한 후 평균 점수를 구하는 간단한 문제이다.

N개의 숫자의 합을 구하는 간단한 문제이다.

#include <iostream>

using namespace std;

int main()
{
	int N = 0;
	string num;

	cin >> N;
	cin >> num;

	int sum = 0;
	for (int i = 0; i < num.length(); i++)
	{
		sum += num[i] - '0';
	}

	cout << sum << endl;


	return 0;
}

num[i] - '0' 으로 쉽게 형 변환을 할 수 있다.

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