[백준] 실패 원인 - 틀렸습니다, 시간 초과, 메모리 초과, 출력 초과, 런타임 에러, 컴파일 에러

백준에서 문제를 풀다 보면 맞았습니다라는 초록색 글씨 대신 빨간색 글씨를 종종, 혹은 많이 보게 될텐데, 여러가지 이유가 있다. 실패한 이유에 대해 알아보자.



1. 틀렸습니다.

이건 뭐 다른 이유가 없이 틀린 거다. 그게 논리적인 이유가 됐든, 무법의 오류가 됐든, 문제를 잘못 읽었든, 예외적인 케이스를 빼먹었든 간에 뭔가 잘못해서 틀린 것이다. 틀리는 유형에 여러가지가 있는데, 아래의 예시 말고도 자신이 자주하는 실수가 있는지 꼭 생각해보자.

1. 배열에 값을 잘못 넣었거나 잘못된 index에 넣어서 배열을 잘못 만든 경우

2. 데이터형 범위를 체크하지 않은 경우 

 Int형과 unsigned long long형은 가능한 수의 범위가 크게 차이난다. 문제를 봤을 때 수가 매우 커질 것 같으면 타입을 바꿔주자.

3. 수학적인 부분 

특히 나눈 결과를 올바른 타입으로 나타내었는지 확인해주자. int / int는 몫만 나오게 된다.

4. 출력을 잘못한 경우

생각보다 자주 나오는 케이스다. 출력 초과랑은 다른 경우인데, 가령 출력을 "true" 또는 "false"로 나타내야하는데 "TRUE" 또는 "FALSE"로 나타내면 틀리게 된다.

5. 조건을 틀린 경우

특히 특정 범위 내에서 해결해야 하는 문제이면, 예를 들어 n = 0 ~ n = 100000 까지 돌아야하는 문제이면 최대값도 넣어보자. 계산이 올바르게 되었다고 해도, 형 범위가 넘었거나 기타 다른 문제에 의해 틀린 결과가 나올 수 있다. 또는 문제를 잘못 읽었을 수도 있으니 다시 한번 읽어서 빠진 조건이 있는지 다 체크해보자. 백준에 질문 검색 란이 있는데, 여러가지 테스트 케이스가 올라오니 참고하는 것도 좋다.

6. while문 같은 루프문을 쓸 경우

조건이 제대로 카운트 되지 않아서 무한루프가 발생하는지, 혹은 의도한대로 카운트가 되는지 체크해주자.



2. 시간 초과

여러 이유가 있겠지만 너무 느린 알고리즘으로 짠다거나, 루프문을 잘못 사용했을 때 발생하게 된다.

쉬운 예로 Bubble sort를 사용하면 O(n^2) 시간이 나오는데, Quick Sort는 상황에 따라 O(NlogN) 시간까지 단축될 수 있다. 이 때 n이 100개 정도면 뭘 써도 상관 없지만, n이 100000개면 n * n = 10000000000, 백억은 당연히 시간초과가 될 것이다. 당연히 100000 * log(100000)이 훨씬 빠를 것이다.
보통 시간 제한이 1초이면 대략 10^8정도까진 허용되는데 (물론 문제에 따라 다 다를 수 있다.) 보기에 뭔가 간당간당해보이고, 제출했을 때 시간이 초과되면 다른 알고리즘을 생각해보자. 시간을 줄이는 알고리즘엔 대표적으로 동적 계획법, 이분 탐색 등이 있다.

무한 루프가 걸려서 시간 초과가 나오는 경우도 있는데, 자신이 짠 루프가 제대로 종료가 되는지 꼭 체크해주자.




3. 메모리 초과

의외로 배열은 메모리 초과의 원인으로 발생하는 일이 많지 않다.

//
//  test.cpp
//  BJ
//
//  Created by 신기열 on 25/10/2019.
//  Copyright © 2019 신기열. All rights reserved.
//

#include <stdio.h>
#include <iostream>

using namespace std;

int test[100000000];

int main(){
    
    for(int i = 0; i < 100000000; i++){
        test[i] = 1;
    }
    
    for(int i = 0; i < 100; i++){
        cout << test[i];
    }
}

좀 단순한 예시긴 한데, 아래의 코드를 돌려봐도 test배열에 제대로 들어가고 출력도 제대로 되긴한다. 물론 컴파일러에 따라, 문제에 따라 달라질 수 있다.
메모리 초과는 보통 재귀함수를 쓸 때 발생하는데, 가령 DFS로 재귀를 돌린다고 할 때 깊이가 너무 깊어지게 되면 스택에 넣는 함수가 많아지게 되고, 예전 글에 썼던 것처럼 10000번 정도 재귀를 돌리면 터지기 때문에 메모리 초과가 날 수 있다.
애당초 메모리 초과가 발생하는 경우를 많이 못 봐서 또 어떤 케이스에서 발생하는지 아직 잘 모르겠다.



4. 출력 초과

그냥 디버깅 한다고 적어 놓은 출력문을 주석 처리를 안하거나, 출력 조건을 제대로 안봐서 나오는 케이스이다. 디버깅용 출력은 꼭 지우도록 하자.




5. 런타임 에러

주로 잘못된 값을 참조할 때 발생하는데, 이것에 대해선 아래의 링크를 참고해보자.

https://www.acmicpc.net/board/view/22980




6. 컴파일 에러

라이브러리를 임포트 하지 않았거나, 언어를 잘못 지정해서 컴파일 할 때 발생한다. 빠진 부분이 있는지 확인하자.