BOJ 101

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

가장 중요한 팁

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

BOJ 작동 원리

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

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

  • 시간 제한은 각 파일마다 따로따로 적용됩니다. 즉 시간 제한이 1초면 첫 번째 파일에 1초, 두 번째 파일에 1초, ..., 마지막 파일에 1초 이내가 걸려야 합니다. 채점 현황에서 볼 수 있는 "시간"은 가장 오래 걸린 파일에서의 구동 시간을 나타냅니다.
  • 메모리 제한도 마찬가지인데, 한 순간에라도 지정된 메모리를 초과하면 안 됩니다. 채점 현황에서 볼 수 있는 "메모리"는 최대 메모리 사용량을 나타냅니다.
  • "첫 줄에 테스트케이스의 개수 T가 주어진다." 또는 "입력은 여러 개의 테스트케이스로 이루어져 있다." 같은 문제는 그 T개의 테스트케이스가 한 파일에 들어있다는 뜻입니다. 그런데 시간과 메모리 제한은 각 파일마다 따로따로 적용된다고 했으므로 주어진 시간 안에 한 파일에 들어있는 모든 테스트케이스가 돌아가야 합니다. 또한 입력 스트림과 출력 스트림은 별개이므로 케이스를 받을 때마다 출력해도 되고, 전부 받은 뒤 전부 출력해도 되고, 심지어 받기 전에 출력해도 (???) 됩니다. 하지만 출력 자체의 순서는 지켜야 합니다.
  • 언어에 따라 시간이나 메모리가 초과되고도 정답을 받을 수 있는데, 그 언어가 정해진 시간/메모리 보너스를 받기 때문입니다. https://www.acmicpc.net/help/language
  • 채점 현황의 "컴파일 에러"를 누르면 어디서 에러가 났는지 볼 수 있습니다. 컴파일 에러일 경우에만 가능합니다.

기타 팁

  • 채점 도움말 https://www.acmicpc.net/help/judge
  • 도움이 필요한 당신에게 https://www.acmicpc.net/blog/view/45 - 여기에는 답변자가 쉽게 이해할 수 있는 질문을 올리는 방법이 제시되어 있습니다.
  • 게시판에서 글쓰기를 누르면 카테고리가 "자유"로 설정됩니다. 그래서 자유 카테고리로 질문글이 올라오는 경우가 종종 보입니다. 카테고리를 "질문"으로 바꾸면 문제 번호와 소스코드를 적는 칸이 나옵니다.
  • 입출력이 느리면 그것만으로도 시간초과가 날 수 있습니다. 이 때는 빠른 입출력을 사용해야 하는데,
    1. C++의 경우 scanf와 printf를 하거나, cin.tie(NULL)과 sync_with_stdio(false)를 한 뒤 cin/cout만 사용하는 방법이 있습니다. 두 번째 방법을 쓸 때는 절대 scanf/printf와 섞어 쓰면 안 됩니다! 그리고 endl은 개행과 함께 flush까지 하느라 매우 느리기 때문에 '\n'으로 대체해야 합니다. 아래에 자세한 설명이 있습니다.
  • 1.1. 후자가 더 빠릅니다. https://www.acmicpc.net/blog/view/56
    1. Java의 경우 BufferedReader와 BufferedWriter가 있습니다. (Java에 대해선 자세히 모르니 여기에도 주의할 점이 필요하면 제보해 주세요.)
    1. Python의 경우 sys.stdin.readline이 input을 대체할 수 있습니다. 단, 개행문자를 같이 읽으므로 스트링 하나를 입력받아야 될 경우 .rstrip()을 꼭 해 줍시다!
  • 3.1. 출력은 그냥 print를 써도 무난하지만, Pypy 2 한정으로 조금 더 빠른 출력도 가능합니다. http://codeforces.com/blog/entry/47667 코드포스에서는 BOJ와 달리 이것의 사용이 매우 큰 차이를 보이는 것 같습니다. 애초에 코드포스에서 파이썬을 쓰는 것 자체가 시간 초과의 원인입니다.
  • 입력 조건을 코드에 넣을 필요는 없습니다. 예를 들어 "3 <= N <= 5000이다."라고 적혀 있으면 모든 입력 파일이 3 <= N <= 5000의 조건을 지킨다는 뜻이고, if(3 <= N && N <= 5000)을 따로 넣지 않아도 됩니다. 조건을 지키지 않는 파일이 있음을 발견하셨다면 파일이 잘못된 것이므로 게시판에 문제 수정 요청을 쓰면 운영자님이 고쳐 주십니다.
  • 배열의 크기는 넉넉하게 잡는 것을 추천드립니다. 예를 들어 "수열의 길이는 10만 이하이다."라고 해서 int A[100000]을 잡았는데 for(int i=1; i<=100000; i++)을 한다든지, "문자열의 길이는 10만 이하이다."라고 해서 char A[100000]을 잡았는데 널 문자때문에 사실 100001개가 필요하다든지... 그래서 [100055]처럼 실제 최대값보다 조금 많이 잡으면 인덱싱 오류가 날 가능성이 줄어듭니다.
  • 알고리즘이나 내부 함수의 시간복잡도를 숙지합시다. 예를 들어 파이썬의 list.pop(0)은 O(n)이 걸립니다. BFS에서 이걸 쓰면 절대 안 됩니다. 그리고 모든 파일에 대해서 시간 안에 돌아가야 합니다. 퀵소트처럼 n <= 100000 기준 평균 시간복잡도가 O(nlogn)이더라도 최악의 시간복잡도가 O(n^2)이면 시간초과가 날 위험이 있습니다.
  • '\n'으로 입력의 끝을 검사할 경우 문제가 생길 수 있습니다. 지금은 데이터의 끝에 '\n'가 반드시 들어오도록 되어 있지만, 오래된 데이터는 '\n'가 없는 경우가 있습니다. getchar나 fgets로 입력받을 때는 '\n'과 EOF를 모두 검사하는 것이 안전합니다.
  • BFS는 큐에서 뺀 다음이 아닌, 큐에 넣을 때 방문 체크를 해야 중복 방문이 일어나지 않습니다.

C++의 빠른 입력

위에서 endl 및 cin.tie와 sync_with_stdio에 대한 말을 했는데, 자세하게 설명하면 이렇습니다.

  • endl은 개행문자를 출력할 뿐만 아니라 출력 버퍼를 비우는 역할까지 합니다. 그래서 출력한 뒤 화면에 바로 보이게 할 수 있는데, 그 버퍼를 비우는 작업이 매우 느립니다. 게다가 온라인 저지에서는 화면에 바로 보여지는 것은 중요하지 않고 무엇이 출력되는가가 중요하기 때문에 버퍼를 그렇게 자주 비울 필요가 없습니다. 그래서 endl을 '\n'으로 바꾸는 것만으로도 굉장한 시간 향상이 나타납니다. 현재 (2018년 1월 25일) N 찍기 (최대 10만 줄) 문제를 endl로 내면 시간초과가 나고, '\n'로 내면 12ms로 통과됩니다.
  • cin.tie(NULL)은 cin과 cout의 묶음을 풀어 줍니다. 기본적으로 cin으로 읽을 때 먼저 출력 버퍼를 비우는데, 마찬가지로 온라인 저지에서는 화면에 바로 보여지는 것이 중요하지 않습니다. 입력과 출력을 여러 번 번갈아서 반복해야 하는 경우 필수적입니다.
  • ios_base::sync_with_stdio(false)는 C와 C++의 버퍼를 분리합니다. 이것을 사용하면 cin/cout이 더 이상 stdin/stdout과 맞춰 줄 필요가 없으므로 속도가 빨라집니다. 단, 이 상태에서 scanf와 printf를 사용하면 안 됩니다.
  • 위에 링크한 "입력 속도 측정" 글을 보면 mmap, fread, getchar가 있긴 한데, 굳이 이것까지 쓸 필요는 없습니다.

기타 FAQ

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

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

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

댓글 (17개) 댓글 쓰기


djm03178 1달 전

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

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


jh05013 1달 전

감사합니다.


jwvg0425 1달 전

퍄퍄 너무 멋져요


godmoon00 1달 전

좋은글 감사합니다!


djm03178 1달 전

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

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

jh05013 1달 전

추가했습니다.


djm03178 1달 전

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

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


jh05013 1달 전

추가했습니다.


yungoon 1달 전

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

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


djm03178 1달 전

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

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


djm03178 1달 전

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

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


jh05013 1달 전

추가했습니다.


djm03178 1달 전

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


jh05013 1달 전

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


sgchoi5 1달 전

너무 좋은 글이네요


djm03178 4일 전

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


jh05013 4일 전

추가했습니다.