BOJ 작동 원리와 자주 틀리는 요인

한 번 쭉 읽어볼 것

 

---

1. BOJ 작동 원리

채점 서버에는 한 쌍 이상의 입력 파일과 출력 파일이 있습니다.코드를 제출하면 그 코드에 입력 파일에 적힌 대로 입력하고 나타나는 출력을 출력 파일과 비교합니다. 모든 입력/출력 파일에 대해 코드가 문제 없이 올바른 출력을 내야 합니다. 여기서 "올바름"이란 것은 단순히 정답과 같은 값이 아니라 같은 출력을 의미합니다. 예를 들어 45.0을 출력해야 하는데 45나 45.00을 출력하면 오답입니다.

스페셜 저지가 있는 문제에는 출력이 올바른지 검사하는 채점 코드가 따로 있습니다. 그러므로 "올바른 출력"은 여러 가지가 될 수 있고, 그 중 하나만 출력하면 됩니다. 예를 들어 10^-2 이하의 오차를 허용하는 문제라면 출력과 정답의 오차가 10^-2 이하인지 검사하는 코드가 있습니다. 그런 문제에서 정답이 45.0이라면 45나 45.00을 출력해도 정답을 받을 수 있습니다.

• 구현을 어떻게 했는지 같은 건 채점 프로그램이 전혀 신경쓰지 않습니다. 그냥 답이 맞게 나오면 됩니다. 반대로, "틀렸습니다"가 나왔다는 건 무조건 답이 맞게 나오지 않는다는 뜻입니다.
• 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 입력받으면 안 됩니다! 예제 형식 그대로 입력받으세요.
• 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 출력해도 안 됩니다! 예제 형식 그대로 출력하세요. 예외적으로, (대부분의 문제에서) 각 줄의 맨 끝에 공백을 넣어도 되고 안 넣어도 되며, 출력의 맨 끝에 줄바꿈을 넣어도 되고 안 넣어도 됩니다. 맨 끝을 제외한 나머지 줄바꿈은 넣어야 합니다.
• 입력 조건을 코드에 넣을 필요는 없습니다. 예를 들어 "3 <= N <= 5000이다."라고 적혀 있으면, 이건 모든 입력 파일이 3 <= N <= 5000의 조건을 지킨다는 뜻입니다. 따라서 if(3 <= N && N <= 5000)을 따로 넣지 않아도 됩니다.
• 시간 제한은 각 파일마다 따로따로 적용됩니다. 즉 시간 제한이 1초면 첫 번째 파일에 1초, 두 번째 파일에 1초, ..., 마지막 파일에 1초 이내가 걸려야 합니다. 채점 현황에서 볼 수 있는 "시간"은 가장 오래 걸린 파일에서의 구동 시간을 나타냅니다.
• 메모리 제한도 마찬가지인데, 한 순간에라도 지정된 메모리를 초과하면 안 됩니다. 채점 현황에서 볼 수 있는 "메모리"는 최대 메모리 사용량을 나타냅니다.
• "첫 줄에 테스트케이스의 개수 T가 주어진다." 또는 "입력은 여러 개의 테스트케이스로 이루어져 있다." 같은 문제는 그 T개의 테스트케이스가 한 파일에 들어있다는 뜻입니다. 그런데 시간과 메모리 제한은 각 파일마다 따로따로 적용된다고 했으므로 주어진 시간 안에 한 파일에 들어있는 모든 테스트케이스가 돌아가야 합니다. 또한 입력과 출력은 분리되어 있으므로 테스트케이스를 받을 때마다 출력해도 되고, 전부 받은 뒤 전부 출력해도 되고, 심지어 받기 전에 출력해도 (???) 됩니다. 하지만 출력 자체의 순서는 지켜야 합니다.
• 언어에 따라 시간이나 메모리가 초과되고도 정답을 받을 수 있는데, 그 언어가 정해진 시간/메모리 보너스를 받기 때문입니다. https://www.acmicpc.net/help/language
• 채점 현황의 "컴파일 에러"를 누르면 어디서 에러가 났는지 볼 수 있습니다. 컴파일 에러일 경우에만 가능합니다.

출처) https://www.acmicpc.net/blog/view/55

 

2. 자주 틀리는 요인

예제는 다 맞는데요...

• 예제는 데이터 중 극히 일부에 불과합니다. 자세한 것은 BOJ 101을 확인해 주시기 바랍니다. 예제는 자신의 코드가 맞을 것임을 확신하는 용도가 아니라, 입출력의 형식을 확인하고 문제의 설명을 검토하는 용도로 사용해야 합니다.
• 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 입력받으면 안 되고, 마음대로 바꿔서 출력해도 안 됩니다. 반드시 주어진 형식 그대로 입력하고, 예제 출력에서 보이는 대로 출력해야 합니다.
• "n을 입력하세요" 같은 걸 출력하면 안 됩니다.
• ideone 등 온라인 컴파일러 사이트에서 여러분의 코드를 직접 돌려 볼 수 있습니다.

데이터가 잘못된 것 같아요

• 이런 글이 올라올 때 대부분의 경우는 본인의 코드가 잘못된 것이었습니다.
• 이런 건 단순 추측 말고 assert문으로 확실하게 확인해 보시기 바랍니다.

---

대부분의 언어

• 입출력이 느리면 그것때문에 시간초과가 날 수 있습니다. 이 문제(링크)를 풀어 봅시다.
• exit code가 0이 아니면 비정상적인 종료를 의미합니다. C/C++ main의 return 1, 여러 언어의 exit(1) 등으로 0이 아닌 exit code를 내면 런타임 에러입니다.
• float, double 등의 부동소수점 자료형은 나타내는 수의 범위가 넓지만, 그 범위 안에 있는 모든 수를 정확하게 나타낼 수 있는 게 절대 아닙니다. 범위도 넓은데 원하는 수를 다 표현할 수도 있고 int만큼이나 빠르기까지 하면 그건 상상의 세계에 있는 자료형이죠.
• 같은 이유로, 부동소수점은 항상 오차를 조심해야 합니다. 가장 위험한 행동으로는 (1) 매우 작은 양수 (또는 절댓값이 매우 작은 음수)로 나누기, (2) 값이 거의 비슷한 두 수 중 어느 것이 더 큰지 판단하기, (3) 두 수가 같은지 판단하기, (4) 정수에 매우 가까운 수를 int로 바꾸기 등이 있습니다.
• '\b'는 하나의 문자일 뿐, 정말로 출력했던 문자를 도로 지우는 문자가 아닙니다. 단지 화면에 내보낼 때만 지운 것처럼 보이게 할 뿐입니다. 출력했던 문자는 지울 수 없습니다.
• 데이터의 끝에 '\n'가 들어오는 것이 원칙이지만, 꼭 지켜지는 사항은 아니며 오래된 데이터일 수록 지켜지지 않을 가능성이 높습니다. '\n'으로 입력의 끝을 검사하거나, 한 줄을 입력받고 마지막 글자를 지울 경우 문제가 생길 수 있습니다. 하지만 이 경우 오타/오역/요청 게시판에 제보하면 수정될 것입니다.
• 비슷하게, 오래된 문제에는 데이터 각 줄의 끝에 공백이 하나씩 들어있을 수도 있습니다. 이것도 오타/오역/요청 게시판에 제보하면 수정될 것입니다.
• 널 문자는 하나의 문자로 취급되며, 널 문자와 공백은 다릅니다. 일부 컴퓨터에서 널 문자를 출력할 때 빈 칸이 출력되는데, 실제로는 엄연히 공백과 다른 하나의 문자입니다. 그래서 널 문자를 출력하지 말아야 되는 데 / 공백을 출력해야 되는데 널 문자를 출력하면 오답입니다.
• "여러 개의 테스트케이스로 이루어져 있는" 문제에서는 각 테스트케이스마다 초기화를 합시다.
• "다음 코드를 실행했을 때 무슨 결과가 나오는지" 구하는 문제 (예시 1) (예시 2) 같은 경우, 정말로 그걸 직접 실행하라는 뜻이 아니라 만약에 실행한다면 무슨 값이 나올지를 구하라는 뜻입니다.
• 나눗셈에 음수가 들어갈 때 결과는 언어마다 다릅니다. C/C++처럼 0에 가까운 방향으로 반올림하는 경우도 있고, Python처럼 작아지는 방향으로 버림하는 경우도 있습니다. 마찬가지로, 언어에 따라 나머지 연산에서 음수가 나올 수도 있습니다.
• 자신이 짠 프로그램이 0-index를 사용하는지, 1-index를 사용하는지 확실하게 알도록 합시다.

반례 찾기

• 가장 중요한 것은 직접 데이터를 만들어서 넣어 보는 것입니다. https://www.acmicpc.net/problem/14405 를 예로 들어 봅시다. 그러면 이런 입력들을 넣어 볼 수 있습니다.
• 1. pi 하나만 넣으면? ka? chu? 한 글자만 넣으면? p? k? c? i? a? r?
• 1. pika는 YES가 나와야 합니다. 이걸 조금 변형하면? pik? pia? pka? piak? pkia? ipka? kipa? pikaa? pikka? piika? ppika?
• 1. kapi도 YES가 나와야 합니다. 이걸 조금 변형하면? kap? kai? api? kaip? kpai? kapii? kaapi?
• 1. 주어진 예제를 조금 변형하면? pikap? pikpi? pipikach? pipikaphu?
• 1. 그냥 정말로 아무거나 넣으면? abcd? pipichukachuka? pichaku? ppap? pikach?
• 입력으로 1 이상 1,000,000 이하의 정수 N이 주어진다면 N=1, N=2 등의 최소 케이스가 잘 나오는지 확인하는 것이 좋습니다. 이런 입력이 특이 케이스가 되는 문제들이 종종 있고, 굳이 특이 케이스가 아니더라도 우리의 코드가 최소 케이스에서 틀릴 가능성은 얼마든지 있습니다. 위에서 언급한 "피카츄" 문제의 경우 p, k 등의 한 글자짜리 입력이 여기에 해당되겠죠.
• N=1,000,000 같은 최대 케이스를 넣었을 때 주어진 시간 제한 안에 답이 나오는지도 확인해 볼 수 있습니다. 답이 맞는지 확인하는 건 어떨까요? 문제에 따라 답을 손으로 알아내기 힘들 수도 있는데, 적어도 말이 되는 값은 나와야겠죠? 출력이 무조건 0 이상일 수밖에 없는 문제에서 음수가 나오면 뭔가 잘못되었다는 뜻입니다.
• 매우 간단한 풀이가 있는데 시간복잡도가 너무 커서 못 쓰고, 그 대신 더 효율적인 풀이를 생각해야 하는 문제가 있습니다. 이런 문제는 다음 방법으로도 반례를 찾을 수 있습니다. 매우 간단한 풀이이면 구현하기 쉬워서 틀릴 가능성이 낮다는 점을 이용한 방법입니다.
• 1. 매우 간단한 풀이를 작성한다.
• 1. 랜덤으로 데이터를 만든다.
• 1. 간단한 풀이와 틀린 풀이가 내놓는 답이 일치하는지 검사한다.
• 1. 2-3번을 반복...
• PS에서의 런타임 에러와 디버깅 (링크)

알고리즘

• 배열 기반의 리스트 (C++ vector, string, Java ArrayList, String, Python list, str, ...)의 중간에 뭔가를 끼워넣거나 빼는 건 O(N)입니다.
• 퀵소트를 직접 구현하면 O(N^2)이 걸리는 데이터를 손쉽게 만들 수 있습니다. 그냥 내장된 정렬 함수를 쓰세요. 정렬을 직접 구현하는 것을 연습하시고자 한다면, 피벗을 랜덤으로 잡은 퀵소트를 구현하거나 힙소트, 머지소트 등 다른 O(nlogn) 정렬 알고리즘을 구현하는 방법이 있습니다.
• 격자에서 탐색할 때 범위 체크를 반드시 합시다.
• DP를 할 때에는 메모이제이션을 합시다. 안 그러면 DP가 아닙니다.
• DFS는 절대로 최단거리를 구해 주지 않습니다. 물론 메모이제이션 없이 모든 경로를 탐색하는 DFS는 최단거리를 구해 주겠지만, 시간 초과가 날 것입니다.

  

• BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. BFS 문제에서 시간 초과나 메모리 초과가 나면 이것부터 의심해 보시면 됩니다.

  

• BFS를 할 때 큐의 크기가 제한되어 있도록 구현했다면, 그 크기는 적어도 방문할 수 있는 정점의 총 개수보다는 크게 합시다.

---

C/C++

• 오버플로우는 항상 조심합시다!!! 특히 "답을 k로 나눈 나머지를 출력한다." 종류의 문제에서 답을 통째로 다 구하고 k로 나누면 안 됩니다. 중간에 오버플로우가 날 수 있습니다.
• ios:sync_with_stdio(false);를 한 뒤에는 iostream과 stdio를 혼용하면 안 됩니다. iostream에 해당하는 것으로 cin, cout 등이 있고, stdio에 해당하는 것으로 printf, scanf, putchar, getchar, puts, gets 등이 있습니다.
• 지역 변수와 지역 배열은 초기화가 안 되어 있습니다.
• 전역 배열을 {1}이라고 초기화하면 첫 원소만 1이 되고 나머지는 그대로 0으로 남습니다.
• float는 너무 부정확해서 유의미한 사용이 사실상 불가능합니다. double을 씁시다.
• 위에서도 언급했지만 (음수) % (양수)는 양수가 아닙니다. 특히 A[(i-1)%N] 같은 걸 하면 큰일납니다. 이럴 때는 (i+N-1)%N을 하면 됩니다.
• char 배열에 길이 N의 문자열을 담으려면 널 문자까지 담아야 하므로 배열의 크기는 N+1 이상이어야 합니다.
• 전역배열의 크기는 넉넉하게 잡는 것을 추천드립니다. 예를 들어 "수열의 길이는 10만 이하이다."라고 해서 int A[100000]을 잡았는데 for(int i=1; i<=100000; i++)을 한다든지, "문자열의 길이는 10만 이하이다."라고 해서 char A[100000]을 잡았는데 널 문자때문에 사실 100001개가 필요하다든지... 그래서 [100055]처럼 실제 최대값보다 조금 많이 잡으면 인덱싱 오류가 날 가능성이 줄어듭니다.
• 채점 환경에서 포인터의 크기는 8바이트입니다. sizeof를 권장합니다.
• strlen은 O(N)입니다. 따라서 for(int i=0; i<strlen(s); i++)은 좋지 않습니다. s의 크기가 변하지 않는다면 strlen(s)를 미리 구해둔 다음 그 값으로 for 루프를 돌립시다.
• memset은 0과 -1만 가능합니다. https://www.acmicpc.net/board/view/23217#comment-40375
• strcmp는 -1, 0, 1이 아니라 음의 정수, 0, 양의 정수를 반환합니다.
• atoi에는 널 문자로 끝나는 문자열을 넘겨줘야지, char형 하나의 주소를 넘겨주면 안 됩니다. 참고로 숫자 c 하나를 int로 바꾸려면 c - '0'을 하면 됩니다.
• 반환형이 있는 함수를 짤 때에는 반드시 모든 분기점에서 무언가를 반환하도록 합시다. 특히 반환하지 않고 함수가 끝나는 것은 undefined behavior이며, 현재 BOJ의 컴파일러는 이 경우에 런타임 에러를 많이 띄우고 있습니다.
• range-based for는 C++11에서 추가된 기능입니다. C++로 제출하면 안 됩니다.
• A[x] = x++;는 매우 위험합니다. 적어도 C++14까지는 undefined behavior였습니다. (C++17에서의 동작은 잘 아시는 분이 제보 바랍니다.)
• a <= b <= c는 (a <= b) <= c로 계산됩니다. "b가 a 이상, c 이하임"을 나타내려면 a <= b && b <= c라고 해야 합니다.
• scanf("%d", &a)를 했는데 EOF를 만나면 a가 0이나 EOF가 되는 게 아니라 저 함수 자체가 EOF를 반환합니다.
• fflush(stdin)은 표준이 아닙니다. rewind(stdin)도 표준이 아닙니다. fflush는 출력 스트림만 비울 수 있습니다.
• itoa는 표준이 아닙니다. 그 대신 sprintf를 쓰세요.

Java

• 위의 C/C++ 내용 중 다수가 Java에도 해당됩니다.
• package boj; 같은 건 모두 지우고 제출해야 하며, 클래스 이름은 Main이어야 합니다.
• Scanner는 하나만 만드세요.
• Linkedlist의 x번째 원소 찾기는 O(x)입니다.
• Integer 등 wrapper class의 객체끼리는 == 으로 비교하면 안 되고 equals 메서드로 비교해야 합니다.
• 원인은 확실치 않지만 Scanner는 메모리를 많이 사용하는 것으로 보입니다. Scanner를 사용하는 것만으로도 메모리 초과가 발생할 수 있습니다. 이 문제(링크)에서 보았듯이 느린 입력이기도 하니, 가능하면 BufferedReader를 사용하는 것이 좋습니다.

Python과 Pypy, 그 외 언어들은 출처 링크에서 참고하기 바람
출처) https://www.acmicpc.net/blog/view/70