티스토리

PS 했던 블로그

검색하기

블로그 홈

PS 했던 블로그

djm03178.tistory.com/m

djm03178 님의 블로그입니다.

구독자: 11

방명록 방문하기

주요 글 목록

좋은 질문을 하는 방법 참고: 도움이 필요한 당신에게BOJ에서 틀린 코드에 대한 도움을 받고 싶을 때 기준입니다. 이런 글이 길어지면 읽기 피곤하니, 짧게 가겠습니다.질문을 올리기 전에조금만 더 고민해 보세요. 디버깅 과정도 엄연히 문제 풀이 과정의 일부이고, 아주 중요한 능력입니다. 오답을 받자마자 고민 없이 곧바로 질문글을 작성하는 것이 습관이 되면 결국 디버깅 능력은 기를 수가 없습니다.예제들을 다시 한 번 넣어보세요. 반례는 보통 멀리 있지 않습니다. 한 글자 수정할 때마다 예제가 나오는지 여부가 매번 바뀌는 건 매우 자연스러운 현상이기 때문에, 다른 곳에서 반례를 찾기 전에 예제를 일단 전부 다시 넣어보는 것이 좋습니다.질문 게시판을 먼저 확인해 보세요. 푼 사람이 많은 문제들의 경우 질문 게시판에 이미 수백 개의 글.. 공감수 3 댓글수 0 2024. 9. 20.
Codeforces 라운드 종류와 문제 난이도 이번 글에는 조금 다른 주제를 가져와 보았습니다. 몇 번에 걸쳐 Codeforces에 관련된 글들을 써보려고 하고, 이 글은 그 중 첫 번째입니다. Rated 라운드의 종류Rated 라운드는 참가자들의 레이팅에 변동을 주는 라운드로, 라운드 종류마다 이 영향을 받는 참가자들의 레이팅 범위가 다릅니다. 실력 수준에 적절하게 맞추어 구성된 문제 셋에서만 경쟁을 하도록 디비전이 여럿으로 나뉘어 있습니다. 우선 전체 목록을 정리하면 다음과 같습니다.DivisionRatedFormatTrusted Participant문제 수비고Div. 1 + Div. 2전원일반 8-9일반적으로 스폰서 라운드Div. 1>= 1900일반 5-7Div. 2와 동시 개최Div. 2 (with Div. 1)일반 5-7Div. 1과 동시 .. 공감수 1 댓글수 0 2024. 8. 18.
런타임 에러의 이유가 힌트입니다. BOJ에서는 몇 년 전에 아주 편리한 기능을 업데이트했습니다. 바로 런타임 에러의 이유를 찾아주는 기능입니다. 모든 종류의 에러를 다 잡아주지는 못하지만, 흔하게 발생하는 많은 종류의 에러들을, 인터프리터 언어의 예외는 바로 잡아주고, 컴파일 언어의 에러는 디버깅 기능을 이용하여 최대한 에러의 원인을 찾아주는 방향으로 동작합니다. (물론, undefined behavior는 디버거조차도 속일 수 있습니다!) 런타임 에러가 발생했을 때 '런타임 에러'라고 쓰인 곳을 클릭하면 도움말 페이지로 이동하는데, 이곳에서 각 에러 종류에 대한 설명과 발생하는 주 원인들을 볼 수 있습니다. 자료가 풍부하지는 않지만, 적어도 초보들이 흔히 실수하는 부분에 대한 설명은 웬만하면 찾을 수 있는 정도는 됩니다. 런타임 에러의.. 공감수 0 댓글수 0 2024. 5. 9.
모든 조건을 함께 고려한 입력만 주어집니다. 이 글은 질문보다는 수정 요청글로 자주 보는 내용에 대한 매크로(?) 답변용입니다. 문제들 중에는 다음과 같은 조건을 가진 것이 많습니다. 입력으로 그래프가 주어지는데, 정점의 개수가 $1 \le N \le 100,000$개, 간선의 개수가 $1 \le M \le 200,000$개이고, 간선의 양 끝점은 서로 다르며 중복된 간선이 없다고 합니다. 그런데 여기서 의문이 듭니다. 정점의 개수가 1개 이상이라고 하는데, 정점이 1개이면 간선은 하나도 못 주어지지 않나요? 그렇다면 정점도 1개 이상이고 간선도 1개 이상이라는 조건이 잘못된 것 아닌가요? 하지만 조건은 이렇게 따로 따로 분리해놓고 생각해야 하는 것이 아닙니다. 다음과 같은 예시를 보겠습니다. "입력으로 $1$ 이상 $1,000,000$ 이하의 정.. 공감수 1 댓글수 0 2024. 5. 7.
예제가 아닌, 문제의 조건에 맞는 코드를 작성해야 합니다. 알고리즘 문제는 일반적으로 어떠한 입력이 주어졌을 때, 그에 대한 올바른 정답을 출력하는 것으로 구성됩니다. 대부분의 문제에는 이러한 입력이 어떤 형식으로 주어지고 출력 형식이 어떻게 되어야 하는지에 대한 힌트를 주기 위해, 그리고 문제 이해를 돕고 몇 가지의 간단한 테스트를 해볼 수 있도록 하나 이상의 예제를 제공합니다. 여기서 중요한 부분이 있습니다. 굵은 글씨로 강조한 것처럼, 예제는 언제까지나 문제 풀이에 대한 힌트를 주고 몇 가지의 간단한 테스트용 예시를 제공할 뿐, 절대로 이들을 통과하기 위한 코드를 작성하라는 의미로 주는 것이 아닙니다. 그러면 문제를 풀 때에는 어디를 목표로 봐야 할까요? 바로 문제의 조건입니다. 문제의 조건이라는 것은 시간/메모리 제한, 주어지는 수의 최소/최대 범위, 문.. 공감수 3 댓글수 2 2024. 4. 8.
라이브러리 함수는 공짜가 아닙니다. 시간 초과를 받는 주 원인이 무엇일까요? 많은 초보들은 이에 대해 '코드가 너무 길어서 그렇지 않을까?' 하고 생각합니다. 하지만 실상은 반대인 경우가 더 많습니다. 알고리즘 문제 풀이에서 코드의 수행 시간을 결정하는 가장 큰 요인은 일반적으로 시간 복잡도이며, 시간 복잡도를 고려하여 작성하였다면 아무리 엄청나게 긴 코드를 작성하더라도 한 번 실행된 것만 가지고 웬만한 문제에서 시간을 초과시킬 일은 없습니다. 반면에 시간 복잡도를 고려하지 않고 오로지 답만 구할 수 있도록 코드를 짧게 줄인 코드는 시간을 초과할 가능성이 높습니다. 이와 관련하여 대표적으로 흔하게 하는 실수가 바로 라이브러리 함수의 시간 복잡도를 고려하지 않고 그 기능만을 목적으로 사용하는 것입니다. 아주 편리하지만 매우 비효율적인, 대표.. 공감수 3 댓글수 0 2024. 2. 19.
BFS를 할 때에는 큐에 넣을 때 방문 표시를 해야 합니다. 제목대로, 또는 큐에서 뺀 뒤에 '이미 방문한 정점인지'를 체크해야 합니다. 그러지 않으면 트리가 아닌 이상 대부분의 경우 시간 초과나 메모리 초과를 받게 됩니다. 그 이유는 다음과 같은 예시에서 확인해볼 수 있습니다. 미로 탐색 문제에 대해, 동일한 로직의 아래 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 .. 공감수 7 댓글수 1 2024. 2. 8.
프로그램의 실행 시간은 원래 일정하지 않습니다. "같은 코드를 여러 번 냈는데 왜 실행 시간이 달라지나요?" 정상입니다. 프로그램의 실행 시간은 원래 일정하지 않기 때문입니다. 똑같이 프로그램을 실행한다고 해도 그 때의 컴퓨터의 상태가 완전히 같을 수는 없습니다. 메모리의 상태가 다르고, OS가 하고 있던 일이 다르고, 백그라운드 서비스들의 상태가 다르고, CPU의 온도가 다르기 때문입니다. 또한 실행 중에도 이 상태는 얼마든지 중간에 변할 수 있고, 이로 인해 같은 코드를 실행하더라도 프로그램이 눈에 띄게 더 빠르거나 느리게 동작할 수 있습니다. 기본적으로 시간이 오래 걸리는 코드라면 이 실행 시마다의 오차는 더 커지게 됩니다. 예를 들어 평균 300ms 정도가 걸리는 코드가 ±20ms 정도의 오차를 보인다면, 평균 3초가 걸리는 코드는 ±200ms.. 공감수 0 댓글수 0 2024. 2. 4.
입출력에 대해 몇 가지 자주 하는 답변 1. 입력과 출력의 순서는 상관이 없습니다. 문제를 풀 때에는 오로지 출력한 전체 내용이 정답과 같기만 하면 됩니다. 여러 테스트 케이스 각각에 대해 답을 출력하는 문제라고 하더라도 반드시 한 케이스를 입력받은 후 답을 출력하고 다음 케이스를 입력받아야 하는 것은 아닙니다. 모든 케이스를 전부 입력받고 답을 나중에 몰아서 출력해도 상관 없고, 입력을 받던 도중에 답을 출력해도 되고, 입력을 받기 전에 답을 출력해도 되며 (답을 알 수 있다면), 입력을 아예 안 받고 답을 출력해도 됩니다. 2. 입력과 출력이 화면에 섞여나와도 문제 없습니다. 보통 프로그램을 테스트할 때에는 콘솔에서 실행하고, 이 콘솔 화면에서 입력과 출력이 함께 이루어지기 때문에 섞여나오는 것이 정답에 영향을 주지 않을까 걱정하는 분들도.. 공감수 1 댓글수 1 2023. 11. 30.
반례에 의존하지 마세요. 이번 글은 실제로 많이 하는 답변이라기보다는 대다수의 질문자들께 드리고 싶은 조언을 담은 글입니다. 질문글을 보다 보면 그 중 반 이상은 '반례를 찾아달라'는 내용이 거의 전부인 것을 목격하게 됩니다. 물론 아무리 봐도 완벽한 내 코드가 틀리는 케이스가 무엇인지 알게 되면 답답함이 해소되는 것은 당연하고, 반례를 바탕으로 디버깅도 훨씬 수월하게 진행할 수 있기 때문에 반례를 부탁하게 되는 심리는 매우 자연스럽습니다. 하지만 저는 이런 당장의 시원함보다는 반례를 알려주지 않는 시스템이기 때문에 얻을 수 있는 것들을 얻어가는 것이 중요하다고 생각합니다. BOJ는 틀린 케이스가 무엇인지 알려주지 않는 사이트로 유명(?)한데, 이는 결코 데이터가 저작권이 있어서 유출되기를 꺼리기 때문이 아닙니다. 데이터에 맞게.. 공감수 18 댓글수 3 2023. 6. 15.
이 코드 그대로 내니 맞았습니다. 이전에 제출했던 틀린 코드 전체를 그대로 올려주세요.라는 비슷한 글을 쓴 적이 있습니다. 이번 글은 이와도 일맥상통하는 것으로, 질문글의 코드가 제출했던 코드와 일치하지 않게 만드는 대표적인 이유이기도 합니다. 제목 그대로, 질문글의 코드를 그대로 한 글자의 수정도 거치지 않고 제출하면 그대로 정답을 받는 경우가 정말 많습니다. 핵심은 정말로 질문글의 코드를 단 한 글자도 고치지 않아야 한다는 것입니다. 그냥 복붙만 제대로 하면 발생하지 않을 문제임에도 불구하고 이런 질문이 종종 올라오게 되는 이유는 제출한 코드와 질문글의 코드가 서로 어딘가 한 글자라도 달라지기 쉬운 문제 풀이 습관을 가지고 있기 때문입니다. 로컬에서 작업한 코드를 그대로 Ctrl+C, Ctrl+V로 제출창에 복붙하세요. 채점 환경이 .. 공감수 2 댓글수 0 2023. 5. 23.
무한 루프에 걸려서 시간 초과입니다. 코드를 제출했는데 시간 초과를 받으면 보통 "이 코드가 그렇게 비효율적인가?" 하고 생각하게 됩니다. 물론 알고리즘의 효율성, 특히 시간 복잡도를 계산하는 것은 코드를 작성하기 전부터 당연히 최우선으로 해야 하는 일이지만 '시간 초과'가 의미하는 것은 항상 '효율성'이 나쁘다는 것을 의미하지는 않습니다. 시간 초과에서 매우 큰 비중을 차지하는 것 중 하나는 바로 코드가 무한 루프를 도는 경우입니다. 문제 풀이에 쓰이는 코드는 반드시 정답을 출력한 후 정상적으로 종료가 되어야 합니다. 만일 더 받을 입력이 없는데도 불구하고 루프를 계속 돌면서 입력을 받고 있다면 그 코드는 높은 확률로 시간 초과나 출력 초과, 혹은 런타임 에러를 받게 됩니다. 이런 경우가 발생하는 대표적인 경우는 입력의 끝 (EOF)을 판.. 공감수 0 댓글수 0 2023. 5. 9.
atoi에 char 변수의 주소를 넣으면 안 됩니다. PS를 하다 보면 문자열로 저장된 수를 정수형으로 바꾸고 싶은 경우가 종종 있습니다. 이를 위해서 편하게 사용할 수 있는 C 라이브러리 함수가 하나 있는데 바로 atoi입니다. 단, 어떤 라이브러리든 마찬가지이지만 사용할 때에는 그 사용법을 정확히 알고 사용해야 하는데 atoi에도 초보자들이 매우 자주 하는 실수가 있습니다. atoi에는 절대로, 절대로 하나의 char 변수의 주소값을 넘겨서는 안 됩니다. atoi가 const char *를 인자로 받기 때문에 얼핏 보면 char 변수 앞에 &를 붙여서 그 주소를 넘겨주면 자료형 문제가 해결되어 사용할 수 있을 것처럼 보입니다. 하지만 그건 올바른 해결 방법이 아닙니다. atoi는 문자가 아니라 문자열을 인자로 받는 함수이기 때문입니다. 문자열의 끝에는 .. 공감수 0 댓글수 0 2023. 5. 9.
Undefined Behavior가 있으면 무슨 일이 일어나도 이상하지 않습니다. C/C++이 어려운 이유 중 하나로 디버깅이 어렵다는 점을 들 수 있을 것입니다. 직접적으로 기계어로 번역되어 실행되는 특성상 코드에 어떤 문제점이 있어도 프로그래머에게 에러 내역을 알려주지 못하는 경우가 많습니다. 이 단점을 극단적으로 보여준다고 할 수 있는 것이 바로 undefined behavior입니다. 번역하면 미정의 동작으로, 그야말로 어떤 일이 벌어져도 이상하지 않게 만드는 코드상의 오류입니다. Undefined behavior (UB)가 무엇이고, 어떤 종류가 있는지는 evenharder 님이 작성하신 C/C++의 undefined behavior 글을 참고하도록 하고, 이 글에서는 이 UB라는 녀석이 왜 무서운지만 간단하게 정리해 보겠습니다. UB가 발생하면 무슨 일이 일어나도 이상하지 .. 공감수 6 댓글수 2 2023. 4. 18.
퀵정렬은 제곱입니다. 알고리즘 문제에서 시간 복잡도는 어떠한 문제든 반드시 고려해야 하는 중요 요소입니다. 그런데 조금 더 구체적으로 인지해야 할 것이 있습니다. 여기에서 말하는 시간 복잡도는 평균이 아니라 항상 최악의 경우를 고려해야 한다는 것입니다. 퀵정렬은 평균과 최악의 경우 시간 복잡도가 서로 다른 대표적인 알고리즘입니다. 거의 대부분의 케이스에서는 $\mathcal{O}(N\log{N})$의 시간 복잡도를 보이지만 최악의 경우에는 $\mathcal{O}(N^2)$으로 느리다고 배우는 버블 정렬, 선택 정렬 등과 동일한 시간 복잡도를 가집니다. PS 문제에서 최악의 경우가 중요한 이유는 단 하나입니다. 단 하나의 케이스에서라도 제한 시간을 넘기면 그 코드는 시간 초과로 판정되기 때문입니다. 출제자들은 언제나 이러한 코.. 공감수 3 댓글수 0 2023. 3. 24.
'출력 형식이 잘못되었습니다'의 의미 출력 형식이 잘못되었습니다라는 판정을 처음 받으면 대개 매우 당황하게 됩니다. 아무리 봐도 눈에 보이는 글자들의 출력은 완벽한데요? 하지만 이 메시지가 의미하는 것은 눈에 보이는 형식이 아니라 눈에 안 보이는, 공백이나 개행과 관련된 형식이 잘못되었다는 뜻입니다. 이와 관련한 질문이 가장 많이 나오는 출처가 별 찍기 시리즈입니다. 별 찍기 - 2 문제를 예로 들어보겠습니다. 다음과 같은 파이썬 코드를 실행해 보면 출력이 언뜻 보기엔 완벽해 보입니다. n = int(input()) for i in range(n + 1): print(' ' * (n + 1 - i) + '*' * i) 실행 결과는 https://ideone.com/GRinXF 에서 볼 수 있습니다. 문제의 예제와 똑같아 보이지 않나요? 그런.. 공감수 0 댓글수 0 2023. 1. 29.
input()과 sys.stdin.readline()의 차이 요즘 부쩍 많이 보이는 파이썬 질문 중에 테스트할 때는 input()을 쓰고 제출할 때에만 sys.stdin.readline()을 쓰는 코드가 종종 보입니다. 알아보니 Jupyter를 쓰시는 분들이 주로 그렇게 하는 것 같습니다 (저는 PyCharm을 써서 몰랐습니다.) Jupyter에는 sys.stdin.readline이 구현되어 있지 않아서 어쩔 수 없이 제출할 때와 코드를 달리해야 하는데, 그렇다면 둘의 차이를 확실하게 알고 사용해야 합니다. 물론 내부적으로도 뭔가 차이가 있겠지만, 일단 겉으로 드러나는 매우 중요한 차이점은 바로 sys.stdin.readline()은 매 줄의 끝에 있는 개행 문자를 포함하여 반환해준다는 것입니다. 예를 들어, 입력으로 abc를 치고 엔터를 쳤다면 이를 s = in.. 공감수 0 댓글수 0 2023. 1. 29.
시간 복잡도는 수행 시간이 아닙니다. 알고리즘의 효율성을 평가하는 기본적인 척도는 시간 복잡도입니다. 문제를 풀 때에도 어떤 알고리즘이 문제의 제한을 시간 내에 통과할 수 있을지 측정하는 용도로 시간 복잡도를 제일 먼저 계산하곤 합니다. 그렇게 해서 나온 시간 복잡도를 가지고 C/C++은 1초에 10억 번 연산을 할 수 있고 PyPy3는 1초에 1억 번을 할 수 있고... 이런 식으로 종종 수행 시간을 예측하고는 합니다. 하지만 이러한 계산 방식에 의존해서는 안 됩니다. 왜냐하면, 시간 복잡도는 수행 시간과는 근본적으로 다르기 때문입니다. 시간 복잡도 vs. 수행 시간 다시 강조하지만 시간 복잡도는 수행 시간과 근본적으로 다릅니다. 복잡도라는 것은 대단히 수학적인 개념으로, 이 글에서 자세히 설명하지는 않겠으나 이해하기 쉽게 말하면 어디까지.. 공감수 7 댓글수 2 2023. 1. 28.
모든 분기를 테스트 해보세요. 작성한 코드가 한 번에 내가 생각한 로직 그대로 올바르게 동작할 가능성은 그다지 크지 않습니다. 그렇기 때문에 코드가 무사히 컴파일이 되었다고 해도 한 번에 맞았습니다!를 받기는 어렵고, 예제가 강력하면 틀렸습니다를 받기 전에 스스로 고쳐볼 기회가 많아집니다. 하지만 예제는 예제일 뿐, 내 코드의 모든 취약점을 다 잡아줄 거라고 절대 기대할 수 없습니다. 결국 스스로 반례를 찾는 연습이 필요합니다. 이때 가장 먼저 해보면 좋을 것이 바로 모든 분기의 코드가 제대로 실행되는지 확인해보는 것입니다. 이를 연습해볼 수 있는 대표적인 문제, 주사위 세개를 예시로 들어보겠습니다. 간단한 로직이니, 내가 쓰는 언어가 아니라도 무서워하지 마세요. a, b, c = map(int, input().split()) if .. 공감수 1 댓글수 0 2023. 1. 27.
sync_with_stdio(false) 이후에는 C와 C++의 입출력 방식을 섞어쓰면 안 됩니다. 흔히 C++에서 입출력을 빨리 하는 기법이라고 해서 ios::sync_with_stdio(false); 라는 문장을 main 함수 상단에 넣곤 합니다. 그런데 이 문장이 왜 입출력을 빠르게 할까요? 그 답은 함수 이름에 직설적으로 들어있습니다. sync(hronize) with stdio, 말 그대로 stdio와 동기화를 한다는 뜻의 이름인데, 여기에 인자를 false를 주었으니, 동기화를 더 이상 안 하겠다는 의미입니다. 쉽게 말해서, ios (C++의 입출력 함수들)는 더 이상 stdio를 신경쓰지 않고 자기 갈 길을 가기 때문에 C++ 입출력 함수들의 속도가 향상될 수 있는 것입니다. 구체적으로는 이제 cin, cout 등이 자기 자신만의 입출력 버퍼를 두고 미리 입력받은 내용을 모아놓는다거나, 출.. 공감수 1 댓글수 0 2023. 1. 26.
문자열의 끝까지만 봐야 합니다. C/C++에서 문자열이란 초보자가 다루기가 상당히 까다로운 편에 속합니다. 정확한 사용법을 숙지하지 못하고 쓰다가 실수를 하는 일도 굉장히 잦습니다. 대표적인 사례가 바로 문자열의 끝과 관련한 것들입니다. 문자열의 끝에는 항상 널 문자가 들어갑니다. 글에서 다루었듯이 일반적인 char로 나타낸 문자열의 끝은 항상 널 문자 ('\0')입니다. C++의 std::string과 같은 경우에도 문자열의 마지막 글자의 다음 인덱스에 접근할 경우 널 문자를 반환할 것이 표준에 명시되어 있습니다. 다시 강조하지만 널 문자는 문자열로서의 마지막을 나타냅니다. 달리 말하면 널 문자를 넘어선 부분은 문자열의 일부가 아닙니다. 흔히 문자열을 입력받기 위해 다음과 같은 고정된 크기의 배열을 선언하고 입력을 받습니다. char.. 공감수 1 댓글수 0 2023. 1. 13.
PyPy3로 제출하면 통과됩니다. BOJ에서는 Python 3를 위한 제출 언어를 두 가지 제공하고 있습니다. 기본 CPython 인터프리터를 사용하는 Python 3와, 일반적으로 훨씬 빠른 속도를 자랑하는 인터프리터인 PyPy3입니다. 이 글에서 하고 싶은 말이 벌써 나왔습니다. PyPy3는 Python 3보다 일반적으로 훨씬 빠르므로, 문제도 PyPy3로 풀기를 권장합니다. 공식 홈페이지의 언급에 의하면 PyPy는 CPython에 비해 평균적으로 4.8배가 빠르다고 합니다. 모든 종류의 벤치마킹에서 항상 빠른 것은 아니지만, 적어도 PS 중에는 Python 3을 굳이 쓸 이유가 저는 웬만하면 없다고 생각합니다. 시간 보너스도 3배 + 2초로 동일하게 주어지는데 일부러 느린 것을 쓸 필요가 없습니다. 처음부터 언어를 PyPy3로 고정.. 공감수 7 댓글수 0 2023. 1. 11.
100%에서 틀리는 것의 의미 BOJ의 질문 게시판 공지사항에서는 "몇 %에서 틀렸다는 내용을 올리지 마세요"라고 적혀있지만, 개인적으로는 몇 %에서 틀렸는지는 때때로 좋은 힌트가 된다고 생각합니다. 그 중 가장 영양가 높은(?) 것이 바로 100%에서 틀리는 경우입니다. 채점 프로그램의 대략적인 동작 방식은 50%에서 틀리는 것의 의미 글에서 설명했으니 여기서는 100%에서 틀리는 것이 무슨 의미를 가지는지에 대해서만 알아보겠습니다. 모든 경우에 해당되는 것은 아니지만, 대부분의 경우에 유의미한 힌트를 줍니다. BOJ에서 데이터를 정렬하는 방법에는 몇 가지가 있는데, 그 중 가장 일반적인 기본값은 데이터의 크기의 내림차순입니다. BOJ 자체에서 여는 대회 문제들을 제외하고, 출처가 따로 없거나 외부 대회가 출처인 문제들의 경우 대부.. 공감수 0 댓글수 0 2023. 1. 7.
Integer끼리는 반드시 equals로 비교해야 합니다. Java에서 자주 보이는, 무한 디버깅을 유발하는 사례입니다. 작은 케이스에서 아무리 해도 반례가 안 나오기 때문에 고생하게 되는 경우가 많습니다. Integer는 primitive type 인 int를 객체의 형태로 편하게 표현하기 위한 wrapper 클래스입니다. primitive type은 Object로서 다룰 수 없기 때문에 언어 차원에서 특별히 이러한 클래스를 제공해주는데, Integer와 int 사이의 형변환이 자동으로 이루어지기 때문에 둘을 같은 것처럼 쓰더라도 보통은 문제가 생기지 않습니다... ...만, 각별히 신경써야 할 부분이 하나 있는데, 바로 Integer 객체끼리 비교를 해야 하는 경우입니다. 다음의 케이스를 확인해 봅시다. https://ideone.com/XjogFw publ.. 공감수 1 댓글수 0 2023. 1. 6.
float는 너무나 부정확합니다. 게임 개발 등 실무 프로그래밍에서는 부동소수점 자료형으로 float (4바이트 부동소수점 자료형)를 쓰는 일이 많습니다. 많은 경우 float는 적당히 쓸만한 정확도를 보여주고, 자료형의 크기가 작아 속도가 빠르기 때문에 자주 쓰이는 편입니다. 하지만, PS에서는 절대 float를 권장하지 않습니다. 이유는 간단합니다. PS 문제들은 칼같은 정확도를 요구하기 때문입니다. 대부분의 문제에서는 조금의 오차도 허용하지 않으며, 오차를 허용하는 문제에서도 그 오차가 매우 작을 것을 요구하는 것이 PS 문제입니다. 실수형을 써야 하는 문제에서 많은 경우 "절대/상대 오차는 $10^{-9}$까지 허용한다."와 같이 극도로 작은 오차만을 허용하는데, $10^{-9}$라는 것은 적어도 유효숫자 9자리가 정확해야 한다는.. 공감수 2 댓글수 2 2023. 1. 4.
fflush(stdin), rewind(stdin)은 표준이 아닙니다. 이 글은 제가 처음 프로그래밍을 접했던 약 15년 전부터 아직까지도 끊임없이 보고 있는 것에 대한 이야기입니다. 결론부터 말해서, C 표준에서 stdin의 버퍼를 비워주는 라이브러리는 없습니다. 흔히 fflush(stdin), rewind(stdin)을 사용하여 버퍼를 비우는 기법이 알려져있지만 이는 어디까지나 특정 라이브러리 (제가 아는 한에서는 Visual Studio만)에서 확장 기능으로 그런 사용법도 제공할 뿐이지, 표준상에서는 stdin에 대해 아예 사용이 안 되는 함수들입니다. 보통 scanf로 정수를 입력받고 다음 줄 전체를 fgets 등으로 읽어오고 싶을 때, 정수 뒤에 남아있는 공백을 지우고 싶어서 많이 사용하게 될 건데, 이걸 fflush나 rewind 등으로 지우려고 하면 안 됩니다... 공감수 1 댓글수 0 2023. 1. 3.
컴파일 에러는 "컴파일 에러"라고 쓰인 곳을 클릭하면 에러 메시지를 볼 수 있습니다. 제곧내 는 아니고, 빌드하는 환경(컴파일러 종류 및 버전, 언어 버전 등)에 따라 허용하는 문법 / 확장 기능 / 라이브러리의 종속성 등이 다르기 때문에 직접 컴파일 했을 때 문제가 없었더라도 제출하면 컴파일 에러를 받게 될 수 있습니다. 이 경우 BOJ에서는 채점 현황에 나타난 "컴파일 에러" 문구를 클릭하면 자세한 에러 메시지를 보여줍니다. 채점 환경에 따라 달라질 수 있다고는 했으나, 대개의 경우는 자신의 코드가 표준을 지키지 않고 특정 컴파일러에서는 제공하는 확장 기능이나 확장 라이브러리를 사용했거나, 헤더 파일이 내부적으로 종속성을 가져서 운 좋게 컴파일이 된 경우입니다. 예를 들어 일부 환경 (Visual Studio 2017)에서는 아래와 같은 코드가 컴파일이 될 수도 있으나, #includ.. 공감수 0 댓글수 0 2023. 1. 2.
문자열의 끝에는 항상 널 문자가 들어갑니다. C나 C++에서 char로 된 배열에 문자열의 형태로 입력을 받는 경우 가장 먼저 생각해야 할 것은 바로 널 문자 ('\0')입니다. 널 문자는 문자열의 끝을 알려주는 특별한 문자로, char 문자열에 대한 모든 문자열 관련 라이브러리는 널 문자를 통해 문자열의 끝을 인지합니다. 이는 입력이나 출력 시에도 예외가 아닙니다. 모든 char 문자열 입력 함수 (scanf, fgets, cin, getline 등)를 통해 char 문자열을 입력받으면 이 함수들은 자기가 알아서 문자열의 끝에 널 문자를 추가해줍니다. 그 말은 길이가 $N$인 문자열을 입력받는다면, 입력 함수들이 실제로 사용하는 배열의 크기는 $N+1$이라는 뜻입니다. 예를 들어, 문자열의 길이가 최대 100만인 문제에서 다음과 같이 입력을 받으.. 공감수 1 댓글수 0 2023. 1. 2.
예제가 반례입니다. 문제를 풀다가 '틀렸습니다'가 나오면 대부분의 사람들은 매우 답답할 것입니다. 아무리 봐도 맞는 코드인데, 예제는 맞고, 어디 반례가 없을까 찾게 되는 것이 매우 일반적입니다. 하지만 놀라운 사실이 있습니다. 반례를 찾는 질문들 중 상당히 높은 비율에서 예제가 반례로 나타난다는 것입니다. 예제를 테스트 해보는 것은 기본이기에 단순히 깜빡하고 안 해본 예제가 있어서인 경우는 사실 그렇게 많지는 않습니다. 대개는 예제를 해보고도 그게 반례라는 것을 깨닫지 못하는 경우입니다. 자주 보이는 사례들을 정리해 보았습니다. 출력이 100% 일치하지 않는 경우: 채점 프로그램은 출력하는 한 글자 한 글자에 매우 민감합니다. 출력은 언제나 요구한 것을 글자 단위로 정확하게 출력해야 합니다 (일부 예외 제외). 수를 공백.. 공감수 5 댓글수 1 2022. 12. 30.
반복문의 조건문 안에 strlen을 넣지 마세요. C/C++에서 strlen은 char의 연속으로 이루어진 기초적인 형태의 문자열의 길이를 구해주는 역할을 합니다. 문자열의 구조를 몰라도 strlen만 있으면 손쉽게 길이를 알 수 있으니 참으로 편리한 함수이지만, 구조를 모르고 아무 곳에나 사용하면 다음과 같은 문제를 겪게 될 수 있습니다. 문자열을 다루는 문제에서 "문자열의 모든 문자를" 하나씩 전부 확인해야 하는 경우가 있습니다. 이 경우 가장 일반적인 방법은 아래와 같이 for 루프를 도는 것입니다. char str[1000001]; scanf("%s", str); for (int i = 0; i < str의_길이; i++) { str[i]에_대한_연산; } str의 최대 길이가 100만인 문제에서, str의_길이를 구하기 위해 다음과 같이 코드를.. 공감수 1 댓글수 0 2022. 12. 19.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.