백준 팁

1. PS 용어
   • 맞왜틀: 분명히 코드를 맞게 짠 것 같으나 틀릴 때 씁니다.
   • TLE: time limit exceeded(시간초과)
   • MLE: memory limit exceeded(메모리 초과)
   • WA: Wrong Answer(틀렸습니다)
   • AC: Accepted(맞았습니다)
   • cp: competitive programming의 약자입니다. 정해진 시간 동안 알고리즘 문제를 해결하는 것으로, ps에 시간 제약이 추가된 것입니다. 백준은 ps에 가깝고, cp는 보통 코드포스에서 연습합니다.
   • 그레이, 그린, 민트, 블루, 퍼플, 오렌지, 레드, 누텔라: 코드포스에서의 티어입니다.
   • 업솔빙: 대회 중에 못 푼 문제를 대회 종료 후 해설을 보거나 추가로 공부하여 풀어내는 것을 말합니다.
   • UB: Undefined Behavior의 약자입니다.
2. 맞왜틀 해결 팁
   • 98%, 99% 정도까지 채점 후 틀렸다면 n=1과 같은 코너케이스에서 틀렸을 확률이 높습니다. 이유는 모르겠으나 보통 이런 코너케이스들이 테스트케이스의 마지막 부분에 위치해 있는 경우가 많습니다.
   • 채점메세지에 틀린 이유가 이상하게 나오는 경우가 가끔씩 있습니다. 예를 들면 딱히 메모리를 많이 쓰지 않았는데 MLE를 받았거나, 포인터를 쓰지 않았는데 double free등을 받는 경우가 있습니다. 이런 경우는 전부 UB 때문입니다. signed 자료형에서 오버플로우가 발생했거나, 0으로 나눴거나, 함수에서 리턴을 하지 않았거나, outOfBounds 등이 보통 유력한 원인입니다. UB이므로 전혀 관련없는 이상한 채점결과가 나올 수 있습니다.
   • https://testcase.ac/ 반례를 찾아주는 사이트입니다. 확장 프로그램도 있으니 설치합시다. 푼 사람이 많은 유명한 문제라면 높은 확률로 반례를 찾을 수 있습니다.
3. 문제 입력 확인용 꼼수
   • 문제에서 어떤 입력이 주어지나 확인하는 꼼수가 있습니다. 아래와 같은 코드를 사용해 문제입력의 조건에 따라 채점결과가 다르게 나오도록 한 뒤, 채점결과가 런타임에러인지 / 시간초과인지 / 출력초과인지 를 확인하여 역으로 유추할 수 있습니다.
   • if (cond1) assert(false); // 런타임에러(assertionFailed)
   • else if (cond2) while(1); // 시간초과
   • else if (cond3) for (int i = 1e8; i--;) cout << " "; // 출력초과
   • 근데 써본 기억은 거의 없습니다.
4. 알고리즘 블로그 보는 법
   • 알고리즘 설명 블로그들을 읽다 보면 참고하라고 걸어둔 링크가 열리지 않는 경우가 많습니다. 그 중 https://www.secmem.org/blog 으로 시작하는 링크의 경우 도메인이 바뀌어서 그렇습니다. 앞부분만 https://infossm.github.io/blog 로 바꾸면 됩니다. 예시입니다: https://infossm.github.io/blog/2019/12/12/HLD/ 
     infossm.github.io의 글들은 google에 그냥 검색하면 잘 노출되지 않습니다. 좋은 글들이 정말 많기 때문에 심화 알고리즘을 공부할 땐 infossm을 같이 검색해보는 걸 추천드립니다. 예를 들면 공부자료를 찾기 힘든 알고리즘 중 하나인 매트로이드도, "매트로이드 infossm"처럼 검색하면 결과가 나옵니다.
5. 문제 해설 찾는 법
   
   • 대회에서 출제된 문제의 경우 공식 에디토리얼이 있는 경우가 많습니다. 백준에서 열린 대회라면 백준 문제 화면 하단의 출처 탭에서 대회 링크를 클릭해 들어가면 보통 해설 pdf가 있습니다. 대회 화면에 pdf가 없는 경우, 공지사항 탭에 해설이 있는 경우도 있습니다. 만약 여기에도 없다면, 백준 홍보 게시판(https://www.acmicpc.net/board/list/ad)에 올라와 있는 경우도 많습니다. 다행히 홍보 게시판에 검색 기능이 제공되므로 대회 이름을 검색해보실 수 있습니다.
   • 가끔 해설pdf링크는 있지만 링크가 유효하지 않은 경우가 있습니다. 이 경우 구글에 해당 pdf의 이름을 그대로 검색하면 제대로 된 링크가 나오던데 이유는 모르겠습니다.
   • 아무리 검색해도 문제 해설이 잘 안나온다면 https://darkbzoj.cc/problems 에서 찾아보시기를 추천드립니다. 비공식 해설이나 다른 사람들이 AC받은 코드를 볼 수 있습니다. ICPC/IOI 등 대회 기출이라면 더더욱 높은 확률로 찾을 수 있습니다. 전 보통 대회이름과 년도로 검색합니다.(예를 들면 'noi2013')
6. 확장프로그램
   • https://marketplace.visualstudio.com/items?itemName=DivyanshuAgrawal.competitive-programming-helper (cph): vscode 확장입니다. 테스트케이스들을 넣으면 자동으로 채점해주는 확장입니다.
   • https://chromewebstore.google.com/detail/competitive-companion/cjnmckjndlpiamhfimnnjmnckgghkjbl (competitive-companion): cph와 함께 굉장히 많이 쓰이는 확장입니다. 백준 문제 페이지에서 단축키 한번만 누르면 테스트케이스를 cph로 긁어와줍니다. 백준뿐 아니라 웬만한 ps/cp사이트는 전부 지원합니다.
   • https://chromewebstore.google.com/detail/testcaseac/idemfboidcafddhdkhbniobcioacjfkm (testcase.ac): 백준 문제들에 대해 반례를 찾아주는 확장입니다.
   • https://chromewebstore.google.com/detail/boj-extended/mfcaadoifdifdnigjmfbekjbhehibfel (boj-extended): 백준 전용 확장입니다. 정말 많은 기능이 있는데, 저는 개인적으로 WA를 받았을 때 몇%에서 틀렸는지 영구적으로 보여주는 기능과, 채점현황⋅그룹⋅랭킹 화면 등에서 사람들의 닉네임 옆에 솔브닥 티어를 같이 표시해주는 기능 때문에 사용합니다. 아쉽게도 firefox에선 버그가 몇 있는데, 개발자분이 Firefox add-ons에 등록했던 계정의 로그인에 문제가 생겨 업데이트하지 못하고 계신 듯 합니다.
   • https://chromewebstore.google.com/detail/%ED%86%A0%ED%83%90%EC%A0%95/hannhecbnjnnbbafffmogdlnajpcomek (토탐정): 백준 전용 확장입니다. 알고리즘 분류 가리개, 랜덤디펜스 등 여러 기능을 제공합니다. 테마가 예쁩니다.
   • https://chromewebstore.google.com/detail/boj-random-defense/dcjggddbgfeieokmfbefkeompjkcjiee (BOJ Random Defense): 백준 랜덤디펜스용 확장입니다. 다른 랜디 확장들과의 차별점은, 따로 제공되는 레이팅 시스템이 있다는 점입니다. 솔브닥에서 유저들을 구경하다보면 프로필 메세지에 dcb14c79-48cd-48d6-a6e9-e4911af39165처럼 이상한 문자열이 적혀있는 경우가 있는데, 이 확장과 연동을 한 흔적입니다.
   • https://chromewebstore.google.com/detail/%EB%B0%B1%EC%A4%80%ED%97%88%EB%B8%8Cbaekjoonhub/ccammcjdkpgjmcpijpahlehmapgmphmk (BaekjoonHub): 백준에서 문제를 풀면 자동으로 깃허브에 커밋해줍니다. 잔디 심기에 좋습니다.
   • https://chromewebstore.google.com/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn (Carrot) : 코드포스 국룰 확장입니다.
7. 추가로 읽어보면 좋은 자료들입니다.
   • C/C++의 undefined behavior(https://infossm.github.io/blog/2020/01/17/c-c++-and-ub/)
   • PS에서의 런타임 에러와 디버깅(https://infossm.github.io/blog/2020/09/19/rte/)
   • 자주 틀리는 요인(https://www.acmicpc.net/blog/view/146)