구간 합 구하기 4

내가 작성한 코드

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

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    int N, M;
    int num;
    int i, j;
    cin >> N >> M;
    vector<int> n(N + 1);
    n[0] = 0;
    for (int q = 0; q < N; ++q) {
        cin >> num;        
        n[q + 1] = n[q] + num;
    }
    while (M--) {
        cin >> i >> j;
        cout << n[j] - n[i - 1] << '\n';
    }
    return 0;
}

처음 제출한 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    int N = 0, M = 0;
    int num = 0;
    vector<int> n;
    int i = 0, j = 0;
    cin >> N >> M;
    while (N--) {
        cin >> num;
        n.push_back(num);
    }
    while (M--) {
        cin >> i >> j;
        int sum = 0;
        for (int s = i - 1; s < j; ++s) {
            sum += n[s];
        }
        cout << sum << endl;
    }
    return 0;
}

고민한 부분

1. 당연하게도 주어진 수의 배열을 주어진 범위 내에서 순회하며 합연산을 하는것은 시간 초과로 나왔다.

   1. 해결방법
      배열에 넣는 값을 DP(동적 프로그래밍)의 방법(작은 문제의 결과 값이 항상 같다는 점을 이용해 큰 문제를 해결하는 방식)으로 해결하고자 하였습니다.
      그리하여 배열에 단순히 받은 수를 넣는 것이 아닌 처음부터 현재까지 받은 수의 합을 넣어주었습니다.

2. DP의 방식을 사용했음에도 불구하고 시간 초가로 나왔습니다.
   그 이유는 vector 멤버함수인 push_back을 사용해서 호출시간이 길었기 때문입니다.

   2. 해결방법
      push_back을 사용하는 것이 아닌 대입 연산자로 넣는 것

3. 대입 연산자를 사용했음에도 불구하고 시간이 초과하였습니다.
   그 이유는 출력문의 마지막 endl을 호출하기 때문입니다.

   3. 해결 방법
      endl또한 함수이기 때문에 호출이 일어납니다. 이 시간을 줄이기 위해 '\n'을 직접 입력해 주었습니다.

4. 그럼에도 불구하고 시간초과가 일어났습니다.

   해결방법
   main문 상단에

   	ios::sync_with_stdio(false);
   	cin.tie(0);
   	cout.tie(0); 

   를 추가합니다.

   코드설명
   ios_base::sync_with_stdio : c의 stdio와 cpp의 iostream을 동기화시켜주는 역할
   이 때 iostream과 stdio의 버퍼를 모드 사용하기 때문에 딜레이 발생
   -> 동기화를 false로 비활성화 시켜 c++만의 독립적인 버퍼 생성하여 실행속도 상승

   단점 : 동기화된 버퍼는 thread-safe하기 때문에 모든 IO의 순서가 보장됨. 즉, 멀티 스레드 환경에서 출력순서를 보장해 줄수 없게됨
   -> cin과 C의 scanf. gets. getchar등을 같이 사용하면 안됨, cout과 C의 pringf, puts, putchar등을 같이 사용하면 안됨

   cin.tie(null) : cin과 cout의 묶음을 풀어준다.
   기본적으로 cin과 cout은 묶여있으며 스트림들은 한 스트림이 다른 스트림에서 IO작업을 진행하기 전 버퍼를 비워준다.
   null로 설정하게 되면

   cout << "이름을 입력하세요: ";
   cin >> name; 

   이름을 입력하라는 출력이 되기도 전에 입력을 받는 경우가 생길 수 있다. 버퍼를 비워주지 않아 cout의 출력이 이루어 지지 않은것이다. tie로 묶어주었다면 스트림이 바뀌며 버퍼가 비워졌겠지만 버퍼를 비워주지 않기 때문에 발생하는 문제이다.
   위 방법을 사용하여 버퍼를 비워주는 시간 또한 단축시켜 문제를 해결 할 수 있었다.

위의 방법을 알려준 블로그의 코드로 테스트 했을 때 메모리 2804kb, 시간 44ms에서

메모리 2412kb, 시간 40ms로 줄이는 작업을 하며 통과하였다.