PS 했던 블로그

알고리즘 문제는 일반적으로 어떠한 입력이 주어졌을 때, 그에 대한 올바른 정답을 출력하는 것으로 구성됩니다. 대부분의 문제에는 이러한 입력이 어떤 형식으로 주어지고 출력 형식이 어떻게 되어야 하는지에 대한 힌트를 주기 위해, 그리고 문제 이해를 돕고 몇 가지의 간단한 테스트를 해볼 수 있도록 하나 이상의 예제를 제공합니다. 여기서 중요한 부분이 있습니다. 굵은 글씨로 강조한 것처럼, 예제는 언제까지나 문제 풀이에 대한 힌트를 주고 몇 가지의 간단한 테스트용 예시를 제공할 뿐, 절대로 이들을 통과하기 위한 코드를 작성하라는 의미로 주는 것이 아닙니다. 그러면 문제를 풀 때에는 어디를 목표로 봐야 할까요? 바로 문제의 조건입니다. 문제의 조건이라는 것은 시간/메모리 제한, 주어지는 수의 최소/최대 범위, 문..

시간 초과를 받는 주 원인이 무엇일까요? 많은 초보들은 이에 대해 '코드가 너무 길어서 그렇지 않을까?' 하고 생각합니다. 하지만 실상은 반대인 경우가 더 많습니다. 알고리즘 문제 풀이에서 코드의 수행 시간을 결정하는 가장 큰 요인은 일반적으로 시간 복잡도이며, 시간 복잡도를 고려하여 작성하였다면 아무리 엄청나게 긴 코드를 작성하더라도 한 번 실행된 것만 가지고 웬만한 문제에서 시간을 초과시킬 일은 없습니다. 반면에 시간 복잡도를 고려하지 않고 오로지 답만 구할 수 있도록 코드를 짧게 줄인 코드는 시간을 초과할 가능성이 높습니다. 이와 관련하여 대표적으로 흔하게 하는 실수가 바로 라이브러리 함수의 시간 복잡도를 고려하지 않고 그 기능만을 목적으로 사용하는 것입니다. 아주 편리하지만 매우 비효율적인, 대표..

제목대로, 또는 큐에서 뺀 뒤에 '이미 방문한 정점인지'를 체크해야 합니다. 그러지 않으면 트리가 아닌 이상 대부분의 경우 시간 초과나 메모리 초과를 받게 됩니다. 그 이유는 다음과 같은 예시에서 확인해볼 수 있습니다. 미로 탐색 문제에 대해, 동일한 로직의 아래 C++과 Python 3 코드를 봅시다. [C++] #include using namespace std; string arr[105]; bool vis[105][105]; int dy[]{ 1, 0, -1, 0 }; int dx[]{ 0, 1, 0, -1 }; int main() { int n, m; cin >> n >> m; for (int i = 0; i > arr[i]; queue q; q.push({ 0, 0 ..

"같은 코드를 여러 번 냈는데 왜 실행 시간이 달라지나요?" 정상입니다. 프로그램의 실행 시간은 원래 일정하지 않기 때문입니다. 똑같이 프로그램을 실행한다고 해도 그 때의 컴퓨터의 상태가 완전히 같을 수는 없습니다. 메모리의 상태가 다르고, OS가 하고 있던 일이 다르고, 백그라운드 서비스들의 상태가 다르고, CPU의 온도가 다르기 때문입니다. 또한 실행 중에도 이 상태는 얼마든지 중간에 변할 수 있고, 이로 인해 같은 코드를 실행하더라도 프로그램이 눈에 띄게 더 빠르거나 느리게 동작할 수 있습니다. 기본적으로 시간이 오래 걸리는 코드라면 이 실행 시마다의 오차는 더 커지게 됩니다. 예를 들어 평균 300ms 정도가 걸리는 코드가 ±20ms 정도의 오차를 보인다면, 평균 3초가 걸리는 코드는 ±200ms..

1. 입력과 출력의 순서는 상관이 없습니다. 문제를 풀 때에는 오로지 출력한 전체 내용이 정답과 같기만 하면 됩니다. 여러 테스트 케이스 각각에 대해 답을 출력하는 문제라고 하더라도 반드시 한 케이스를 입력받은 후 답을 출력하고 다음 케이스를 입력받아야 하는 것은 아닙니다. 모든 케이스를 전부 입력받고 답을 나중에 몰아서 출력해도 상관 없고, 입력을 받던 도중에 답을 출력해도 되고, 입력을 받기 전에 답을 출력해도 되며 (답을 알 수 있다면), 입력을 아예 안 받고 답을 출력해도 됩니다. 2. 입력과 출력이 화면에 섞여나와도 문제 없습니다. 보통 프로그램을 테스트할 때에는 콘솔에서 실행하고, 이 콘솔 화면에서 입력과 출력이 함께 이루어지기 때문에 섞여나오는 것이 정답에 영향을 주지 않을까 걱정하는 분들도..

이번 글은 실제로 많이 하는 답변이라기보다는 대다수의 질문자들께 드리고 싶은 조언을 담은 글입니다. 질문글을 보다 보면 그 중 반 이상은 '반례를 찾아달라'는 내용이 거의 전부인 것을 목격하게 됩니다. 물론 아무리 봐도 완벽한 내 코드가 틀리는 케이스가 무엇인지 알게 되면 답답함이 해소되는 것은 당연하고, 반례를 바탕으로 디버깅도 훨씬 수월하게 진행할 수 있기 때문에 반례를 부탁하게 되는 심리는 매우 자연스럽습니다. 하지만 저는 이런 당장의 시원함보다는 반례를 알려주지 않는 시스템이기 때문에 얻을 수 있는 것들을 얻어가는 것이 중요하다고 생각합니다. 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가 발생하면 무슨 일이 일어나도 이상하지 ..