정리해야 기억에 남는다.

배열은 기본적으로 여러 개의 값을 저장할 수 있다.

축구 선수의 데이터를 저장해야 한다고 가정하면 이름부터 패스 성공률, 슛 성공률, 득점 등 여러 데이터를 저장해야 한다.

그러나 배열은 여러 값을 저장할 순 있지만 데이터 형이 모두 같아야 한다는 특징이 있다.

이와 같은 기능을 수행할 수 있는 것이 구조체이다.

구조체를 사용하면 관련된 정보를 묶어서 저장하고 사용할 수 있다.

(추후에 나오는 class와 비슷하지만 access specifier인 public, private, protected 기능을 사용할 수 없다. 이것이 차이점.)

struct soccerplayer
{
    char name[20];
    float passsuccess_rate;
    int backnumber;
}

이렇게 구조체를 선언하고 멤버 변수를 정의한다.

name은 soccerplayer형의 구조체 변수라고 한다.

struct soccerplayer
{
    char name[20];
    //물론 string 사용 가능하다.
    float passsuccess_rate;
    int backnumber;
}

soccerplayer son = {"son", 89.12, 7};
soccerplayer son {"son", 89.12, 7};

son.name = "son";

c++11 부터 이렇게 구조체를 초기화 할 수 있다.

또한 '=' 표시를 생략해도 된다.

멤버 연산자(.)를 통해서 개별 멤버에 직접 접근할 수도 있다.

C++ 에서 문자열을 배열로써 저장할 수 있지만 string 형 변수로 저장할 수 있다.

char cat [10] = "cat";

string dog = "dog";

string pig;
cin >> pig;

배열로 저장할 땐 크기를 지정해야 하지만

string은 따로 지정하지 않아도 자동으로 처리한다.

그래서 입력을 받을 때에도 크기를 따로 지정하지 않아도 된다.

배열로써 크기를 지정한 후 데이터 추가와 같은 행위를 할 때 지정한 크기를 넘어간다면 메모리 문제가 발생한다.

string은 필요 시 자동으로 변환하기 때문에 더욱 안전하다.

따라서 기본적으로 char 형 배열 변수로 문자열을 저장할 수 있지만

string을 이용하면 단점도 보완하고 더 편리하게 문자열을 저장할 수 있다.

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

#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)으로 계산한다.