BOJ 101

BOJ 질문 게시판에서 활동하면서 "이건 모두가 알아야 할 것 같다"라고 생각한 것들을 적어 보려 합니다.

가장 중요한 팁

  • 채점 데이터에는 예제만 있는 게 아니라 우리에게 공개되지 않는 추가적인 데이터가 많이 준비되어 있습니다. 예제 입출력은 "예를 들어 이런 입력을 줄 것이고 이 때는 이렇게 출력해야 한다"라는 뜻이지, "이게 잘 돌아가면 대충 맞는 코드일 것이다"라는 뜻이 절대 아닙니다!! 그러니 틀렸다고 바로 질문을 올리지 말고 적어도 여러 종류의 입력을 직접 만들어서 넣어 봅시다. 아무렇게나 만들어서 몇 번 넣으면 반례가 나오는 질문이 많이 있습니다.
  • 입력 범위를 봅시다. n이 1,000,000,000까지 가는 문제에서 1부터 n까지 루프를 돌리면 당연히 안 되고, 배열 크기가 10,000까지 가야 되는데 1,000까지 잡으면 당연히 안 됩니다...
  • 질문 게시판을 봅시다. 제출한 사람이 많은 문제일 수록 여러분과 똑같은 질문이 들어있을 가능성이 높아집니다.

BOJ 작동 원리

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

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

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

자주 틀리는 요인

  • freopen 지우세요. 배열 초기화 하세요. (C/C++)
  • main의 리턴값이 0이 아니면 런타임 에러가 납니다. 다른 값이 리턴되는 것은 비정상적인 종료를 의미합니다. (C/C++)
  • 전역배열의 크기는 넉넉하게 잡는 것을 추천드립니다. (C/C++, Java) 예를 들어 "수열의 길이는 10만 이하이다."라고 해서 int A[100000]을 잡았는데 for(int i=1; i<=100000; i++)을 한다든지, "문자열의 길이는 10만 이하이다."라고 해서 char A[100000]을 잡았는데 널 문자때문에 사실 100001개가 필요하다든지... 그래서 [100055]처럼 실제 최대값보다 조금 많이 잡으면 인덱싱 오류가 날 가능성이 줄어듭니다.
  • Scanner는 하나만 만드세요. (Java)
  • 파이썬으로 재귀를 너무 깊이 들어가지 마세요. (Python) 기본 설정상 1000이 최대입니다. sys.setrecursionlimit으로 최대 깊이를 늘리거나, (메모리가 너무 부족한 문제일 경우) 아예 재귀 없는 풀이를 생각해 보세요.
  • \b는 하나의 문자일 뿐, 정말로 출력했던 문자를 도로 지우는 문자가 아닙니다. 단지 화면에 내보낼 때만 지운 것처럼 보이게 할 뿐입니다. 출력했던 문자는 지울 수 없습니다.
  • 부동소수점 자료형으로 정수를 저장하면 안 됩니다. 넓은 범위의 수를 나타내기 위해 정확도를 희생한 자료형입니다. 무슨 수든 정확하게 나타내는 마법의 자료형이 아닙니다.
  • 입출력이 느리면 그것만으로도 시간초과가 날 수 있습니다. https://www.acmicpc.net/problem/15552
  • '\n'으로 입력의 끝을 검사할 경우 문제가 생길 수 있습니다. 지금은 데이터의 끝에 '\n'가 반드시 들어오도록 되어 있지만, 오래된 데이터는 '\n'가 없는 경우가 있습니다. getchar나 fgets로 입력받을 때는 '\n'과 EOF를 모두 검사하는 것이 안전합니다.
  • 널 문자는 하나의 문자로 취급되며, 널 문자와 공백은 다릅니다. 일부 컴퓨터에서 널 문자를 출력할 때 빈 칸이 출력되는데, 실제로는 엄연히 공백과 다른 하나의 문자입니다. 그래서 널 문자를 출력하지 말아야 되는 데 / 공백을 출력해야 되는데 널 문자를 출력하면 오답입니다.
  • 알고리즘이나 내부 함수의 작동 원리와 시간복잡도를 숙지합시다.
    1. C/C++: strlen은 O(N)입니다. memset은 0과 -1만 가능합니다. https://www.acmicpc.net/board/view/23217#comment-40375
    1. Java: Linkedlist의 x번째 원소 찾기는 O(x)입니다.
    1. Python: list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 O(N)입니다. 특히 list를 큐처럼 쓰면 절대로 안 됩니다. collections.deque를 써야 합니다.
    1. 대부분의 언어: 배열 기반의 리스트 (C++ vector, string, Java ArrayList, String, Python list, str, ...)의 중간에 뭔가를 끼워넣고 빼는 건 O(N)입니다.
    1. 알고리즘: DFS는 절대로 최단거리를 구해 주지 않습니다. 최단거리는 BFS입니다.
    1. 알고리즘: 퀵소트를 직접 구현하면 O(N^2)이 걸리는 데이터를 손쉽게 만들 수 있습니다. 그냥 내장된 정렬 함수를 쓰세요.
    1. 알고리즘: BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다. BFS 문제에서 메모리 초과가 나면 이것부터 의심해 보시면 됩니다.

기타 FAQ

Q. 어느 케이스에서 틀렸는지 / 어디서 런타임 에러가 났는지는 볼 수 없나요?

A. 이걸 볼 수 있게 하면 악용해서 데이터를 얻어내거나, 출력이 YES/NO인 문제의 경우 입력과 출력만 짝지어서 풀 수 있습니다. 그래서 테스트케이스 확인 기능은 없으며, 앞으로도 없을 예정입니다...만 (2018년 4월) 최근에 일부 문제에 한해 공개해도 좋겠다고 하신 적이 있습니다. 게시판에서 반례를 찾으라고 했지만 사실 디버깅은 스스로 하는 게 가장 좋습니다.

Q. 파이썬으로 OOOO번을 시간 내에 못 푸나요?

A. 파이썬이 원래 극도로 느리기 때문에 제대로 된 풀이로도 시간초과가 날 수 있습니다. 그 대신 Pypy로 내면 거의 모든 문제를 풀 수 있습니다. (이 글을 쓰고 있는 저는 파이썬과 Pypy만으로 약 2400문제를 풀었습니다.)

Q. 왜 코인 수익이 안 들어오나요?

A. "실수익이 200코인 이상이 되어야 정산이 가능합니다. 접수는 매달 10~15일 사이에 자동으로 진행되며, 정산은 매달 25일에 진행됩니다. 휴일인 경우에는 다가오는 평일에 정산이 진행됩니다." https://www.acmicpc.net/coin/pay

Q. 문제의 정답 비율은 어떻게 계산되나요?

A. https://www.acmicpc.net/problem/15595

Q. 계정 연동에 앳코더는 추가될 수 없나요?

A. 앳코더 API가 없어서 안 된다고 합니다.

Q. 모네로 마이닝이 뭔가요?

A. https://www.acmicpc.net/board/view/22282

추후 내용이 추가될 수 있습니다.

댓글 (22개) 댓글 쓰기


djm03178 7달 전

정말 꼭 필요하다 싶은 것 적어주셨네요. 수고하셨습니다.

앞으로 링크 많이 뿌릴게요.


jh05013 7달 전

감사합니다.


jwvg0425 7달 전

퍄퍄 너무 멋져요


godmoon00 7달 전

좋은글 감사합니다!


djm03178 7달 전

이 내용들 추가해주시면 좋을 거 같습니다.

  1. cout에서 endl이 매우 느리다는 것
  2. 퀵소트를 직접 구현하는 건 최악의 경우에 시간 복잡도 / 스택 오버플로 문제가 있고, 이런 데이터가 입력 데이터에 있을 가능성이 매우 높다는 것

jh05013 7달 전

추가했습니다.


djm03178 7달 전

이것도 자주 보이는 질문이네요.

예전에 입력된 데이터들의 경우 마지막에 eoln이 없어서 getchar나 fgets 등으로 입력을 받을 시 '\n'으로 끝을 체크하려는 경우 문제가 생기는 일이 종종 있는데 이에 대한 설명도 있으면 좋을 거 같습니다.


jh05013 7달 전

추가했습니다.


yungoon 7달 전

채점 현황에서 볼 수 있는 "메모리"는 최대 메모리 사용량을 나타냅니다.

입력되는 데이터의 개수가 최대 10만일 경우 int arr[100000]으로 선언하는 경우와 개수를 먼저 n으로 입력받고 int arr[n]으로 선언하는 경우가 서로 메모리가 다른 것으로 보아 최대 메모리 사용량이 아닌 평균 메모리 사용량인 걸로 추측하고 있었는데, 제가 잘못 생각하고 있는 건가요?


djm03178 7달 전

운영체제가 메모리를 할당해주는 방식은 좀 복잡합니다. n바이트의 크기를 요청했다고 해서 꼭 n바이트만 할당주는 것이 아니라, 실제로는 페이지 단위로 듬뿍듬뿍 할당해주고 이후 추가 메모리 할당 요청이 왔을 때 새로 할당하지 않고 기존에 할당해 준 페이지 내의 다른 공간을 활용하게끔 하기도 합니다. 이렇다 보니 현재 여건에 따라서 메모리가 할당되는 구조가 달라질 수도 있고, 동적으로 크기가 정해지는 상황이라면 더욱 그렇습니다.

그리고 확인해 본 결과 가변 크기 배열은 애초에 스택 영역이 아닌 힙 영역에 할당되는 것으로 보입니다. 지역 변수로 배열을 선언하면 스택 영역에 메모리 할당이 이루어지는데 가변 크기 배열은 컴파일 시간에 그 크기가 정해지지 않았기 때문에 스택에 할당을 할 수 없는 것으로 보입니다. 스택 영역과 힙 영역에서 메모리가 할당되는 방식도 전혀 다르기 때문에 꼭 n이 10만이라고 해서 int arr[100000] 을 한 것과 같은 양의 메모리가 할당된다는 법은 없습니다.


djm03178 7달 전

소수점 수를 문제 요구대로 정확하게 출력하지 않고 맞왜틀 하시는 분들도 있는데 맨 윗 부분에 추가하면 좋을 거 같습니다.

예를 들면 1과 1.0이 다르고, 4.500 으로 출력해야 할 것을 4.5로 출력하면 안 된다는 것 등이요.


jh05013 7달 전

추가했습니다.


djm03178 7달 전

채점 환경의 속도도 대략적으로 안내하는 게 어떨까요? 아래에서 두 번째 항목에 간단하게 어느 정도까지가 1초 내에 통과될 수 있는지 써두면 좋을 것 같습니다. 10~20억 정도를 돌리면서 왜 시간 초과 나는지 모르겠다고 하는 질문도 많이 보이네요.


jh05013 7달 전

사실 "달팽이는 올라가고 싶다" 사례처럼 단순 연산은 20억 번 할 수 있는 것 같아서 어느 정도라고 해야 될 지 잘 모르겠습니다. "시간복잡도 대입" 같은 말로 추가하겠습니다.


sgchoi5 6달 전

너무 좋은 글이네요


djm03178 6달 전

질문 게시판에 글 올리는 법도 한 줄로 간단히 설명하면 어떨까요? 카테고리 설정, 문제 번호 설정, 코드 올리는 칸에 대해서요.


jh05013 6달 전

추가했습니다.


djm03178 5달 전

"공백 문자는 ' '로 출력해야 합니다." 도 추가하면 어떨까요? 널 문자도 하나의 문자로 취급되며 printf("%c") 등으로 출력할 시 오답 처리가 된다는 것을 모르시는 분이 많은 것 같습니다.


jh05013 5달 전

추가했습니다.


moonhi123 4달 전

감사합니다!


veydpz 4달 전

이거 이제서야 봤네요... 정말 멋진 글입니다. :fan:


rlaeogus890 4달 전

감사합니다.