[백준/C++] 백준 시간초과 해결법, 원인 정리

728x90

 

백준(C++) 시간초과 해결법

 

 

백준 알고리즘 문제를 풀다 보면 제출 시 시간초과가 뜨는 경우가 있다.

 

시간초과

 

 

이 경우 코드 몇 개만 추가하거나 수정하거나 해서 시간초과를 해결할 수 있다.

아니면 문제 해결에 사용한 알고리즘의 시간복잡도를 고려해 볼 수도 있다.

오늘 시간초과 원인과 해결법에 대해서 알아보자.

 

 

1. ios::sync_with_stdio(false) 추가

 

C++에서 입력은 크게 

printf와 cout

출력은

scanf와 cin이 있다.

 

여기서 cout와 cin은 printf, scanf에 비해 속도가 느리다.

그 이유는 cout와 cin는 실행 시 값의 자료형을 검사하기 때문이다.

속도가 좀 더 느리나 안정적이다.

 

---

ios::sync_with_stdio(false);

---

 

 

ios::sync_with_stdio는 c의 stdio와 cpp의 iosream을 동기화해준다.

이걸 false로 해준다면 동기화를 해제해 주고 C++ 만의
버퍼를 생성하게 된다. 이렇게 한다면 사용하는 버퍼의 수가 줄어들어 실행속도가 향상된다.
한 가지 단점이라면 코드를 추가하면 scanf, printf를 못쓰고 cout, cin만 사용할 수 있게 된다.

 

 

 

 

2. cin.tie(0), cout.tie(0) 추가

cin은 실행 시 flush연산을 한다

flush연산은 버퍼를 비우는 연산으로 실행 때마다 비우게 되므로 비효율적이다.

cin과 cout은 평소에 묶여있어서 cin을 사용할 때마다 cout에 flush연산이 발생한다.

cin.tie(0)을 해준다면

동기화를 해제하여 속도가 향상된다.

cout는 프로그램 종료 전 flush를 자동실행하기 때문에

그전에 따로 flush를 수행할 필요가 없다.

 

 

3. endl 대신 '\n'사용

 

 

endl은  사용 시 출력버퍼를 비우는 과정(flush)이 있어 더 느리다.

출력할 부분을 일일이 출력한다.
'\n'은 출력버퍼를 비우지 않는다.

출력할 부분을 모아두었다가 한 번에 출력한다.

 

즉

'\n' = 개행(줄 바꿈)
endl = 개행(줄 바꿈) + 버퍼 비우기(flush연산)

 

'\n'은 줄 바꿈만 한다면

endl은 버퍼 비우기까지 한다.

cout<<n<<endl; 대신

cout<<n<<'\n'를 사용하자

이 방법은 시간 차이가 크므로

시간초과를 해결하기 매우 좋다.

 

 

아래는 코드에 따른 수행시간 차이이다.

출력 속도 비교 (acmicpc.net)

endl은 매우 느리다!

 

 

 

4. 무한 재귀, while탈출

 

#include<iostream>
using namespace std;
void count(int n)
{
    cout<<n<<' ';
    count(n-1);
}
int main()
{
    int n=5;
    count(n);
}

 

위 코드는 5 4 3 2 1을 출력하기 위한 코드이다.

위 코드는 시간초과가 난다.

그 이유는 함수의 종료조건이 없기 때문이다.

종료 조건을 추가하면

 

#include<iostream>
using namespace std;
void count(int n)
{
    if(n==0)
        return;
    cout<<n<<' ';
    count(n-1);
}
int main()
{
    int n=5;
    count(n);
}

이렇게 되고 출력결과 '5 4 3 2 1'이 잘 나온다.

일반 함수에서는 상관없지만

자기 자신을 호출하는 재귀함수에서는

반드시 종료 조건을 추가해야 한다.

 

 

이와 마찬가지로 while문에서도 종료 조건을 명확하게 해야 한다.

어떠한 경우에도 while문을 탈출하지 못하는 경우가 존재하면 안 된다.

 

#include<iostream>
using namespace std;
int main()
{
    int n=5;
    while(1)
    {
        if(n==0)
            break;
        cout<<n<<' ';
        n--;
    }
}

 

위 코드는 '5 4 3 2 1'을 출력하기 위해 종료 조건을 추가한 while문이다.

 

 

 

5. 알고리즘의 시간복잡도 확인

 

2751번: 수 정렬하기 2 (acmicpc.net)

수를 정렬하는 문제이다.

 

이 문제를 버블정렬, 삽입정렬로 해결하려고 하면

시간초과가 나게 된다?

그 이유는 무엇일까?

그 이유는 일단 N의 입력값으로 최대 100만이 주어진다.

버블정렬, 삽입정렬과 같은 알고리즘은 시간복잡도가 O(N^2)이다

즉 100만 × 100만 = 1조이다.

문제에서 시간제한이 2초인데

C++기준 1초당 1억~3억 정도의 연산 횟수를 가진다고 보면 된다.

2초면 2억 ~6억 정돈데 1조 번의 연산을 하기에는 어림도 없다.

 

즉 문제를 푸는 알고리즘을 바꿔야 한다.

O(N^2)으로는 어림도 없고

O(NlogN) 혹은 O(N)으로 풀 수 있는 방법을 찾아야 한다.

 

시간복잡도를 계산하는 방법은 다음에 글을 쓰도록 하겠다.