자주 틀리는 요인

원래는 BOJ 101 글에 있었던 내용인데, 쓸 내용이 너무 많아져서 독립된 글로 옮겼습니다.

예제는 다 맞는데요...

  • 채점 데이터에는 예제만 있는 게 아니라 우리에게 공개되지 않는 추가적인 데이터가 많이 준비되어 있습니다. 그 데이터에서도 전부 옳은 답을 내야 합니다. 예제 입출력은 "예를 들어 이런 입력을 줄 것이고 이 때는 이렇게 출력해야 한다"라는 뜻이지, "이게 잘 돌아가면 대충 맞는 코드일 것이다"라는 뜻이 절대, 절대, 절대 아닙니다!!
  • 그 전에 예제가 다 맞는 건 확실한가요? 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 입력받으면 안 되고, 마음대로 바꿔서 출력해도 안 됩니다. 반드시 주어진 형식 그대로 입력하고, 예제 출력에서 보이는 대로 출력해야 합니다.
  • "n을 입력하세요" 같은 걸 출력하면 안 됩니다.
  • ideone 등 온라인 컴파일러 사이트에서 여러분의 코드를 직접 돌려 볼 수 있습니다.

데이터가 잘못된 것 같아요

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

대부분의 언어

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

알고리즘

  • 배열 기반의 리스트 (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로 나누면 안 됩니다. 중간에 오버플로우가 날 수 있습니다.
  • 지역 변수와 지역 배열은 초기화가 안 되어 있습니다.
  • 전역 배열을 {1}이라고 초기화하면 첫 원소만 1이 되고 나머지는 그대로 0으로 남습니다.
  • float는 너무 부정확해서 유의미한 사용이 사실상 불가능합니다. double을 씁시다.
  • (음수) % (양수)는 양수가 아닙니다. 특히 A[(i-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)입니다.
  • memset0과 -1만 가능합니다. https://www.acmicpc.net/board/view/23217#comment-40375
  • strcmp는 -1, 0, 1이 아니라 음의 정수, 0, 양의 정수를 반환합니다.
  • atoi에는 널 문자로 끝나는 문자열을 넘겨줘야지, char형 하나의 주소를 넘겨주면 안 됩니다. 숫자 c 하나를 int로 바꾸려면 c - '0'을 하면 됩니다.
  • 반환형이 있는 함수를 짤 때에는 반드시 모든 분기점에서 무언가를 반환하도록 합시다.
  • range-based for는 C++11에서 추가된 기능입니다. C++로 제출하면 안 됩니다.
  • A[x] = x++;는 매우 위험합니다. 적어도 C++14까지는 undefined behavior였습니다. (C++17에서의 동작은 잘 아시는 분이 제보 바랍니다.)
  • a <= b <= ca <= b && b <= c가 아니라 (a <= b) <= c입니다.
  • scanf("%d", &a)를 했는데 EOF를 만나면 a가 0이나 EOF가 되는 게 아니라 저 함수 자체가 EOF를 반환합니다.
  • fflush(stdin)은 표준이 아닙니다. fflush출력 스트림만 비울 수 있습니다.

Java

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

Python

"자주 틀리는 요인"과는 상관 없는 이야기지만, 파이썬 2는 허점 투성이이고 2020년에 죽는 언어입니다. 제발 2 말고 3을 씁시다...

  • BOJ는 numpy 등 외장모듈을 지원하지 않습니다. (사실 모든 언어가 그렇습니다.)
  • 풀이가 분명히 맞고 시간복잡도도 충분히 작은데 시간 초과가 난다면 언어를 Pypy로 설정하고 제출하면 됩니다. 파이썬은 원래 편리성과 속도를 맞바꾼 언어이기 때문에, 맞아야 될 풀이가 시간 초과더라도 이상할 게 전혀 없습니다.
  • 사실 Pypy가 시간 초과더라도 이상할 건 전혀 없습니다. 상황에 맞는 언어를 사용하도록 합시다.
  • is 키워드는 두 대상의 값이 같은지가 아니라 완전히 같은 대상을 가리키는지를 비교합니다. BOJ에서 이걸 쓸 일은 거의 없습니다. 같은 "hello"더라도 따로 정의하면 다른 대상이 됩니다. 이걸 쓰면 디버깅하기도 힘든 게, -5 이상 255 이하의 int는 미리 만들어 놓고 정의할 때마다 가져다 쓰기 때문에, 딱 그 범위까지는 is와 ==가 똑같은 동작을 합니다. 그래서 손으로 반례를 찾으려고 하면 찾아지지 않습니다.
  • list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 O(N)입니다. https://wiki.python.org/moin/TimeComplexity
  • 위의 이유로, list를 큐로 사용하면 절대, 절대, 절대, 절대, 절대 안 됩니다!! 큐는 반드시 collections.deque를 써야 합니다.
  • 아니요, queue.Queue도 안 됩니다. 이건 멀티스레딩을 위해 만들어진 큐이고 매우 느립니다.
  • 파이썬의 재귀 깊이는 기본적으로 최대 1,000입니다. sys.setrecursionlimit으로 이 깊이를 조절할 수 있습니다.
  • Pypy의 재귀 깊이는 파이썬과 달리 딱 정해 놓은 제한이 없습니다. 하지만 10만 단위로 너무 깊이 들어가면 스택 오버플로가 나고, 그 제한은 파이썬보다 낮습니다. 또한 Pypy는 재귀에 굉장히 약합니다.
  • 두 개의 int를 나누면 float이 됩니다. int(a/b) 말고 a//b를 쓰는 것이 훨씬 안전합니다. 맨 위의 "부동소수점 자료형은 나타내는 수의 범위가 넓지만 ..."을 읽어보세요.

다른 언어

추가해야 할 내용을 제보받으면 추가하겠습니다.

댓글 (18개) 댓글 쓰기


sgchoi5 10달 전

수고하셨어요. 많은 분들이 읽어보셨으면 좋겠네



chemistrae03 10달 전

파이썬 list 시간 복잡도 링크에 다음 페이지를 올려주세요. https://wiki.python.org/moin/TimeComplexity


jh05013 10달 전

추가했습니다.


chemistrae03 10달 전

공식 자료에 따르면 마지막에 있는 원소를 제거할 때만 O(1) 이네요.


eric00513 10달 전

오 정말 수고하셨습니다.

제 생각에 C/C++ 부분에서 배열 할당을 너무 크게 하면 런타임 에러/메모리 초과와 같은 오류가 생길 수 있다는 내용이 있으면 좋을 것 같습니다.


eric00513 10달 전

왜냐하면, 이런 상황이 있었습니다.

https://www.acmicpc.net/problem/12850 문제에서 https://www.acmicpc.net/board/view/18640 상황이 있었습니다.


jh05013 10달 전

"시간/공간 복잡도를 계산해 보세요" 등으로 추가하겠습니다.


kqkdn 10달 전

좋은 글 감사합니다. 많은 도움이 될거같네요 ㅎㅎ


cs71107 8달 전

정말 수고하셨습니다. 많은 분들이 읽고 참고하시면 좋겠네요^^


djm03178 6달 전

자바 전체 재채점 이후 Scanner에 의해 메모리 초과가 나는 일이 많아졌습니다. 이에 대한 것도 있으면 좋을 것 같습니다.


jh05013 6달 전

어떻게 설명하는 것이 좋을까요?


djm03178 6달 전

"원인은 확실치 않지만 Scanner는 메모리를 많이 사용하는 것으로 보입니다. Scanner를 사용하는 것만으로도 메모리 초과가 발생할 수 있으니, 가능하면 BufferedReader를 사용하는 것이 좋습니다."


daniel060811 2달 전

이거 다 적으시면 안힘드시나요?


nill1024 1달 전

아직 초보라서 그런건진 모르겠지만 저는 개인적으로 틀린 원인의 60퍼 이상이 인덱스를 0으로 쓰는것때문에 발생하는 것 같아요. 인덱스가 1부터 들어가야 제대로 굴러가는 코드를 만들어놓고 인덱스 0부터 입력되는 경우가 많아서 항상 틀리는것같습니다


eric00513 1달 전

인덱스를 0부터 사용하면 보통 DP에서 -1이나 음수 인덱스를 참조하면 런타임 에러틀렸습니다를 받아서 저는 항상 배열 인덱스를 1부터 사용합니다. (벡터 같은 STL은 예외일 것 같아요.)


jh05013 1달 전

추가했습니다.