PS 했던 블로그

흔히 C++에서 입출력을 빨리 하는 기법이라고 해서 ios::sync_with_stdio(false); 라는 문장을 main 함수 상단에 넣곤 합니다. 그런데 이 문장이 왜 입출력을 빠르게 할까요? 그 답은 함수 이름에 직설적으로 들어있습니다. sync(hronize) with stdio, 말 그대로 stdio와 동기화를 한다는 뜻의 이름인데, 여기에 인자를 false를 주었으니, 동기화를 더 이상 안 하겠다는 의미입니다. 쉽게 말해서, ios (C++의 입출력 함수들)는 더 이상 stdio를 신경쓰지 않고 자기 갈 길을 가기 때문에 C++ 입출력 함수들의 속도가 향상될 수 있는 것입니다. 구체적으로는 이제 cin, cout 등이 자기 자신만의 입출력 버퍼를 두고 미리 입력받은 내용을 모아놓는다거나, 출..

C/C++에서 문자열이란 초보자가 다루기가 상당히 까다로운 편에 속합니다. 정확한 사용법을 숙지하지 못하고 쓰다가 실수를 하는 일도 굉장히 잦습니다. 대표적인 사례가 바로 문자열의 끝과 관련한 것들입니다. 문자열의 끝에는 항상 널 문자가 들어갑니다. 글에서 다루었듯이 일반적인 char로 나타낸 문자열의 끝은 항상 널 문자 ('\0')입니다. C++의 std::string과 같은 경우에도 문자열의 마지막 글자의 다음 인덱스에 접근할 경우 널 문자를 반환할 것이 표준에 명시되어 있습니다. 다시 강조하지만 널 문자는 문자열로서의 마지막을 나타냅니다. 달리 말하면 널 문자를 넘어선 부분은 문자열의 일부가 아닙니다. 흔히 문자열을 입력받기 위해 다음과 같은 고정된 크기의 배열을 선언하고 입력을 받습니다. char..

BOJ에서는 Python 3를 위한 제출 언어를 두 가지 제공하고 있습니다. 기본 CPython 인터프리터를 사용하는 Python 3와, 일반적으로 훨씬 빠른 속도를 자랑하는 인터프리터인 PyPy3입니다. 이 글에서 하고 싶은 말이 벌써 나왔습니다. PyPy3는 Python 3보다 일반적으로 훨씬 빠르므로, 문제도 PyPy3로 풀기를 권장합니다. 공식 홈페이지의 언급에 의하면 PyPy는 CPython에 비해 평균적으로 4.8배가 빠르다고 합니다. 모든 종류의 벤치마킹에서 항상 빠른 것은 아니지만, 적어도 PS 중에는 Python 3을 굳이 쓸 이유가 저는 웬만하면 없다고 생각합니다. 시간 보너스도 3배 + 2초로 동일하게 주어지는데 일부러 느린 것을 쓸 필요가 없습니다. 처음부터 언어를 PyPy3로 고정..

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% 일치하지 않는 경우: 채점 프로그램은 출력하는 한 글자 한 글자에 매우 민감합니다. 출력은 언제나 요구한 것을 글자 단위로 정확하게 출력해야 합니다 (일부 예외 제외). 수를 공백..