예제는 다 맞는데요...
- 예제는 데이터 중 극히 일부에 불과합니다. 자세한 것은 BOJ 101을 확인해 주시기 바랍니다. 예제는 자신의 코드가 맞을 것임을 확신하는 용도가 아니라, 입출력의 형식을 확인하고 문제의 설명을 검토하는 용도로 사용해야 합니다.
- 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 입력받으면 안 되고, 마음대로 바꿔서 출력해도 안 됩니다. 반드시 주어진 형식 그대로 입력하고, 예제 출력에서 보이는 대로 출력해야 합니다.
- "n을 입력하세요" 같은 걸 출력하면 안 됩니다.
- ideone 등 온라인 컴파일러 사이트에서 여러분의 코드를 직접 돌려 볼 수 있습니다.
대부분의 언어
- 입출력이 느리면 그것때문에 시간초과가 날 수 있습니다. 이 문제(링크)를 풀어 봅시다.
- exit code가 0이 아니면 비정상적인 종료를 의미합니다. C/C++ main의 return 1, 여러 언어의 exit(1) 등으로 0이 아닌 exit code를 내면 런타임 에러입니다.
- float, double 등의 부동소수점 자료형은 나타내는 수의 범위가 넓지만, 그 범위 안에 있는 모든 수를 정확하게 나타낼 수 있는 게 절대 아닙니다. 범위도 넓은데 원하는 수를 다 표현할 수도 있고 int만큼이나 빠르기까지 하면 그건 상상의 세계에 있는 자료형이죠.
- 같은 이유로, 부동소수점은 항상 오차를 조심해야 합니다. 가장 위험한 행동으로는 (1) 매우 작은 양수 (또는 절댓값이 매우 작은 음수)로 나누기, (2) 값이 거의 비슷한 두 수 중 어느 것이 더 큰지 판단하기, (3) 두 수가 같은지 판단하기, (4) 정수에 매우 가까운 수를 int로 바꾸기 등이 있습니다.
- '\b'는 하나의 문자일 뿐, 정말로 출력했던 문자를 도로 지우는 문자가 아닙니다. 단지 화면에 내보낼 때만 지운 것처럼 보이게 할 뿐입니다. 출력했던 문자는 지울 수 없습니다.
- 데이터의 끝에 '\n'가 들어오는 것이 원칙이지만, 꼭 지켜지는 사항은 아니며 오래된 데이터일 수록 지켜지지 않을 가능성이 높습니다. '\n'으로 입력의 끝을 검사하거나, 한 줄을 입력받고 마지막 글자를 지울 경우 문제가 생길 수 있습니다. 하지만 이 경우 오타/오역/요청 게시판에 제보하면 수정될 것입니다.
- 비슷하게, 오래된 문제에는 데이터 각 줄의 끝에 공백이 하나씩 들어있을 수도 있습니다. 이것도 오타/오역/요청 게시판에 제보하면 수정될 것입니다.
- 널 문자는 하나의 문자로 취급되며, 널 문자와 공백은 다릅니다. 일부 컴퓨터에서 널 문자를 출력할 때 빈 칸이 출력되는데, 실제로는 엄연히 공백과 다른 하나의 문자입니다. 그래서 널 문자를 출력하지 말아야 되는 데 / 공백을 출력해야 되는데 널 문자를 출력하면 오답입니다.
- "여러 개의 테스트케이스로 이루어져 있는" 문제에서는 각 테스트케이스마다 초기화를 합시다.
- 나눗셈에 음수가 들어갈 때 결과는 언어마다 다릅니다. C/C++처럼 0에 가까운 방향으로 반올림하는 경우도 있고, Python처럼 작아지는 방향으로 버림하는 경우도 있습니다. 마찬가지로, 언어에 따라 나머지 연산에서 음수가 나올 수도 있습니다.
- 자신이 짠 프로그램이 0-index를 사용하는지, 1-index를 사용하는지 확실하게 알도록 합시다.
반례 찾기
- 가장 중요한 것은 직접 데이터를 만들어서 넣어 보는 것입니다. https://www.acmicpc.net/problem/14405 를 예로 들어 봅시다. 그러면 이런 입력들을 넣어 볼 수 있습니다.
- pi 하나만 넣으면? ka? chu? 한 글자만 넣으면? p? k? c? i? a? r?
- pika는 YES가 나와야 합니다. 이걸 조금 변형하면? pik? pia? pka? piak? pkia? ipka? kipa? pikaa? pikka? piika? ppika?
- kapi도 YES가 나와야 합니다. 이걸 조금 변형하면? kap? kai? api? kaip? kpai? kapii? kaapi?
- 주어진 예제를 조금 변형하면? pikap? pikpi? pipikach? pipikaphu?
- 그냥 정말로 아무거나 넣으면? abcd? pipichukachuka? pichaku? ppap? pikach?
- 입력으로 1 이상 1,000,000 이하의 정수 N이 주어진다면 N=1, N=2 등의 최소 케이스가 잘 나오는지 확인하는 것이 좋습니다. 이런 입력이 특이 케이스가 되는 문제들이 종종 있고, 굳이 특이 케이스가 아니더라도 우리의 코드가 최소 케이스에서 틀릴 가능성은 얼마든지 있습니다. 위에서 언급한 "피카츄" 문제의 경우 p, k 등의 한 글자짜리 입력이 여기에 해당되겠죠.
- N=1,000,000 같은 최대 케이스를 넣었을 때 주어진 시간 제한 안에 답이 나오는지도 확인해 볼 수 있습니다. 답이 맞는지 확인하는 건 어떨까요? 문제에 따라 답을 손으로 알아내기 힘들 수도 있는데, 적어도 말이 되는 값은 나와야겠죠? 출력이 무조건 0 이상일 수밖에 없는 문제에서 음수가 나오면 뭔가 잘못되었다는 뜻입니다.
- 매우 간단한 풀이가 있는데 시간복잡도가 너무 커서 못 쓰고, 그 대신 더 효율적인 풀이를 생각해야 하는 문제가 있습니다. 이런 문제는 다음 방법으로도 반례를 찾을 수 있습니다. 매우 간단한 풀이이면 구현하기 쉬워서 틀릴 가능성이 낮다는 점을 이용한 방법입니다.
- 매우 간단한 풀이를 작성한다.
- 랜덤으로 데이터를 만든다.
- 간단한 풀이와 틀린 풀이가 내놓는 답이 일치하는지 검사한다.
- 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
- BOJ는 numpy 등 외장모듈을 지원하지 않습니다. (사실 모든 언어가 그렇습니다.)
- 풀이가 분명히 맞고 시간복잡도도 충분히 작은데 시간 초과가 난다면 언어를 Pypy로 설정하고 제출하면 됩니다. 파이썬은 원래 편리성과 속도를 맞바꾼 언어이기 때문에, 맞아야 될 풀이가 시간 초과더라도 이상할 게 전혀 없습니다.
- 두 수를 입력받고 나서 비교할 때는 반드시 int로 변환을 합시다. 문자열의 비교는 사전 순 비교이기 때문에, 3은 10보다 작지만 "3"은 "10"보다 큽니다.
- is 키워드는 두 대상의 값이 같은지가 아니라 완전히 같은 대상을 가리키는지를 비교합니다. BOJ에서 이걸 쓸 일은 거의 없습니다. 같은 "hello"더라도 따로 정의하면 다른 대상이 됩니다. 이걸 쓰면 디버깅하기도 힘든 게, -5 이상 255 이하의 int는 미리 만들어 놓고 정의할 때마다 가져다 쓰기 때문에, 딱 그 범위까지는 is와 ==가 똑같은 동작을 합니다. 그래서 손으로 반례를 찾으려고 하면 찾아지지 않습니다.
list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 O(N)입니다. 이외에도 O(N)이 걸리는 list 연산이 굉장히 많습니다. https://wiki.python.org/moin/TimeComplexity - 위의 이유로, list를 큐 또는 덱으로 사용하면 절대, 절대, 절대, 절대, 절대 안 됩니다!! 반드시 collections.deque를 써야 합니다.
- 아니요, queue.Queue도 안 됩니다. 이건 멀티스레딩을 위해 만들어진 큐이고 매우 느립니다.
- 파이썬의 재귀 깊이는 기본적으로 최대 1,000입니다. sys.setrecursionlimit으로 이 깊이를 조절할 수 있습니다.
- 두 개의 int를 나누면 float이 됩니다. int(a/b) 말고 a//b를 쓰는 것이 훨씬 안전합니다. 맨 위의 "부동소수점 자료형은 나타내는 수의 범위가 넓지만 ..."을 읽어보세요.
Pypy만
일반 Python에는 해당되지 않는 사항입니다.
- 사실 Pypy가 시간 초과더라도 이상할 건 없습니다. 쉬운 문제들은 거의 다 Pypy로 충분히 풀리지만, solved.ac 플래티넘 정도의 문제부터는 조금씩 위험해지기 시작합니다. 상황에 맞는 언어를 사용하도록 합시다.
- Pypy의 재귀 깊이는 파이썬과 달리 딱 정해 놓은 제한이 없습니다. 하지만 10만 단위로 너무 깊이 들어가면 스택 오버플로가 나고, 그 제한은 파이썬보다 낮습니다. 또한 Pypy는 재귀에 굉장히 약합니다.
- print가 sys.stdout.write보다 많은 메모리를 차지합니다. 구체적으로, print를 많이 사용할 수록 메모리도 많이 사용됩니다. 2020년 8월 9일 현재 Atcoder에서도 같은 현상이 나는 것으로 확인했습니다.
- sys.setrecursionlimit에서 설정해 놓은 재귀 깊이가 클 수록 메모리 사용량도 큽니다. 2020년 8월 9일 현재 Codeforces에서도 같은 현상이 나는 것으로 확인했습니다.
내 인생의 주연