PS 했던 블로그

이번 글은 실제로 많이 하는 답변이라기보다는 대다수의 질문자들께 드리고 싶은 조언을 담은 글입니다. 질문글을 보다 보면 그 중 반 이상은 '반례를 찾아달라'는 내용이 거의 전부인 것을 목격하게 됩니다. 물론 아무리 봐도 완벽한 내 코드가 틀리는 케이스가 무엇인지 알게 되면 답답함이 해소되는 것은 당연하고, 반례를 바탕으로 디버깅도 훨씬 수월하게 진행할 수 있기 때문에 반례를 부탁하게 되는 심리는 매우 자연스럽습니다. 하지만 저는 이런 당장의 시원함보다는 반례를 알려주지 않는 시스템이기 때문에 얻을 수 있는 것들을 얻어가는 것이 중요하다고 생각합니다. BOJ는 틀린 케이스가 무엇인지 알려주지 않는 사이트로 유명(?)한데, 이는 결코 데이터가 저작권이 있어서 유출되기를 꺼리기 때문이 아닙니다. 데이터에 맞게..

이전에 제출했던 틀린 코드 전체를 그대로 올려주세요.라는 비슷한 글을 쓴 적이 있습니다. 이번 글은 이와도 일맥상통하는 것으로, 질문글의 코드가 제출했던 코드와 일치하지 않게 만드는 대표적인 이유이기도 합니다. 제목 그대로, 질문글의 코드를 그대로 한 글자의 수정도 거치지 않고 제출하면 그대로 정답을 받는 경우가 정말 많습니다. 핵심은 정말로 질문글의 코드를 단 한 글자도 고치지 않아야 한다는 것입니다. 그냥 복붙만 제대로 하면 발생하지 않을 문제임에도 불구하고 이런 질문이 종종 올라오게 되는 이유는 제출한 코드와 질문글의 코드가 서로 어딘가 한 글자라도 달라지기 쉬운 문제 풀이 습관을 가지고 있기 때문입니다. 로컬에서 작업한 코드를 그대로 Ctrl+C, Ctrl+V로 제출창에 복붙하세요. 채점 환경이 ..

코드를 제출했는데 시간 초과를 받으면 보통 "이 코드가 그렇게 비효율적인가?" 하고 생각하게 됩니다. 물론 알고리즘의 효율성, 특히 시간 복잡도를 계산하는 것은 코드를 작성하기 전부터 당연히 최우선으로 해야 하는 일이지만 '시간 초과'가 의미하는 것은 항상 '효율성'이 나쁘다는 것을 의미하지는 않습니다. 시간 초과에서 매우 큰 비중을 차지하는 것 중 하나는 바로 코드가 무한 루프를 도는 경우입니다. 문제 풀이에 쓰이는 코드는 반드시 정답을 출력한 후 정상적으로 종료가 되어야 합니다. 만일 더 받을 입력이 없는데도 불구하고 루프를 계속 돌면서 입력을 받고 있다면 그 코드는 높은 확률로 시간 초과나 출력 초과, 혹은 런타임 에러를 받게 됩니다. 이런 경우가 발생하는 대표적인 경우는 입력의 끝 (EOF)을 판..

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 ..