문제 검수 체크리스트

현재 BOJ에서 열리는 대회에는 일정 기준을 만족하는 검수진이 필수로 요구되지만, 정확히 무엇을 검수해야 하는지에 대해서는 정리된 바가 없습니다.

출제자, 검수자가 신경써야 할 사항을 이 글에서 정리해 보고자 합니다.

지금 시간이 없어서 나머지는 작성 예정입니다.

더 읽기댓글 쓰기

(C/C++) 조건부 컴파일로 디버깅용 출력 한방에 없애기

여러분이 방금 틀렸습니다를 받았던 문제의 코너 케이스를 고쳤다고 해봅시다.

들뜬 마음에 점검도 안하고 바로 백준에 코드를 제출해버립니다!

void AddEdge(int v1, int v2)
{
    adjacencyList[v1].push_back(v2);
    adjacencyList[v2].push_back(v1);
    // 어라? 이거 지웠어야 하는데 그냥 제출해버렸네...
    printf("[DEBUG] Add edge (%d, %d)\n", v1, v2);
}

아... 근데 깜빡하고 디버깅하면서 출력했던 문자열을 안 지우고 제출해서 또 틀렸습니다를 받아버렸습니다...

깜빡하지 않았다고 하더라도, 디버깅용 문자열을 여기저기서 출력했다면 그걸 일일히 찾아서 지우는 것도 꽤 귀찮은 일입니다.

더 읽기댓글 쓰기

이분 탐색(Binary Search) 헷갈리지 않게 구현하기

개요

이분 탐색은 off-by-one error가 발생하기 쉬워서 늘 헷갈립니다.

이분 탐색 문제를 풀다보면 탈출 조건으로 lo <= hi, lo < hi, lo + 1 < hi 중 어느 걸 선택해야 할 지, 정답이 lo인지 hi인지 (lo + hi) / 2인지 모르겠고, 심지어는 while문이 끝나지 않아서 시간초과를 받기도 합니다.

더 읽기댓글 쓰기

❌ fflush(stdin), rewind(stdin) ❌

들어가면서

질문 게시판에 올라오는 C/C++ 코드 중 종종 fflush(stdin) 또는 rewind(stdin) 을 사용한 코드들이 올라옵니다.

결론부터 말하자면, 이런 문장을 쓰는 프로그램은 호환성이 없으며, 구현체가 달라지면 전혀 다른 행동을 할 수 있습니다.

위 두 문장은 Windows 운영체계에서 Microsoft Visual C++ (이후 MSVC)로 컴파일한 프로그램을 실행하고, stdin 이 키보드인 경우에만 원하는 동작을 하고, BOJ 의 채점 환경인 Linux 운영체계에서 GCC 또는 clang 로 컴파일한 프로그램을 실행하고, stdin 이 파일인 경우에는 전혀 다른 동작을 합니다. 이 두 함수의 원래 의미를 설명하는 것으로 글을 시작하겠습니다.

더 읽기댓글 쓰기

C++ 유용한 문법들

이 글은 유용한 문법 및 함수들을 소개하는 글입니다.
"요약 노트" 정도로 생각해주시면 될 것 같습니다.
그래서 구체적인 원리나 주의사항, 확장 가능성에 대한 이야기는 생략하겠습니다. 궁금한 부분에 대해 댓글로 남겨주시면 답해드리도록 하겠습니다 :)
제 원문은 이 링크입니다.
이를 축약해서 백준 블로그에 올립니다.

  • f, l은 앞 주소와 뒷 주소를 나타내고, 여러 개면 번호를 1부터 차례대로 붙였습니다. (f, l은 first와 last의 약자, [f,l)임에 유의하세요)
  • func은 호출할 함수를 나타냅니다.
  • 비교기반 함수에 대해서는 cmp 함수를 추가하는 것이 항상 가능하므로, 생략하였습니다. (cmp는 compare의 약자)
  • max가 있으면 min도 있습니다.
  • 맨 첫 줄에 #include <bits/stdc++.h> 구문을 작성했다고 전제합니다.

노트처럼 사용하실 수 있도록 모아놓고 싶었습니다. 의견은 언제든 환영이고, 앞으로도 이 글은 지속적으로 개선해나가겠습니다.

입출력

  • cin.tie(0)->sync_with_stdio(0): 속도 개선
  • endl'\n'로 대체하기: 속도 개선
  • getline(cin, s): 공백까지 통째로 한 줄 입력

더 읽기댓글 쓰기

Fast I/O 구현 코드

안녕하세요 jinhan814입니다. 제가 문제를 풀면서 자주 사용하는 FastIO 구현 코드를 공유하면 좋을 거 같아서 BOJ 블로그에 글을 작성해보았습니다.؜

(참고 : https://blog.naver.com/jinhan814/222266396476)

؜

더 읽기댓글 쓰기

알고리즘 문제풀이를 함에 있어서 자주 접하게 될 용어들

이런 약자들에 대해 다룬 글이 하나쯤은 있었을 것 같지만, 잘 나오지 않아서 정리해 보았습니다. 이런 종류의 글은 백준 블로그에 어울리지 않았을까 하는 생각이지만, 저도 처음 써보는 거라 이상한 점 있으시면 피드백 주세요^^

OJ들 (Online Judge)

  • BOJ,백준: Baekjoon Online Judge
  • CF,코포: Codeforces
  • 앳코: Atcoder
  • USACO: USA Computing Olympiad
  • xOI: (지명) Olympiad in Informatics (ex. InternationalOI, BalticOI, KoreaOI, JpaneseOI,...)
  • ICPC: International Collegiate Programming Contest

기본 용어들

  • PS: Problem Solving (문제 풀이)
  • CP: Competitive Programming (경쟁 프로그래밍)
  • CS: Computer Science (컴퓨터 과학)
  • STL: Standard Template Library (표준 템플릿 라이브러리)
  • 맞왜틀: 맞는 것 같은데 왜 틀리지
  • 틀왜맞: 틀릴 것 같은데 왜 맞지
  • 솔브닥: Solved.ac 티어 안내 서비스
  • 업솔빙: $\frac{\mathrm{absorbing + upsolving}}{2}$ (≈대회 때 못 푼 문제/헷갈리는 문제를 곱씹어보는 과정)
  • 예제: 문제에서 주어진 input과 output
  • 테케: 테스트 케이스의 약자로, 예제의 일반화. 조건을 만족한다면 다 통용해서 사용함.
  • 섭테: 서브 태스크의 약자로, 부분 문제를 뜻함. 각 부분 문제에는 조금씩 배점이 부여됨.
  • 올솔: All Solve! 다 풀어낸 경우
  • NGD: 노가다. 수학에서 자주 쓰여서 자연스럽게 PS에서도 통용됨.
  • $\mathrm{wlog}$: $\mathrm{Without\, Loss\, Of\, Generality}$의 약자. 일반성을 잃지 않는다는 뜻인데, 예를 들어 $a, b, c$ 세 수의 관계가 대칭적일 경우 $a\leq b\leq c$라고 순서를 강제하는 것이 있다.
  • $\mathrm{isw}$: $\mathrm{In\; the\; Same\; Way}$의 약자. 직역하면 같은 방식으로. 값만 바뀌고 동일한 구조를 유지하는 경우 똑같은 것을 또 쓰는 것을 막기 위함이다.
  • $\mathrm{s.t.}$: $\mathrm{such\; that}$의 약자. '다음을 만족하는' 이라는 뜻이다.
  • ∎: 증명 완료
  • $\mathrm{i.e.}$: $\mathrm{id\; est}$의 약자. 영어로는 that is 정도의 의미이다. '즉,'과 같은 의미이다. (사실 '즉'이 더 짧은 것 같은데?)
  • $\forall$: for all이라는 뜻. "모든 ~에 대해서"
  • $\exists$: exists라는 뜻. "~가 존재한다"

채점 결과

  • AC: Accepted = 맞았습니다!!
  • CE: Compile Error = 컴파일 에러
  • MLE: Memory Limit Exceeded = 메모리 초과
  • PE: Presentation Error = 출력 형식이 잘못되었습니다
  • OLE: Output Limit Exceed = 출력 초과
  • RE: Runtime Error = 런타임 에러
  • TLE: Time Limit Exceeded = 시간 초과
  • WA: Wrong Answer = 틀렸습니다
  • UB: Undefined Behavior, 배열 인덱스 밖으로 벗어난 곳을 참조하는 경우가 대표적. 링크 : UB에 관한 evenharder님의 글 참고!
  • 더 참고할 만한 것들: 링크 : 틀리는 이유에 관한 백준님의 글 참고!

더 읽기댓글 쓰기

BOJ의 Good Bye, BOJ 2020!

12월 26일

2020년 12월 26일 토요일, 이 날은 BOJ에서 7개의 대회가 동시에 열린 날이었습니다. 이 날은 17시 23분부터 48분까지 채점 현황이 너무 느린 문제가 발생했습니다. 제출은 정상적으로 되지만, 제출 후에 바로 넘어가야하는 채점 현황 페이지가 열리지 않아 제출이 정상으로 되었는지 확인을 할 수 없는 문제가 있었습니다. 채점 현황이 너무 느려 채점이 약 5분 정도 밀려 결과를 볼 수 없었습니다.

지난 블로그: 2020년 7월 25일 서버 사고 이후 약 2달간 당시 사고를 재현해보고, 원인이 무엇이었는지, 각 원인이 어떤 연관 과정을 가졌는지 파악하는데 성공했습니다. 이후 일부 대비를 했지만, 원활한 대회 진행에 방해가 되는 현상은 피할 수 없었습니다.

더 읽기댓글 쓰기

BOJ의 2020년 마무리

안녕하세요.

2020년을 마무리하며 BOJ의 2020년을 정리해봤습니다.

먼저 올해는 BOJ의 10주년이었습니다. 10주년 기념으로 뭔가를 해보려고 했으나, 준비할 시간이 부족해 하지 못했었습니다. 10주년이 아니더라도 이벤트는 언제든 할 수 있으니 시간이 조금 나는대로 준비해보겠습니다.

더 읽기댓글 쓰기

2020-2021 ICPC 일정 정리

매년 문제를 업로드 하기 위해 캘린더에 정리하고 있는데, 올해는 미정이 많아 이곳에 정리합니다.

North America

더 읽기댓글 쓰기