PS, 코테 입문자들을 위한 백준 가이드 (시간복잡도, 언어별 추가 시간, solved.ac)

(수정 중...) 원래 동아리 활동용으로 남들이 안 알려주는 정보만 모아놨었지만, 생각보다 유입이 많아 보다 더 일반적인 정보도 다룰 수 있게 수정 중입니다

1. 시간복잡도

거의 모든 백준 문제들은 시간복잡도를 명시하지 않습니다. 코드 내용과 실행 시간만 보고 시간복잡도를 100% 정확히 결정하는 일이 불가능하기 때문입니다. 따라서 백준 문제들은 데이터의 크기와 개수를 통해 문제가 요구하는 시간복잡도를 암시하고 있습니다. 예를 들어 지문에서

"시간 제한 : 1초"
"첫째 줄에 수열의 길이 n이 주어진다. n은 5,000 이하의 자연수이다."

라고 하면, 문제가 요구하는 시간복잡도는 \( O(n^2) \)입니다. 다음은 상황에 따라 문제가 요구하는 시간복잡도를 간단히 정리한 표입니다.

	시간복잡도	대표 알고리즘
n <= 10	\( O(n!) \)	Bruteforcing
n <= 20	\( O(2^n) ~ O(n^2 \times 2^n) \)	Bitmask DP
n <= 50	\( O\left(\sqrt{2}^n \right) \)	MITM
n <= 500	\( O(n^3) \)	Matrix Chain Multiplication
n <= 5,000	\( O(n^2) \)
n <= 100,000	\( O(n \sqrt{n}) ~ O(n \log^2{n}) \)	Mo's
n <= 1,000,000	\( O(n \log{n}) \)	Sorting, LIS, etc...
n <= 10,000,000	\( O(n) \)	Fibonacci (DP), DFS, Tree traversal
그 이상	\( O(\log n), O(1) \)	Binary search, Exponential, Hashing

그런데 이렇게 보니까 이걸 언제 다 외우나 하고 가슴이 답답해집니다. 이 값을 외우지 않고도 시간복잡도를 가늠하는 쉬운 방법이 있습니다. n에 직접 숫자를 넣어 보는 것이지요. 이게 대체 무슨 소리인지 이해하기 전에 알아둬야 할 사실이 하나 있습니다.

"컴퓨터는 1초에 1억-2억 번을 연산할 수 있다."

이게 사실인지는 알려져 있지 않습니다. 사실 사용하는 컴퓨터가 뭔지에 따라 속도는 몇 배씩이나 차이가 날 수 있겠죠. 그럼에도 불구하고 이 명제를 참이라고 믿는 태도는 꽤나 유용합니다. 대부분의 문제는 시간제한이 1초이고, 경험적으로 봤을 때 대부분의 골드급 문제는 0.1초~0.3초 안에 풀릴 수 있도록 설계되어 있습니다. 보통 2000만 번의 연산을 거치면 문제가 풀린다고 가정하는 것이 꽤나 합리적이라는 말이죠. (항상 그런 것은 아니며, 플래티넘~다이아 문제 이상에서는 2억 번의 연산을 요구하는 문제도 심심찮게 나옵니다) 이제 다시 위 표로 올라가서 n에 주어진 값들을 대입해 봅시다. 아마 대부분 3000만 번에서 벗어나지 않을 겁니다.

2. (추가 시간 없음)

 

앗 첨부자료 넣으려고 했는데 실수로 다이아 솔브 사진이 찍혀 버렸네

간혹 백준에서 보이는 (추가 시간 없음)이라는 표시. 무슨 뜻일까요? 이 표시의 뜻을 이해하기 위해서는 먼저 추가 시간이 뭔지부터 알아야 합니다. 많은 분들이 알다시피 Java와 Python은 C++보다 느립니다. 심할 때는 파이썬으로 \( O(n \log n) \)에 풀리는 문제가 C++로 \( O(n^2) \)에 풀리기도 합니다! 그래서 형평성을 위해 Java와 Python에 다음의 추가 시간을 주고 있습니다.

Java : 2배 + 1초
Python : 3배 + 2초

(추가 시간 없음)은 바로 이 추가 시간이 없다는 뜻입니다. 백준은 대회 문제를 다수 보유하고 있는데, 어떤 대회는 "상황에 맞는 언어를 골라 쓰는 것도 능력"이라는 철학 하에 이 추가 시간을 없애는 정책을 세우고 있기 때문입니다. 대표적으로 UCPC가 그런 대회입니다.

3. solved.ac

solved.ac

처음 백준 사이트에 들어가면 2만 개의 문제들의 황량한 행렬을 만나게 됩니다. 이 문제들 중 뭐가 지금 내 실력에 맞는지 알 수 있는 방법이 있을까요? solved.ac는 바로 그 기능을 제공해주는 프로그램입니다.

설정 방법은 간단합니다.

백준 로그인 -> 설정 -> 'solved.ac' 클릭 -> solved.ac 사용하기 -> 다시 설정 -> '보기' 클릭 -> 난이도 보기, 알고리즘 분류 보기를 원하는 대로 설정

4. Chrome Extension Programs (BOJ Extended, 토탐정, BaekjoonHub 등...)

유용한 크롬 익스텐션입니다. 알아서 검색해서 찾으세요!