PS 했던 블로그

BOJ의 질문 게시판 공지사항에서는 "몇 %에서 틀렸다는 내용을 올리지 마세요"라고 적혀있지만, 개인적으로는 몇 %에서 틀렸는지는 때때로 좋은 힌트가 된다고 생각합니다. 그 중 가장 영양가 높은(?) 것이 바로 100%에서 틀리는 경우입니다. 채점 프로그램의 대략적인 동작 방식은 50%에서 틀리는 것의 의미 글에서 설명했으니 여기서는 100%에서 틀리는 것이 무슨 의미를 가지는지에 대해서만 알아보겠습니다. 모든 경우에 해당되는 것은 아니지만, 대부분의 경우에 유의미한 힌트를 줍니다. BOJ에서 데이터를 정렬하는 방법에는 몇 가지가 있는데, 그 중 가장 일반적인 기본값은 데이터의 크기의 내림차순입니다. BOJ 자체에서 여는 대회 문제들을 제외하고, 출처가 따로 없거나 외부 대회가 출처인 문제들의 경우 대부..

Java에서 자주 보이는, 무한 디버깅을 유발하는 사례입니다. 작은 케이스에서 아무리 해도 반례가 안 나오기 때문에 고생하게 되는 경우가 많습니다. Integer는 primitive type 인 int를 객체의 형태로 편하게 표현하기 위한 wrapper 클래스입니다. primitive type은 Object로서 다룰 수 없기 때문에 언어 차원에서 특별히 이러한 클래스를 제공해주는데, Integer와 int 사이의 형변환이 자동으로 이루어지기 때문에 둘을 같은 것처럼 쓰더라도 보통은 문제가 생기지 않습니다... ...만, 각별히 신경써야 할 부분이 하나 있는데, 바로 Integer 객체끼리 비교를 해야 하는 경우입니다. 다음의 케이스를 확인해 봅시다. https://ideone.com/XjogFw publ..

게임 개발 등 실무 프로그래밍에서는 부동소수점 자료형으로 float (4바이트 부동소수점 자료형)를 쓰는 일이 많습니다. 많은 경우 float는 적당히 쓸만한 정확도를 보여주고, 자료형의 크기가 작아 속도가 빠르기 때문에 자주 쓰이는 편입니다. 하지만, PS에서는 절대 float를 권장하지 않습니다. 이유는 간단합니다. PS 문제들은 칼같은 정확도를 요구하기 때문입니다. 대부분의 문제에서는 조금의 오차도 허용하지 않으며, 오차를 허용하는 문제에서도 그 오차가 매우 작을 것을 요구하는 것이 PS 문제입니다. 실수형을 써야 하는 문제에서 많은 경우 "절대/상대 오차는 $10^{-9}$까지 허용한다."와 같이 극도로 작은 오차만을 허용하는데, $10^{-9}$라는 것은 적어도 유효숫자 9자리가 정확해야 한다는..

이 글은 제가 처음 프로그래밍을 접했던 약 15년 전부터 아직까지도 끊임없이 보고 있는 것에 대한 이야기입니다. 결론부터 말해서, C 표준에서 stdin의 버퍼를 비워주는 라이브러리는 없습니다. 흔히 fflush(stdin), rewind(stdin)을 사용하여 버퍼를 비우는 기법이 알려져있지만 이는 어디까지나 특정 라이브러리 (제가 아는 한에서는 Visual Studio만)에서 확장 기능으로 그런 사용법도 제공할 뿐이지, 표준상에서는 stdin에 대해 아예 사용이 안 되는 함수들입니다. 보통 scanf로 정수를 입력받고 다음 줄 전체를 fgets 등으로 읽어오고 싶을 때, 정수 뒤에 남아있는 공백을 지우고 싶어서 많이 사용하게 될 건데, 이걸 fflush나 rewind 등으로 지우려고 하면 안 됩니다...

제곧내 는 아니고, 빌드하는 환경(컴파일러 종류 및 버전, 언어 버전 등)에 따라 허용하는 문법 / 확장 기능 / 라이브러리의 종속성 등이 다르기 때문에 직접 컴파일 했을 때 문제가 없었더라도 제출하면 컴파일 에러를 받게 될 수 있습니다. 이 경우 BOJ에서는 채점 현황에 나타난 "컴파일 에러" 문구를 클릭하면 자세한 에러 메시지를 보여줍니다. 채점 환경에 따라 달라질 수 있다고는 했으나, 대개의 경우는 자신의 코드가 표준을 지키지 않고 특정 컴파일러에서는 제공하는 확장 기능이나 확장 라이브러리를 사용했거나, 헤더 파일이 내부적으로 종속성을 가져서 운 좋게 컴파일이 된 경우입니다. 예를 들어 일부 환경 (Visual Studio 2017)에서는 아래와 같은 코드가 컴파일이 될 수도 있으나, #includ..

C나 C++에서 char로 된 배열에 문자열의 형태로 입력을 받는 경우 가장 먼저 생각해야 할 것은 바로 널 문자 ('\0')입니다. 널 문자는 문자열의 끝을 알려주는 특별한 문자로, char 문자열에 대한 모든 문자열 관련 라이브러리는 널 문자를 통해 문자열의 끝을 인지합니다. 이는 입력이나 출력 시에도 예외가 아닙니다. 모든 char 문자열 입력 함수 (scanf, fgets, cin, getline 등)를 통해 char 문자열을 입력받으면 이 함수들은 자기가 알아서 문자열의 끝에 널 문자를 추가해줍니다. 그 말은 길이가 $N$인 문자열을 입력받는다면, 입력 함수들이 실제로 사용하는 배열의 크기는 $N+1$이라는 뜻입니다. 예를 들어, 문자열의 길이가 최대 100만인 문제에서 다음과 같이 입력을 받으..

문제를 풀다가 '틀렸습니다'가 나오면 대부분의 사람들은 매우 답답할 것입니다. 아무리 봐도 맞는 코드인데, 예제는 맞고, 어디 반례가 없을까 찾게 되는 것이 매우 일반적입니다. 하지만 놀라운 사실이 있습니다. 반례를 찾는 질문들 중 상당히 높은 비율에서 예제가 반례로 나타난다는 것입니다. 예제를 테스트 해보는 것은 기본이기에 단순히 깜빡하고 안 해본 예제가 있어서인 경우는 사실 그렇게 많지는 않습니다. 대개는 예제를 해보고도 그게 반례라는 것을 깨닫지 못하는 경우입니다. 자주 보이는 사례들을 정리해 보았습니다. 출력이 100% 일치하지 않는 경우: 채점 프로그램은 출력하는 한 글자 한 글자에 매우 민감합니다. 출력은 언제나 요구한 것을 글자 단위로 정확하게 출력해야 합니다 (일부 예외 제외). 수를 공백..

C/C++에서 strlen은 char의 연속으로 이루어진 기초적인 형태의 문자열의 길이를 구해주는 역할을 합니다. 문자열의 구조를 몰라도 strlen만 있으면 손쉽게 길이를 알 수 있으니 참으로 편리한 함수이지만, 구조를 모르고 아무 곳에나 사용하면 다음과 같은 문제를 겪게 될 수 있습니다. 문자열을 다루는 문제에서 "문자열의 모든 문자를" 하나씩 전부 확인해야 하는 경우가 있습니다. 이 경우 가장 일반적인 방법은 아래와 같이 for 루프를 도는 것입니다. char str[1000001]; scanf("%s", str); for (int i = 0; i < str의_길이; i++) { str[i]에_대한_연산; } str의 최대 길이가 100만인 문제에서, str의_길이를 구하기 위해 다음과 같이 코드를..

BOJ에서 문제를 풀다 보면 50%에서 오답을 받는 경우를 심심찮게 볼 수 있습니다. 일반적으로 이런 경우는 문제가 "입력은 여러 개의 테스트 케이스로 이루어져 있다"와 같은 형식일 때입니다. 언뜻 보면 퍼센트가 반이나 올라갔으니까, 반은 맞은 건가? 하고 생각하기 쉽습니다. 하지만 대개의 경우, 진실은 그렇지 않습니다. 이게 무엇을 의미하는지 이해하려면 우선 BOJ의 채점 원리를 알아야 합니다. 자세한 동작 원리는 https://help.acmicpc.net/judge/info 에 설명되어 있으니, 여기에서는 짧게 필요한 것만 요약하겠습니다. BOJ 채점 프로그램에서 보여주는 %는 하나의 데이터에 대해 프로그램이 실행하는 단계와 그 실행 결과에 대한 판정을 내리는 2개의 단계로 나누어져 있습니다. 예를..

코드는 제출했던, 틀렸던 바로 그 코드 전체가 온전하게 있어야 답변을 원활하게 할 수 있습니다. 항목별로 강조하자면, 오답을 받은 코드를 한 글자의 수정도 없이 전체를 그대로 가져와야 합니다. 이는 질문에서 이야기하고자 하는 부분이 특정 함수나 특정 문장에 국한된 것이라 하더라도, 또는 딱 한 부분을 고쳤을 때 채점 결과가 달라지는 상황이라도 예외가 아닙니다. 이유는 다음과 같습니다. 가장 확실하고 쉬운 디버깅 방법은 답변자가 그 코드를 복사해서 로컬에 넣고 직접 돌려보는 것입니다. 그런데 코드 전체가 없으면 애초에 이를 테스트하는 것 자체가 매우 번거롭습니다. 눈으로만 디버깅을 하거나, 아니면 임의의 테스트 코드를 직접 작성해야만 합니다. 직접 제출해보기 위해서라도 원본 코드 그대로는 반드시 필요합니다..