PS 했던 블로그

PS를 하다 보면 문자열로 저장된 수를 정수형으로 바꾸고 싶은 경우가 종종 있습니다. 이를 위해서 편하게 사용할 수 있는 C 라이브러리 함수가 하나 있는데 바로 atoi입니다. 단, 어떤 라이브러리든 마찬가지이지만 사용할 때에는 그 사용법을 정확히 알고 사용해야 하는데 atoi에도 초보자들이 매우 자주 하는 실수가 있습니다. atoi에는 절대로, 절대로 하나의 char 변수의 주소값을 넘겨서는 안 됩니다. atoi가 const char *를 인자로 받기 때문에 얼핏 보면 char 변수 앞에 &를 붙여서 그 주소를 넘겨주면 자료형 문제가 해결되어 사용할 수 있을 것처럼 보입니다. 하지만 그건 올바른 해결 방법이 아닙니다. atoi는 문자가 아니라 문자열을 인자로 받는 함수이기 때문입니다. 문자열의 끝에는 ..

C/C++이 어려운 이유 중 하나로 디버깅이 어렵다는 점을 들 수 있을 것입니다. 직접적으로 기계어로 번역되어 실행되는 특성상 코드에 어떤 문제점이 있어도 프로그래머에게 에러 내역을 알려주지 못하는 경우가 많습니다. 이 단점을 극단적으로 보여준다고 할 수 있는 것이 바로 undefined behavior입니다. 번역하면 미정의 동작으로, 그야말로 어떤 일이 벌어져도 이상하지 않게 만드는 코드상의 오류입니다. Undefined behavior (UB)가 무엇이고, 어떤 종류가 있는지는 evenharder 님이 작성하신 C/C++의 undefined behavior 글을 참고하도록 하고, 이 글에서는 이 UB라는 녀석이 왜 무서운지만 간단하게 정리해 보겠습니다. UB가 발생하면 무슨 일이 일어나도 이상하지 ..

알고리즘 문제에서 시간 복잡도는 어떠한 문제든 반드시 고려해야 하는 중요 요소입니다. 그런데 조금 더 구체적으로 인지해야 할 것이 있습니다. 여기에서 말하는 시간 복잡도는 평균이 아니라 항상 최악의 경우를 고려해야 한다는 것입니다. 퀵정렬은 평균과 최악의 경우 시간 복잡도가 서로 다른 대표적인 알고리즘입니다. 거의 대부분의 케이스에서는 $\mathcal{O}(N\log{N})$의 시간 복잡도를 보이지만 최악의 경우에는 $\mathcal{O}(N^2)$으로 느리다고 배우는 버블 정렬, 선택 정렬 등과 동일한 시간 복잡도를 가집니다. PS 문제에서 최악의 경우가 중요한 이유는 단 하나입니다. 단 하나의 케이스에서라도 제한 시간을 넘기면 그 코드는 시간 초과로 판정되기 때문입니다. 출제자들은 언제나 이러한 코..

출력 형식이 잘못되었습니다라는 판정을 처음 받으면 대개 매우 당황하게 됩니다. 아무리 봐도 눈에 보이는 글자들의 출력은 완벽한데요? 하지만 이 메시지가 의미하는 것은 눈에 보이는 형식이 아니라 눈에 안 보이는, 공백이나 개행과 관련된 형식이 잘못되었다는 뜻입니다. 이와 관련한 질문이 가장 많이 나오는 출처가 별 찍기 시리즈입니다. 별 찍기 - 2 문제를 예로 들어보겠습니다. 다음과 같은 파이썬 코드를 실행해 보면 출력이 언뜻 보기엔 완벽해 보입니다. n = int(input()) for i in range(n + 1): print(' ' * (n + 1 - i) + '*' * i) 실행 결과는 https://ideone.com/GRinXF 에서 볼 수 있습니다. 문제의 예제와 똑같아 보이지 않나요? 그런..

요즘 부쩍 많이 보이는 파이썬 질문 중에 테스트할 때는 input()을 쓰고 제출할 때에만 sys.stdin.readline()을 쓰는 코드가 종종 보입니다. 알아보니 Jupyter를 쓰시는 분들이 주로 그렇게 하는 것 같습니다 (저는 PyCharm을 써서 몰랐습니다.) Jupyter에는 sys.stdin.readline이 구현되어 있지 않아서 어쩔 수 없이 제출할 때와 코드를 달리해야 하는데, 그렇다면 둘의 차이를 확실하게 알고 사용해야 합니다. 물론 내부적으로도 뭔가 차이가 있겠지만, 일단 겉으로 드러나는 매우 중요한 차이점은 바로 sys.stdin.readline()은 매 줄의 끝에 있는 개행 문자를 포함하여 반환해준다는 것입니다. 예를 들어, 입력으로 abc를 치고 엔터를 쳤다면 이를 s = in..

알고리즘의 효율성을 평가하는 기본적인 척도는 시간 복잡도입니다. 문제를 풀 때에도 어떤 알고리즘이 문제의 제한을 시간 내에 통과할 수 있을지 측정하는 용도로 시간 복잡도를 제일 먼저 계산하곤 합니다. 그렇게 해서 나온 시간 복잡도를 가지고 C/C++은 1초에 10억 번 연산을 할 수 있고 PyPy3는 1초에 1억 번을 할 수 있고... 이런 식으로 종종 수행 시간을 예측하고는 합니다. 하지만 이러한 계산 방식에 의존해서는 안 됩니다. 왜냐하면, 시간 복잡도는 수행 시간과는 근본적으로 다르기 때문입니다. 시간 복잡도 vs. 수행 시간 다시 강조하지만 시간 복잡도는 수행 시간과 근본적으로 다릅니다. 복잡도라는 것은 대단히 수학적인 개념으로, 이 글에서 자세히 설명하지는 않겠으나 이해하기 쉽게 말하면 어디까지..

작성한 코드가 한 번에 내가 생각한 로직 그대로 올바르게 동작할 가능성은 그다지 크지 않습니다. 그렇기 때문에 코드가 무사히 컴파일이 되었다고 해도 한 번에 맞았습니다!를 받기는 어렵고, 예제가 강력하면 틀렸습니다를 받기 전에 스스로 고쳐볼 기회가 많아집니다. 하지만 예제는 예제일 뿐, 내 코드의 모든 취약점을 다 잡아줄 거라고 절대 기대할 수 없습니다. 결국 스스로 반례를 찾는 연습이 필요합니다. 이때 가장 먼저 해보면 좋을 것이 바로 모든 분기의 코드가 제대로 실행되는지 확인해보는 것입니다. 이를 연습해볼 수 있는 대표적인 문제, 주사위 세개를 예시로 들어보겠습니다. 간단한 로직이니, 내가 쓰는 언어가 아니라도 무서워하지 마세요. a, b, c = map(int, input().split()) if ..

흔히 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로 고정..