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
  • 채점 현황의 "컴파일 에러"를 누르면 어디서 에러가 났는지 볼 수 있습니다. 컴파일 에러일 경우에만 가능합니다.

자주 틀리는 요인

너무 많아져서 아래 글로 분리했습니다. https://www.acmicpc.net/blog/view/70

기타 FAQ

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

A. 원래 디버깅은 스스로 해야 가장 큰 도움이 됩니다. 그리고 테스트케이스를 볼 수 있게 하면 악용해서 입력과 출력을 짝짓는 것만으로 문제를 통과할 수 있습니다. 그래서 테스트케이스 확인 기능은 없으며, 앞으로도 없을 예정입니다. 런타임 에러 메시지를 볼 수 있게 하면 악용해서 데이터를 얻어낼 수 있으므로 런타임 에러 메시지는 볼 수 없으며, 앞으로도 볼 수 없을 예정입니다.

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

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

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

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

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

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

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

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

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

댓글 (22개) 댓글 쓰기


djm03178 11달 전

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

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


jh05013 11달 전

감사합니다.


jwvg0425 11달 전

퍄퍄 너무 멋져요


godmoon00 11달 전

좋은글 감사합니다!


djm03178 10달 전

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

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

jh05013 10달 전

추가했습니다.


djm03178 10달 전

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

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


jh05013 10달 전

추가했습니다.


YunGoon 10달 전

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

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


djm03178 10달 전

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

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


djm03178 10달 전

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

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


jh05013 10달 전

추가했습니다.


djm03178 10달 전

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


jh05013 10달 전

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


sgchoi5 10달 전

너무 좋은 글이네요


djm03178 9달 전

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


jh05013 9달 전

추가했습니다.


djm03178 9달 전

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


jh05013 9달 전

추가했습니다.


moonhi123 8달 전

감사합니다!


veydpz 8달 전

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


rlaeogus890 7달 전

감사합니다.