BOJ 101

BOJ 작동 원리

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

입출력 파일은 공개되지 않습니다. 예제는 데이터 중 극히 일부에 불과합니다. 예제는 자신의 코드가 맞을 것임을 확신하는 용도가 아니라, 입출력의 형식을 확인하고 문제의 설명을 검토하는 용도로 사용해야 합니다.

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

  • 구현을 어떻게 했는지 같은 건 채점 프로그램이 전혀 신경쓰지 않습니다. 그냥 답이 맞게 나오면 됩니다. 반대로, "틀렸습니다"가 나왔다는 건 무조건 답이 맞게 나오지 않는다는 뜻입니다.
  • 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 입력받으면 안 됩니다! 예제 형식 그대로 입력받으세요.
  • 줄바꿈이나 띄어쓰기 등을 마음대로 바꿔서 출력해도 안 됩니다! 예제 형식 그대로 출력하세요. 예외적으로, (대부분의 문제에서) 각 줄의 맨 끝에 공백을 넣어도 되고 안 넣어도 되며, 출력의 맨 끝에 줄바꿈을 넣어도 되고 안 넣어도 됩니다. 맨 끝을 제외한 나머지 줄바꿈은 넣어야 합니다.
  • 입력 조건을 코드에 넣을 필요는 없습니다. 예를 들어 "3 <= N <= 5000이다."라고 적혀 있으면, 이건 모든 입력 파일이 3 <= N <= 5000의 조건을 지킨다는 뜻입니다. 따라서 if(3 <= N && N <= 5000)을 따로 넣지 않아도 됩니다.
  • 입력을 다 받고 나서야 출력을 할 필요는 없습니다. 입력과 출력을 번갈아서 해도 됩니다. 근본적으로 입력 파일과 출력 파일은 분리되어 있습니다.

시간, 메모리 제한

시간 제한은 각 파일마다 따로따로 적용됩니다. 즉 시간 제한이 1초면 첫 번째 파일에 1초, 두 번째 파일에 1초, ..., 마지막 파일에 1초 이내가 걸려야 합니다. 채점 현황에서 볼 수 있는 "시간"은 가장 오래 걸린 파일에서의 구동 시간을 나타냅니다.

메모리 제한도 마찬가지인데, 한 순간에라도 지정된 메모리를 초과하면 안 됩니다. 채점 현황에서 볼 수 있는 "메모리"는 최대 메모리 사용량을 나타냅니다.

언어에 따라 시간이나 메모리가 초과되고도 정답을 받을 수 있는데, 그 언어가 정해진 시간/메모리 보너스를 받기 때문입니다. https://www.acmicpc.net/help/language

"첫 줄에 테스트케이스의 개수 T가 주어진다." 또는 "입력은 여러 개의 테스트케이스로 이루어져 있다." 같은 문제는 그 T개의 테스트케이스가 한 파일에 들어있다는 뜻입니다. 그런데 시간과 메모리 제한은 각 파일마다 따로따로 적용된다고 했으므로 주어진 시간 안에 한 파일에 들어있는 모든 테스트케이스가 돌아가야 합니다.

틀려야 되는 코드가 맞았다고 뜹니다

  • 시간 제한을 넘겼는데 맞았다고 뜬다면, 위의 "시간, 메모리 제한" 단락을 참조하세요.
  • 틀렸습니다, 런타임 에러 등이 떠야 하는데 맞았다고 뜬다면, 입출력 데이터가 충분히 강력하지 않은 경우입니다. 게시판의 오타/오역/요청 카테고리에 틀려야 하는 제출 번호, 반례 데이터와 정답을 게시해 주세요.

맞아야 되는 코드가 틀렸다고 뜹니다

  • 대부분은 그냥 착각입니다. 푼 사람이 많은 문제라면 특히 그렇습니다. 항상 자신의 잘못부터 의심하는 것이 바람직합니다.
  • 정말로 문제가 의심되신다면, (1) 우선 해당 문제의 질문 게시판을 검색해서 잘못된 데이터가 제보된 적 있는지 확인해 보세요. 없다면, (2) 데이터의 범위를 assert문을 걸어서 확실하게 확인해 보세요. assert를 사용하지 않고 올라왔던 데이터 수정 요청은 대부분 잘못된 요청이었습니다. assert문을 걸었는데도 런타임 에러가 뜨지 않는다면 그냥 착각일 가능성이 높습니다.

자주 틀리는 요인

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

기타 FAQ

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

A. 파이썬이 원래 극도로 느리기 때문에 제대로 된 풀이로도 시간초과가 날 수 있습니다. 그럴 때는 Pypy로 제출하시면 웬만한 문제들은 풀 수 있습니다. (꽤 어려운 문제들의 경우 이것도 안 될 수도 있습니다.)

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

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

Q. 문제 번호가 왜 1000부터 시작하나요?

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

Q. 하스켈 언어의 지원 계획이 있나요?

A. 채점에 문제가 있어서 해결될 때까지 보류됩니다. 이 글(링크)이 글(링크)을 참조해 주세요.

Q. 번역은 어떻게 하나요?

A. 번역 기능이 있었으나, 오역의 문제가 많이 발생하여 중단되었습니다.

Q. 출제는 어떻게 하나요?

A. https://www.acmicpc.net/help/problem-add

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


댓글 (30개) 댓글 쓰기


djm03178 6년 전

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

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


jh05013 6년 전

감사합니다.


jwvg0425 6년 전

퍄퍄 너무 멋져요


godmoon00 6년 전

좋은글 감사합니다!


djm03178 6년 전

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

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

jh05013 6년 전

추가했습니다.


djm03178 6년 전

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

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


jh05013 6년 전

추가했습니다.


YunGoon 6년 전

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

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


djm03178 6년 전

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

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


djm03178 6년 전

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

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


jh05013 6년 전

추가했습니다.


djm03178 6년 전

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


jh05013 6년 전

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


sgchoi5 6년 전

너무 좋은 글이네요


djm03178 6년 전

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


jh05013 6년 전

추가했습니다.


djm03178 6년 전

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


jh05013 6년 전

추가했습니다.


moonhi123 5년 전

감사합니다!


veydpz 5년 전

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


rlaeogus890 5년 전

감사합니다.


codenstory 4년 전

읽었습니다.


ttppggnnss 4년 전

정말 좋은 글인 것 같습니다 감사합니다


hakiabuji 3년 전

처음 이 사이트에 오시는 초심자들이 이와 같은 기초적인 글들은 미리 확인할 수 있도록

공지나 배너등으로 안내를 해주심이 좋을 것 같습니다.

저도 이글은 사이트 알게된지 몇주나 지나고 읽게 되었어요ㅎ


kano2812 3년 전

동감합니다. 정말 좋은 글인데 이 사이트를 이용한지 1달이 지나서야 이 글을 일게 됐네요.


whqkrkt04 3년 전

이제 RTE 종류가 공개되므로, 런타임에러 메시지 관련 문단이 수정되어야 할 것 같습니다.


jh05013 3년 전

답변 내용이 별로 마음에 안 들어서 그 김에 수정하려고 합니다. 그 전까지 해당 내용은 삭제해 두겠습니다. 감사합니다.


klop9090 2년 전

없습니다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋ


goodcoding 1년 전

좋은정보 감사합니다