정리해야 기억에 남는다.

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

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

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

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

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

(추후에 나오는 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)으로 계산한다.

배열(array)은 데이터 형이 같은 여러 개의 값을 연속적으로 저장할 수 있는 데이터 구조이다.

int array[5] = {10, 20, 30, 40, 50};

이렇게 초기화를 한다면 이것을 int 형의 배열이라고 한다.

(만약 초기화를 하지 않고 선언, 즉 int array[5]; 를 한다면 배열 원소들은 그 메모리 위치에 전부터 우연히 남아있던 쓰레기 들을 값으로 취한다. 그래서 선언보단 모든 변수는 초기화를 해주는 것이 좋다.)

배열은 개별적인 접근을 허용하기 위해 index를 사용하여 배열 원소에 차례로 번호를 부여한다.

이것이 배열의 유용한 점이다.

C++ 배열 index는 항상 0부터 시작한다는 것을 꼭 명심해야 한다.

문자열은 메모리에 바이트 단위 연속적으로 저장되어 있는 문자들을 말한다.

string은 추후에 살펴보도록 하고 우선 C 스타일 문자열을 살펴본다.

문자열은 독특한 특징을 가지고 있는데 마지막에 꼭 \0 (null character)를 넣어줘야 한다는 것이다.

char tiger[5] = {'h', 'a', 'p', 'p', 'y'};
char tiger[5] = {'m', 'o', 'm', 'o', '\0'};

두 배열 모두 char형 배열이지만 두 번째만이 문자열이다.

\0 를 만날 때까지 문자 단위로 문자열을 처리한다.

따라서 문자열을 저장하는 데 필요한 char형 배열의 최소 크기를 정할 때 

null character 하나가 추가된다는 것을 고려해야 한다.

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