알고리즘 문제해결 분야는 정말 매력적입니다. 어려운 문제를 해결했을 때의 뿌듯함과 차근차근 실력을 쌓아가면서 느낄 수 있는 성취감을 더 많은 분들께서 느껴 봤으면 좋겠다는 생각을 가지고 있습니다. 그래서 solved.ac를 만들어나가는 것은 제가 가장 즐거워하는 일이면서 제가 정말 잘 할 수 있는 일입니다. 이 일에 집중하면서 제 역량을 온전히 발휘하기 위해 넥슨 엔진스튜디오에서 퇴사하고 창업에 나서기로 결심했습니다.

토이 프로젝트로 만들어 오던 solved.ac를 사업으로서 영위하기 위해 2022년 12월 5일 ‘솔브드’로 개인사업자 등록을 완료했습니다. 2019년 6월 5일에 개발을 시작했으니 딱 3년 반 만입니다. 솔브드는 그 동안 9만 명의 프로그래머 분들께 알고리즘 문제해결을 공부하는 여정에 도움을 드렸습니다.

앞으로도 ‘알고리즘 문제해결 학습의 이정표’에 걸맞는 서비스가 되도록 노력하겠습니다. 특히 컴퓨팅 사고력과 코딩 테스트의 중요성이 대두되고 알고리즘 문제해결 애호가들이 어느 때보다 많아진 지금, 학습자들과 애호가 모두를 아우를 수 있는 이정표를 마련하기 위해 끊임없이 개척해 나가겠습니다. 기여자 분들의 노고를 폄하하거나, 문제해결과 실력 상승의 재미를 해치고 박탈감을 발생시키는 사업 모델 등은 지금도 앞으로도 도입하지 않을 것입니다.

잘 부탁드리겠습니다. 감사합니다!

$$ $\newcommand{\eps}{\varepsilon_{\mathrm{m}}}$ $\newcommand{\F}{\mathbb{F}}$

프로그래밍 문제를 출제하다 보면 가끔 실수를 다루는 문제를 출제하고 싶어질 때가 있습니다. 웬만하면 모든 걸 정수로 하면 좋겠지만 문제 상황이 그렇지 못할 경우도 존재하죠. 그러나 우리가 다루는 실수는 사실 정확히 말하면 실수가 아니기 때문에 조심해야 할 점들이 꽤나 있습니다.

이 글은 floating point 실수 연산의 오류 분석과, 이를 기반으로 프로그래밍 문제에서 좀 더 옳은 정답 데이터를 만드는 방법에 대해 소개합니다. 굳이 문제나 데이터를 만들지 않더라도 일반적으로 프로그래밍 문제에서 실수를 다루는 데에 참고하면 도움이 될 것입니다.

IEEE 754

아마 float이나 double 등을 처음 배울 때 한 번쯤은 봤을 법한 그림입니다. 지금은 잊어버렸을 수도 있겠습니다만, 아무튼 컴퓨터가 실수를 그렇게 정확하게 나타내지는 못한다는 것쯤은 알고 계시리라 생각합니다.

사실 float과 double은 아무 실수나 나타낼 수 있는 것이 아니며, 분모가 $2^n$인 유리수만을 나타낼 수 있습니다. 심지어 $0.1$과 같은 우리가 보기에 간단해 보이는 유리수도 분모를 $2^n$으로 나타낼 수 없기에, double x = 0.1을 하면 $0.1$이 아니라 $0.1$을 최대한 근사한 값¹이 들어가게 됩니다.

양수 float 값 $q$는 일반적으로 다음과 같이 저장됩니다²:

여기서 $A$는 음이 아닌 정수이고, $B$는 소숫점 아래에 쓸 수 있는 $0 \le B < 1$의 이진수 소수입니다. 수의 크기에 따라 $A$를 조절해서 $\left[1, 2\right)$보다 크거나 작은 수를 표현할 수 있습니다.

int, long long 등에 제한이 있듯이 float, double도 한정된 비트를 사용하는 만큼 제한이 있습니다. 아래 정보는 일반적인 온라인 저지 환경에서의 GCC를 가정합니다.

자릿수가 제한되어 있는 만큼 이산적입니다. 예를 들어 $3$자리만 사용할 수 있는 상황이고 $A = \mathit{bias}$, 즉 $q = 2^0 \times \left(1+B\right) = 1+B$라고 한다면 $1.\underline{000}_2=1$과 $1.\underline{001}_2=1.125$ 사이의 수는 표현할 수 없게 되는 것입니다.

사실 $A$나 $\mathit{bias}$보다 중요하게 봐야 할 건 $B$의 유효숫자 수입니다. 이게 전부 $2$진수라서 생각하기 어려울 수 있으니 $\log_2 10$로 나눠서 생각해 보면 이렇습니다.

이 이후부터는 참값과 근삿값을 구분해야 할 일이 있으면 다음과 같은 표현법을 쓰도록 하겠습니다. $\F$는 ECMAScript 스펙에서 따왔습니다.

그리고 편의를 위해 $\mathit{bias}$는 $A$에 이미 더해져 있다고 생각하겠습니다.

정확도의 소실

유효숫자가 정해져 있다 보니 불가피하게 정확도의 소실이 일어납니다. 그래서 일반적으로 실수를 다루는 문제들은 절대/상대 오차 얼마 이하는 정답으로 간주합니다. 하지만 문제를 만드는 입장에서는 정해의 오차가 얼마 정도인지를 정확히 알고 있어야 참가자에게 ‘이 정도의 정확성을 갖는 풀이를 제출하십사’라고 요구할 수 있습니다. 반대로는 ‘이 정도의 정확도를 요구하려면 정해가 어느 정도로 정확해야겠구나’를 생각할 수 있겠죠.

여기서 ‘절대 오차’와 ‘상대 오차’에 대해 먼저 설명하도록 하겠습니다.

• $x$의 근삿값 $y$가 $\delta_a$만큼의 ‘절대 오차’를 갖고 있다는 것은 $|x-y| \le \delta_a$임을 의미합니다.

• 반면 $y$가 $\delta_r$만큼의 ‘상대 오차’를 갖고 있다는 것은 $\frac{|x-y|}{x} \le \delta_r$임을 의미합니다. 실생활에서 ‘$1$% 정도의 차이가 발생할 수 있다’같은 표현이 상대 오차 $0.01$이 발생할 수 있다는 것과 같은 표현이겠네요.

이제 자주 사용하는 연산들에서 오차가 얼마나 발생할 수 있는지 하나하나 뜯어보도록 합시다.

입력

조금 전에 참값을 어떻게 float이 다룰 수 있는 값으로 근사하는지 설명했습니다. 참값 $x_\R$를 유효숫자 $p$비트의 float 값 $x_\F$로 나타내려고 한다면 정확히 얼마만큼의 오차가 발생할까요?

일단 $x_\R = 2^A \times \left(1+B_\R\right)$라고 한다면, $B$의 자릿수 제한을 맞춰 주기 위해 $B_\R$을 최대한 가까운 $p$자리 이진 소수로 반올림합니다. 이렇게 하면 $B$에는 최대 $0.5 \times 2^{-p} = 2^{-p-1}$만큼의 절대 오차가 발생하게 됩니다.

$x_\R$과 $x_\F$의 입장에서는 어떨까요? 앞서 언급한 것은 $B$에서의 오차였으므로, $x$ 입장에서 생각하려면 $2^A$를 곱해 줘야 합니다. 그러면 $x$ 입장에서의 절대 오차는 $2^A \times 2^{-p-1}$입니다.

앞서 $A$는 수의 크기에 따라 조정된다고 설명했습니다. 음? 입력받는 값의 스케일에 따라 결정된다구요? 그러면 오차를 절대 오차보다는 상대 오차로 나타내는 것이 괜찮은 옵션인 것 같아 보입니다.

상대 오차는 최대

이고, $0 \le B < 1$이므로

가 됩니다. 따라서 반올림 오차는 상대 오차로 최대 $\frac{2^{-p}}{2}$입니다. 이를 간단하게 나타내기 위해, 부동소수점 수에서 다음 수와의 간격을 나타내는 기계 입실론^{machine epsilon}을 도입해 표기해 봅시다. 기계 입실론은 $\eps$과 같이 나타내고, $\eps = 2^{-p}$이므로 $\frac{2^{-p}}{2} = 0.5 \eps$로 표현할 수 있겠습니다.

결론: 실수를 입력받으면 최대 $0.5 \eps$만큼의 상대 오차가 발생합니다.

double에서 $p=52$임을 생각하면 유효숫자가 $15$자리쯤 된다고 볼 수 있습니다. 따라서 double을 입력받았다면 앞의 $15$자리까지는 믿을 수 있다고 할 수 있겠습니다.

부호가 같은 수의 덧셈

유효숫자 세 자리 float에서, $a_\F=1.\underline{101}_2$와 $b_\F=1\underline{10}.\underline{1}_2$를 더하는 상황을 가정해 봅시다.

그냥 더하면 $\left(a_\F + b_\F\right)_\R = 1\,\underline{000}.001_2$이 되지만, 우리의 float은 유효숫자 $3$개까지만을 허용하므로 $.001_2$ 부분을 날려야 합니다. 따라서 계산된 값을 다시 float에 저장하면 $\left(a_\F + b_\F\right)_\F = 1\,\underline{000}_2$ 부분만이 남습니다.

컴퓨터는 계산 과정에서는 저장하는 float의 두 배 정도의 공간을 사용해 정확하게 계산하고 이후 반올림하기 때문에, 덧셈의 경우에도 반올림 오차 한 번만이 발생합니다. 이는 상대 오차 $0.5 \eps$입니다.

부호가 같은 두 float의 덧셈에서는 $0.5 \eps$만큼의 상대 오차가 발생합니다.

그러나 여기에는 함정이 있는데, $a_\F \ne a_\R$이라는 점입니다. $a_\F$와 $a_\R$는 이미 $0.5 \eps$만큼의 상대 오차를 갖고 있습니다. 따라서 $\left(a_\F + b_\F\right)_\R$와 $a_\R + b_\R$의 상대 오차는 이미 $0.5 \eps$입니다. 여기서 반올림도 수행해야 하므로, 발생할 수 있는 오차는 최대

입니다. $0.25 \eps^2$는 너무 작아서 무시할 수 있습니다(후술). 따라서 다시 결론을 내리면,

결론: 부호가 같은 두 실수를 입력받아 더하면 $\eps$만큼의 상대 오차가 발생합니다.

여담으로 큰 차이가 나는 두 수를 더하면 더하는 것에 의미가 없어질 수도 있습니다. 예를 들어 $a_\F=1\underline{001}_2$과 $b_\F=0.001\underline{101}_2$을 더하는 경우 계산 결과는 $\left(a_\F + b_\F\right)_\R=1\underline{001}.001101_2$이 되지만, 반올림하면 $1\underline{001}_2$이 되어 $a_\F$와 같아집니다. $\eps^2$ 자체는 float으로 정확히 표현할 수 있을지 몰라도, $\eps \times 2$ 이상의 값과 더하면 이와 같은 현상이 나타나기 때문에 생각하지 않아도 괜찮습니다.

곱셈과 나눗셈

이번에는 $a_\F=1.\underline{110}_2$와 $b_\F=1\underline{10}.\underline{1}_2$를 곱하거나 나누는 상황을 생각해 봅시다.

반올림하면 이렇게 됩니다.

계산 과정에서의 정확도 손실은 발생하지 않으며(나눗셈의 경우 무시할 수 있을 정도로 작습니다), 반올림 오차 $0.5 \eps$가 발생합니다.

이번에도 $a_\F \ne a_\R$임을 고려해 봅시다. $\left(a_\F\times b_\F\right)_\R$와 $a_\R\times b_\R$의 상대 오차는 $\eps$가 되고, 반올림을 수행해 $\left(a_\F\times b_\F\right)_\F$로 만들면 $1.5 \eps$가 됩니다. 나눗셈도 같은 방법으로 계산 가능합니다.

결론: 두 float의 곱셈/나눗셈에서는 $0.5 \eps$만큼의 상대 오차가 발생합니다.
두 실수를 입력받아 곱하거나 나누면 $1.5 \eps$만큼의 상대 오차가 발생합니다.

부호가 같은 수의 뺄셈

뺄셈, 혹은 부호가 다른 수의 덧셈은 위에서 언급한 덧셈과 비슷하지만 상황이 조금 다릅니다. 특히 $x_\F \ne x_\R$이면서 차이가 얼마 안 나는 값을 계산하려고 하는 경우입니다.

예를 들어 $a_\F=1.\underline{111}_2$에서 $b_\F=1.\underline{110}_2$을 빼는 경우를 생각해 봅시다. 결과는 $\left(a_\F-b_\F\right)_\R=0.001\underline{0\,00}_2$입니다. 이는 별 문제가 없어 보이지만, 계산 결과에서의 밑줄 친 $\underline{000}$은 $a_\F$에도 $b_\F$에도 없었던 값입니다. 이 새롭게 생긴 유효 비트 $3$개를 그냥 믿기에는 조금 꺼림칙합니다. 다행히도 두 값이 근삿값이 아니라 참값이라면, 즉 $a_\F=a_\R$고 $b_\F=b_\R$라면 계산 결과는 정확하고 믿을 수 있습니다.

하지만 $a_\F$가 정확한 값이 아니라면, 즉 $a_\F$과 $a_\R$의 차이가 크다면 문제가 됩니다. 예를 들어 $1.93$에서 $1.69$를 빼는 상황을 생각해 본다면 정확한 결과는 $0.24$여야 하지만, $1.93_\F=1.\underline{111}_2$, $1.69_\F=1.\underline{110}_2$이므로 $\left(1.93_\F-1.69_\F\right)_\F=0.001\underline{0\,00}_2 = 0.125$가 됩니다. 무려 두 배나 차이가 나네요!

조금 더 극단적인 예로 $|\varepsilon_\F| < \eps$에 대해 다음과 같은 계산을 한다고 가정해 봅시다.

$2 \varepsilon_\F$이 나와야 할 것처럼 보입니다. 그러나 $\varepsilon_\F$이 반올림 오차보다 작으므로 실제로는 아래와 같이 계산됩니다.

이는 무려 $100$%의 상대 오차입니다. 이런 현상을 재앙적인 소거^{catastrophic cancellation}라고도 합니다.³

따라서 뺄셈을 정확하게 하고자 할 경우 비슷한 두 값의 뺄셈을 최대한 피하도록 해야 합니다. 예를 들어 앞서 언급한 $(1+\varepsilon_\F)-(1-\varepsilon_\F)$의 경우, $(1-1)-(-\varepsilon_\F-\varepsilon_\F)$로 계산 순서를 약간 바꾸면 조금 더 정확한 값을 얻을 수 있을 것입니다.

결론: 부호가 같은 두 실수의 뺄셈을 하는 상황은 가급적 피하는 것이 좋습니다.

덧셈, 곱셈, 나눗셈은 상대적으로 훨씬 ‘안전한’ 연산이므로 가능한 경우 덧셈, 곱셈, 나눗셈만을 사용하도록 수정합니다. 일례로 실수 값의 누적 합을 구해야 한다면 대신 펜윅 혹은 세그먼트 트리를 사용할 수 있습니다.

여담으로, 같은 부호이더라도 두 배 이상 차이가 나는 값의 뺄셈은 $\eps$ 이하의 오차만이 발생함을 덧셈의 경우와 비슷한 방법으로 보일 수 있습니다.

뺄셈을 포기할 수 없다면

뺄셈의 오차를 다른 상황과 같이 생각할 수 없는 이유는 없는 유효숫자를 만들어야 하는 상황 때문입니다. 따라서 상대 오차를 계산하기는 어렵습니다. 하지만 절대 오차를 계산해 볼 수는 있습니다.

$a_\R$에서 $b_\R$을 빼는 연산을 생각해 봅시다.

• 우선 이 값들을 입력받는 과정에서 반올림 오차 $0.5 \eps$가 생깁니다. 이 오차는 상대 오차이므로, 절대 오차로 바꾸면 각각 $0.5 \eps a_\R$과 $0.5 \eps b_\R$이 됩니다. 따라서 $a_\R-b_\R$과 $\left(a_\F-b_\F\right)_\R$은 최대 $0.5 \eps \left(|a|_\R+|b|_\R\right)$의 절대 오차를 가집니다.

• 이제 $\left(a_\F-b_\F\right)_\R$을 $\left(a_\F-b_\F\right)_\F$로 근사합니다. 이 과정에서 반올림 오차 $0.5 \eps$가 한 번 더 생깁니다. $0.5 \eps \left(|a|_\R+|b|_\R\right)$의 절대 오차에 $0.5 \eps$의 상대 오차가 한 번 더 생기므로, 총 절대 오차는 $\left[0.5 \eps \left(|a|_\R+|b|_\R\right)\right]\left(1+0.5\eps\right)$입니다.

• 앞서 언급했던 것처럼 $0.25 \eps^2$는 $0.5 \eps$에 비하면 무시할 수 있는 수준이므로, $0.5 \eps \left(|a|_\R+|b|_\R\right)$만큼의 절대 오차가 발생한다고 할 수 있습니다.

따라서 다루는 수들의 스케일을 알고 있다면, 다행히도 발생하는 오차를 절대 오차로나마 가늠할 수 있습니다.

결론: 부호가 같은 두 실수 $a$와 $b$가 있을 때,
$a$에서 $b$를 빼면 최대 $0.5 \eps \left(|a|+|b|\right)$만큼의 절대 오차가 발생합니다.

정리해 보면 이렇습니다.

그러나 이 표에서 언급한 덧셈과 뺄셈에서의 상대 오차는 덧뺄셈 한 번에서 발생하는 오차이고, 덧셈을 계속 누적해나간다면 덧셈을 할 때마다 반올림 오차가 새로 발생하고, 이는 절대 오차로서 더해짐을 간과하면 안 됩니다. 프로그래밍 문제에서는 일반적으로 덧셈을 여러 번 하는 상황이 많기 때문에, 덧뺄셈은 아예 절대 오차로만 생각하는 편이 좋겠습니다. 이렇게 하면 부호가 같은 경우와 다른 경우에 차이가 없어지며, 다음과 같이 다시 한 번 정리할 수 있습니다.

정해 코드의 오차 계산 및 문제 설계

문제에서 얼마만큼의 오차를 허용할지는 정해 코드의 최대 오차를 계산함으로서 정할 수 있습니다.

BOJ #1546 평균과 똑같은 문제를 조금 더 어렵게 세팅한다고 가정해 봅시다. 정해 코드를 이렇게 짰습니다.

double s = 0;

int n;
cin >> n;
while (n--) {
    double x;
    cin >> x;
    s += x;
}

cout << fixed << setprecision(12) << s / n << '\n';

일단 $s$의 오차는 덧셈 $N$번이 누적되므로 높게 잡아도 $N \times 0.5 \eps \left(s+s\right) = Ns\eps$ 이하의 절대 오차가 생깁니다. 마지막에 나눗셈 한 번을 하므로 상대 오차 $1.5\eps$가 한 번 더 생깁니다.

그러면 총 절대 오차는 $Ns\eps$, 총 상대 오차는

가 됩니다.

허용 오차 설정하기

double로 풀리게 하고 싶다면 어떻게 해야 할까요? double에서는 $10^{-16} < \eps < 10^{-15}$이므로 넉넉하게 $\eps = 10^{-15}$로 두고 계산하면, 위 코드의 절대 오차는 $Ns \times 10^{-15}$, 상대 오차는 $\left(N + 1.5\right) \times 10^{-15}$가 나옵니다. 따라서 $N$의 값에 따라 오차 허용 범위가 달라지는데, $N = 10^5$로 설정한다면 상대 오차가 약 $10^{5-15}=10^{-10}$이 되므로 $10^{-9}$ 혹은 그보다 넉넉한 허용 범위를 잡으면 무리 없이 통과할 것입니다. (통상적으로 상대 오차 혹은 절대 오차 중 하나만 범위에 들어오면 맞도록 하기 때문에 그렇습니다.)

반대로 $N = 10^5$인 상황에서 float을 저격하고 싶다면 어떻게 해야 할까요? float에서는 $10^{-7} < \eps < 10^{-6}$이므로, $\eps = 10^{-7}$로 보수적이게 잡으면 상대 오차 $10^{5-7}=10^{-2}$라는 계산이 나옵니다. 따라서 허용 오차 범위를 $10^{-2}$로 잡으면 float을 사용한 코드가 통과하지 못할 가능성이 있고, $10^{-3}$ 혹은 그 이하로 잡으면 float이 통과하기 어려운 문제로 세팅할 수 있을 것입니다.

위의 예시에서도 그렇듯이 float의 경우 덧셈을 $100\,000$번만 하는데도 $10^{-2}$ 혹은 그 이상의 오차가 발생하기 때문에, float 코드는 부정확한 값을 도출하기 상당히 쉽습니다. 그래서 float을 굳이 통과시켜 주려고 의도하는 상황이 아니고서야 float으로 작성한 코드는 그냥 틀렸다고 생각하고, double으로 해결하는 경우만 신경써도 충분합니다.

In Practice

그러나 문제에서 요구하는 계산이 많아지고 복잡해지면 코드마다 사칙연산을 수행하는 횟수가 천차만별일 수 있습니다. 따라서 실수 오차를 신경쓰는 게 문제가 물어보는 주요 포인트가 아닌 이상 실제 세팅할 때는 위에서 언급한 표의 모든 상수를 $10$ 정도로 놓고 오차 허용 범위를 설계하게 됩니다. 앞의 상수는 계산 횟수에 비례하기 때문입니다.

굳이 $10$으로 두는 이유는 앞서 말했듯이 상수와 계산 횟수는 비례하기 때문에, 상수가 너무 커질 정도로 계산 횟수가 많아지면 차라리 시간 초과가 나는 편이 낫기 때문입니다.

데이터 제작

특히 데이터를 제작할 때 주의해야 하는 점이 있습니다. 바로 데이터 자체에 오차가 있는 경우입니다. 데이터도 컴퓨터로 계산하는 것이기에 일반적인 방법으로 만든다면 데이터에도 그만큼의 오차가 생길 수밖에 없고, 이렇게 오차가 있는 데이터를 기준으로 채점하면 오히려 맞아야 하는 답을 틀리다고 채점하게 될 수도 있습니다. 실수를 많이 다뤄보지 않은 세터가 꽤 흔하게 하는 실수입니다.

이를 방지할 수 있는 방법은 여러 가지가 있는데, 몇 가지를 소개하자면:

• long double, __float128, Python Decimal, Java BigDecimal 등 double보다 훨씬 정확한 자료형을 통해 계산합니다.

• 가능한 경우 모든 계산을 정수로 수행합니다. 분모와 분자를 관리하는 분수 구조체를 만들거나, Python Fraction을 사용하는 것도 고려해 볼 수 있습니다.

정해 소스의 오차가 최대 얼마인지를 계산하는 것의 중요성을 강조하고 싶습니다. 개인적으로 double로 풀리게 하고 싶다면 데이터는 적어도 최대 $10^{-15}$만큼의 오차만을 갖도록 만드는 것을 권장합니다.

여담

사칙연산 이외의 함수들의 오차는 어떻게 구하나요?

IEEE 754는 사실 아래의 연산들에 대해 가장 가까운 실수를 계산할 수 있도록 하고 있습니다⁴. 의외로 제곱근이 들어가 있습니다.

• 사칙연산

• 제곱근

• 단일 곱셈 누산

• 나머지 연산

• 최대 및 최솟값

C는 이를 따라서, sqrt와 fmod는 반올림 오차, 즉 상대 오차 $0.5\eps$만을 가지도록 합니다. 단, 이는 인자들이 참값임을 가정한 오차임에 주의해야 합니다.

제곱근을 제외하고, GNU C에서 실수와 관련된 함수들의 구현과 오류의 대략적인 양은 문서에 명시되어 있습니다. 문서에서 명시된 ULP^{unit in the last place}는 이 글에서 언급한 기계 입실론과 같은 단위인데, 상대 오차입니다.

보통 채점 환경으로 주로 사용되는 x86_64에서의 주요 함수의 오차는 다음과 같습니다. 모두 계산 결과에 대한 상대 오차이므로, 입력값의 오차를 따로 고려해 줘야 함에 유의합니다.

• sin, cos, tan, asin, acos, atan: $\eps$

• pow, exp, expm1, log, log1p: $\eps$

• hypot: $\eps$

• sinh, cosh, tanh, asinh, acosh, atanh: $2\eps$

• cbrt: $4\eps$

일부 함수들은 정의역이 제한되어 있으므로(예를 들어 acos는 $-1$과 $+1$ 사이의 입력만 허용합니다) 계산 과정에서 실수로 정의역을 벗어나는 값을 넣지 않도록 주의해야 합니다. 또한 아래 함수들은 특정 범위의 입출력을 피하거나, 입력 범위에 각별히 주의하는 것을 요합니다.

• log: 출력값이 $0$에 가까울 것으로 예상하는 경우.

  • $\log \left(x+1\right)$이 필요한 상황이라면 $x$의 값을 조금 더 정확히 입력할 수 있는 log1p 함수를 사용합니다: $\operatorname{log1p} x=\log \left(x+1\right)$.

  • $x$가 작다면, $x+1$을 계산하는 데에서 이미 정확도의 손실이 일어납니다.

• exp, pow: 출력값이 $1$에 가까울 것으로 예상되는 경우.

  • $e^x-1$의 정확한 값이 필요한 상황이라면 마찬가지로 expm1 함수를 사용합니다: $\operatorname{expm1} x=e^x-1$.

• fmod: 나눠지는 값이 나누는 값보다 너무 큰 경우.

  • 인자가 참값이 아니라 반올림된 값일 경우 뺄셈과 비슷하게 재앙적 소거가 쉽게 발생할 수 있습니다.

여담으로, tan 함수의 경우 $\left(\frac{1}{2}+n\right)\pi$ 왼쪽에서는 $+\infty$로 발산하고 오른쪽에서는 $-\infty$로 발산하지만, 어떤 부동소수점 값도 $\left(\frac{1}{2}+n\right)\pi$를 정확히 표현할 수 없어서 우려하는 오류가 발생하지 않습니다.

일부 연산은 CPU가 직접 지원하고, CPU의 구현에 따라 오차가 다르게 발생하는 경우가 존재합니다. 예를 들어 exp10 함수는 CPU가 10의 $N$제곱 연산을 지원한다면 코드로 계산하려고 하지 않고 하드웨어로 __builtin_exp10을 통해 더 빠르게 계산하려고 할 것입니다.

glibc 소스에서도 상세 구현을 확인하고 오차를 가늠할 수 있습니다.

다른 방식으로 오차를 구하는 글도 있던데 여기서는 왜 이렇게 구하나요?

아마 $a \pm b$의 오차 $\delta \left(a \pm b\right)$는 $\sqrt{\left(\delta a\right)^2+\left(\delta b\right)^2}$라고 설명하는 글을 보셨을지도 모르겠습니다. 이는 물리학 등에서 $a$와 $b$가 여러 번의 측정을 통해 얻어낸 평균값이고, 오차가 확률분포(특히 정규분포)에서 추출될 것이라고 가정할 수 있을 때 사용하는 방법입니다. 즉, 우리가 다루는 오차와는 다른 성격의 오차입니다. 여기에서는 수치해석적 관점에서의 오차 전파를 다루고 있습니다.

마무리하면서

부동소수점 오차는 참 다루기 힘든 주제입니다. 이 글이 부동소수점 오차에 대한 막연한 가늠과 추측을 해소하고 좀 더 좋은 문제들을 만드는 데 기여해, 제가 백준에서 맞왜틀을 덜 당할 수 있기를 희망합니다.

이 글 작성에 도움을 주신 김영현^kipa00님과 김준원^junie님께 감사의 말씀을 전합니다.

각주

1. double의 경우 $0.1_\F$은 정확히

   $$0.1000\,0000\,0000\,0000\,0555\,1115\,1231\,2578\,2702\,1181\,5834\,0454\,1015\,625$$

   입니다. ↑

2. $q=0$, $q=+\infty$, $q=\,$NaN, 그리고 $A = 0$인 경우는 예외입니다. ↑

3. 반면 두 값이 참값인 경우에서 일어나는 현상은 온화한 소거^{benign cancellation}라고 합니다. ↑

4. https://en.wikipedia.org/wiki/IEEE_754#Required_operations ↑

(23/7/19) 사칙연산 이외 함수들에 대한 설명을 추가했습니다. kiwiyou님께 감사의 말씀을 드립니다.

ICPC 월드 파이널 참석 후기 — Привет!

버거킹을 먹은 후에는 인터넷으로 미리 코로나 검사를 예약하고 인천공항 코로나 검사센터에서 검사를 받았습니다. 당시에는 보건소에 가면 누구나 무료로 코로나 검사를 받을 수 있던 시절이었지만, 보건소 검사결과는 언제 나올지 모르는 반면 러시아 입국 시각을 기준으로 72시간 내에 받은 검사 결과가 필요했기에 한 명 당 10만 원 가량의 거금을 들여서 검사를 받았습니다.

비행기는 오후 11시 반에 출발합니다. 오후 1시에 PCR 검사를 받고 무려 10시간을 때워야 하는 슬픈 상황입니다.

사실 레드시프트가 해외 대회를 치러 간 건 처음이 아닙니다. 2019년에 태국 방콕 리저널에도 참가했었는데요, 당시 제가 팀노트 25장 × 3권을 무려 잉크젯 프린트로 인쇄하느라 늦어서 공항철도에서 내리자마자 게이트까지 뛰어갔는데도 비행기를 놓칠 뻔 한 적이 있었던지라 이번엔 일찍 공항에 왔습니다.

카드 셔플 문제의 출제자 semteo04는 서강대학교 마술 동아리 MASU-Z 부원입니다. 시간을 때우면서 신기한 마술들을 볼 수 있었어요.

제가 모스크바 여행을 다녀온다고 하니 solved.ac 일러스트 작가님이 여행객 한별이 아크릴을 선물해주셨습니다. 제가 평소에 메고 다니는 가방이랑 같은 걸 메고 있네요. 저는 정말 성덕이 아닐까요? 이 글을 빌어 다시 한 번 감사의 말씀을 드립니다 🙏 

오래 걸어다니다 보니 피곤하고 덥고 온 몸이 땀 범벅이 돼서 샤워할 수 있는 곳을 알아보다가, 면세영역에 샤워실이 있다고 해서 일단 출국심사를 받았습니다.

오른쪽이 출국심사대입니다. 심각한 코로나 상황을 보여주기라도 하듯 사람이 몇 명 안 보이는 공항 면세영역입니다. 터키나 러시아는 어떤 상황일지, 우리가 다녀오는 동안 우리나라는 어떻게 될지 걱정이 앞섭니다. 면세구역 중앙이라 아직 몇 명 보이기는 하지만 게이트와 가까워질수록 우리 말고는 아무도 없어서 비현실적인 기분이었습니다.

그리고 아쉽게도 코로나 상황 때문에 샤워실은 문을 닫았더라구요.

그렇게 이 시국에 해외에 나가보게 되었습니다.

앞선 포스트에서 언급했던 것과 같이 이 여정은 터키항공 TK091편으로 튀르키예(당시 터키)의 수도 이스탄불까지 날아가고, 여기서 환승해 터키항공 TK413편으로 러시아 브누코보 공항까지 가는 여정이었습니다. 여정표만 보면 5시간 반 정도만에 갈 수 있을 것 같지만 튀르키예와 한국의 시차는 6시간이라 TK091편만 무려 11시간 반이나 걸립니다. 가 본 곳이 전부 아시아뿐이라 6시간 초과의 비행기를 타본 적 없는 저로서는 걱정 반 설렘 반이었어요. 와 내가 드디어 시차 적응이라는 걸 해볼 수 있다니!

운좋게도 제가 창가 자리라서 인천 야경을 찍을 수 있었어요.

11시간 반 앉아 있으면 굉장히 배고프죠. 밤에 출발한 비행기라서 저녁 기내식이 나왔습니다. 공항에서 저녁을 먹었지만 그냥 또 먹기로 합니다.

기내식은 비빔밥과 물고기 요리 중 하나를 고를 수 있었고 비빔밥은 외국 항공사 기내식 치고는 꽤 맛있었습니다. 터키항공은 튀르키예의 자존심인가?

심지어 이 비행기는 (꽤 비싼 값을 주면) 엄청 느린 위성 인터넷을 쓸 수 있게 해 줍니다. 기내에서 여자친구에게 깜짝 밤인사를 전할 수 있었어요. 트위터를 할 수 있는 속도는 아니었고….

그렇게 밥을 먹고 편하게 잤습니다. 자고 일어나니까 밥을 한 끼 더 줍니다.

11시간 반 비행이라 기내식이 두 개 나오는 것 같네요. 약간 느끼하지만 맛있었습니다.

어떻게 보면 한나절동안 정말 아무것도 안 하고 앉아만 있는 거라 약간 사육당하는 느낌이 들더라구요. 하지만 피곤했기 때문에 먹고 또 바로 잤어요.

얼마 안 잤는데 튀르키예에 거의 도착해 있었습니다. 11시간 알차게 보냈네요! 답답한 비행을 가장 알차게 보낼 수 있는 방법은 바로 수면이 아닐까 싶네요.

굉장히 숙련된 파일럿이었는지 비행기 착륙을 무슨 고급 세단 승차감이 들도록 할 수 있다는 걸 처음 알았습니다. 터키항공은 신인가?

아무튼 러시아에 가자마자 호텔에서 씻겠다는 다짐으로 가득한 네 명은 지친 몸을 이끌고 환승을 합니다.

이스탄불 국제공항은 웅장한 별천지였고 튀르키예는 다른 세계에 온 건가 싶을 정도로 사람이 많았습니다. 당시 우리나라 방역 상황에서는 상상하기 힘든 인파입니다.

샤워실 안내판이 눈에 띄고 면세점 내에 제가 정말 좋아하는 쉐이크쉑도 있었지만 환승 시간 간격이 그렇게 여유가 있는 편은 아니라서 바로 게이트로 이동하기로 합니다.

현지시각 새벽 5시에 도착했고 새벽 7시 45분 비행기를 타야 되기 때문에 날이 밝아오는 걸 볼 수 있었습니다. 우리나라와의 시차는 6시간이지만 비행기에서 너무 잘 잤는지 시차는 이미 적응해버렸습니다.

최종 목적지인 모스크바로 출발합시다! 이번엔 두 시간만 가면 됩니다.

보통 서울-제주 비행기는 기내식을 주지 않는데 터키항공 TK413편은 두 시간 비행임에도 불구하고 아침 기내식을 줍니다! 졸지에 아침 기내식을 두 개 먹어버린 돼지가 되었습니다. 꿀꿀. 근데 맛있었어요. 터키항공은 정말 최고의 항공사가 아닐까….

Привет, Россия!

긴 여정 끝에 드디어 러시아의 브누코보^{Внуково} 국제공항에 도착했습니다. 셰레메티예보^{Шереметьево}가 인천공항이라면 브누코보는 김포공항쯤의 포지션인 것 같습니다. 튀르키예는 가까운 나라니까요.

입국심사장으로 이동합니다. 러시아는 제1세계 국가들에게는 아직도 까다로운 입국 정책을 유지하고 있습니다. 하지만 적어도 러시아가 우크라이나와 전쟁하기 전까지는 한국의 이미지는 굉장히 좋기 때문에 입국심사는 큰 걱정 없이 통과할 거라고 믿었습니다.

그리고 실제로 두 명은 별 문제 없이 통과했습니다. 영어를 잘 모르는 눈치였는데, 영어로 몇 가지 물어보는 시도를 하더니 그냥 들여보내줬습니다.

하지만 두 명이 통과하고 나니까 입국심사대의 문이 전부 닫히고 다른 두 팀원이 입국심사대 저편에 갇혀 버렸습니다 …?

영문도 모른 채 30분동안 입국심사대를 경계로 두고 불안에 떨고 있었습니다.

나중에 물어보니 함께 입국한 다른 한국인의 일행으로 오해받아서 여권을 압수당하고 이것저것 물어봤다고 합니다. 우리나라도 아니고 남의 나라에서 이런 일을 겪다니 국제 이산가족 비슷한 게 될까 봐 정말 무서웠어요.

무서움은 코카-콜라 바닐라로 녹이기로 합니다.

처음 뵙겠습니다, 모스크바

모든 입국 과정을 무사히 마치고 공항 로비로 나왔더니 ICPC 자원봉사자 분들께서 우리를 기다리고 계셨습니다!

브누코보는 모스크바와는 조금 거리가 있는 곳이라 모스크바 중심에 있는 숙소로 가려면 꽤 이동해야 합니다. 다행히도 ICPC에서 택시를 지원해 줘서 편하게 이동할 수 있었습니다.

러시아판 카카오+네이버라고 할 수 있는 얀덱스^Яндекс 택시를 두 대 불러 이동했습니다. 얀덱스는 검색엔진 회사인데 번역도 하고 택시도 하고 배달도 하고, 게임 플랫폼도 있고, 러시아 국내에서 구글보다 점유율이 높은 것까지 판박이입니다. 하나 다른 건 우리나라의 모든 곳에서 카카오 라이언 캐릭터를 볼 수 있는데 얀덱스는 캐릭터는 없는 거 같다 정도네요.

고속도로를 타고 크라운 플라자 호텔로 가는 길에서 차들을 많이 볼 수 있었는데 그 중에는 한국 중고차도 간간히 보였습니다. ‘최대적재량 4500kg’라는 한글이 적힌 현대 트럭이 인상깊었어요.

모스크바는 이렇게 세 개의 큰 순환도로로 이뤄져 있습니다. 중앙에 있는 순환도로 안에 크렘린과 붉은 광장이 있고, 이 근처에서 ICPC 월드 파이널이 개최됩니다. 우리나라로 치면 브누코보 공항은 김포공항쯤 되고, 대회 장소는 광화문 근처라고 할 수도 있을 것 같습니다. 물론 이제 모스크바 면적은 서울의 4배에 달하기 때문에 광화문 근처에서 이런 대회를 열 수 있는 공간이 있는가 하면 그건 또 모르겠다는 생각이 들지만 여하튼 그렇습니다.

호텔은 대회 장소에서 그렇게 멀지 않은 곳이었습니다. 역시 ICPC 8연속 우승을 차지하고 있는 러시아의 심장 모스크바에서 열리는 ICPC여서 그런지 만반의 준비를 한 것 같다고 느꼈습니다.

모스크바 강변을 따라 지어진 러시아 건축 양식의 건물들이 보이는 멋진 뷰가 있는 객실이었습니다. 그림같이 아름다워서 눈을 뗄 수가 없었어요.

모스크바 산책

첫째 날에는 다들 시차적응도 해야 했고 십 몇 시간동안 비행기 타고 고생하느라 많이는 못 돌아다녔습니다. 다만 멀리까지 와서 호텔에만 있기는 아까우니까 산책을 나가기로 합니다.

개인적으로 공공디자인에 관심이 많아서 눈여겨봤는데 모스크바의 그것은 꽤 마음에 들었습니다. Moscow Sans를 사용하고 있는데 이런 디자인 언어가 대중교통과 거리 안내판 등 많은 곳에 적용되어 있었습니다.

그리고 사람들이 마스크를 안 쓰고 다닙니다. 실내에서도요! 당시는 2021년 9월이었고 우리나라는 음식점에서 식사를 오후 9시까지밖에 할 수 없었던 시국이었던지라 적잖은 문화충격을 받았죠.

숙소 근처 스몰렌스카야^{Смоленская} 역까지 걸어가서 지하철을 타 보려고 역에 들어가서 노선도를 구경하고 있으니, 역무원 분께서 다가오셔서 미숙한 영어로 노선도에 그려진 붉은 별을 가리키면서 ‘여기 가면 멋진 거리도 있고 레닌 동상도 있다’ 같은 추천을 해주셨지만 여기까지 걸어온 것만 해도 힘에 부쳐서 내일 가 보기로 합니다.

스몰렌스카야 근처에는 아르바트^Арбат 거리가 있습니다. 아르바트는 거리의 화가들이 많기로 유명합니다. 그래서 그런지 돌아오는 길에 캔버스에 유화 그림을 그리는 화가 분을 뵐 수 있었어요. 거리에서 그림을 그리는 광경은 우리나라에서는 잘 볼 수 없었던 광경이라서 유럽에 왔다는 실감이 나게 해 주는 무언가였네요.

모스크바 음식

저희와 비슷하게 온 경북대학교 Catdriip 팀과 연락이 닿아서 근처 식당에서 저녁을 먹기로 합니다. 찾아간 곳은 서강대학교 프로그래밍 대회 문제 Ресторан의 소재가 되기도 했던, 레스토랑 마트료시카^{Ресторан «Матрешка»}입니다.

모스크바 강을 따라 걸어가면서 모스크바 야경을 볼 수 있었는데 밤의 모스크바도 엄청 예뻤습니다. 첫 번째 사진 왼쪽의 으리으리한 건물은 호텔이라고 하네요. 레스토랑 앞에는 마트료시카 조각상이 있었어요.

음식점에 들어오니 카운터에서 외투를 보관해 주시고 신발장처럼 번호표를 나눠주셨습니다. 이것도 신기한 부분이었는데, 며칠 살아보면서 느꼈던 부분이라면 러시아 사람들은 외투를 입고 대신 안에 따뜻한 옷을 입지는 않는 것 같았습니다. 실내 온도가 높은 대신 외투 보관소가 대부분의 시설에 있었던 느낌이었어요. 어쩐지 외투 입고 따뜻하게 입으니까 많이 덥더라구요.

dogdriip님과는 개인적으로 친분이 있어서 자주 뵈었지만 exqt 님과 skeep194 님은 초면이었습니다. 이쪽도 여러 사정으로 인해 2019년 서울 리저널 팀 구성과는 약간 다른 구성으로 출전했습니다.

메뉴판에 약간 의외의 음식이 보이는데, 러시아에는 의외로 전통 만두^{Пельмени}가 있고 꽤 대중적이라고 합니다. 유럽과 아시아의 영향을 모두 받은 결과일까요?

저는 닭고기 포자르스키 코틀레타^{Пожарские котлета}을 주문했습니다. 이름은 뭔가 치킨까스일 거 같고, 생긴 것도 실제로 도깨비방망이 같은 걸 끼얹은 치킨까스처럼 보이기는 하지만 되게 부드러운 다진 닭고기 튀김입니다.

맛은 예상할 수 있는 맛보다 맛있고, 약간 느끼했고.. 식감은 고로케 같은 느낌이었어요. 고로케도 좋아하고 닭고기도 좋아해서 개인적으로는 꽤 마음에 들었어요! 아마 서울에서 러시아 식당을 갈 일이 생긴다면 메뉴판에서 찾아보게 될 것 같네요.

물이 부족해서 더 달라고 요청했는데 이게 나중에 영수증에 떡하니 적혀 있었다는 점은 조금 당황스러웠네요. 심지어 에비앙… 무려 2,070루블, 당시 가격으로 33,120원이 7인 식사의 물 값으로만 나갔다는 건데… 이럴 때는 한국이 역시 최고인 것 같고 그렇죠.

러시아는 음식점 9시 영업제한 같은 게 따로 없었어서 늦게까지 맛있게 먹고 야경을 감상하며 천천히 숙소로 돌아왔습니다.

모스크바에서의 하루

아직 ICPC 공식 일정 시작까지는 하루 더 남은 관계로 다음 포스트도 아마 관광 이야기가 될 것 같네요. 1년만에 다시 쓰려니까 기억이 조금씩 사라져가는데 빨리 쓸 걸 하는 후회가 남습니다… 빨리 ICPC 얘기 하고 싶은데 어떻게 대회가 6일치 일정이나 되는지 모르겠네요. 여유가 되는 대로 더 써 보겠습니다!

시리즈: ICPC World Finals Moscow

1. 모스크바 ICPC 월드 파이널에 다녀왔습니다 (1)

2. 모스크바 ICPC 월드 파이널에 다녀왔습니다 (2)

사용해 보기: BOJ 디스크립션 툴 / 소스: GitHub

한국에서는 프로그래밍 대회가 많이 열립니다! 정말 고무적인 일입니다.

의외로 전국 대학생 프로그래밍 경시대회^ICPC 리저널이 매년 열리는 나라는 많지 않습니다. 서강대학교에서는 2005년부터 매년 대회를 열어 작년에는 무려 17번째 교내 프로그래밍 대회가 열렸고, 전국 대학생 프로그래밍 대회 동아리 연합에서는 올해로 11번째 대회를 개최했습니다. 넥슨과 삼성전자 — 대한민국 최고의 게임 기업과 대한민국 최대의 정보기술 기업 — 도 꾸준히 관심을 갖고 대회를 열고 있습니다(각각 7회, 8회째). 최근에는 현대모비스 및 여러 스타트업들도 자체 대회를 개최하고 있습니다.

이렇게 프로그래밍 대회에 대한 국가적 관심이 커지고 있는 상황에서 학교/동아리 및 커뮤니티 대회 개최에 대한 수요가 커지는 것은 어떻게 보면 당연한 일인데요, 백준 온라인 저지가 학교/동아리 대회에 대해 무료로 채점 환경을 제공하고 있다는 건 참 다행인 점입니다.

디스크립션 작업에서 발생하는 문제들

하지만 이런 좋은 플랫폼이 있음에도 불구하고 온사이트 대회에서는 문제지를 만들어야 한다는 점 때문에 디스크립션을 작성하는 과정에서 마주하는 근본적 문제들이 존재합니다.

• 출제자: (BOJ에서만 지문을 수정하고) 디스크립션 수정했어요!

• 검수자 A: (출력할 문제지를 보면서) 🤔 어디가 수정됐다는 거지…

• 검수자 B: (BOJ 지문과 출력할 문제지가 다른 상황을 보면서) 😵 어느 쪽이 의도된 지문일까?

이런 상황이 생길 수 있기 때문에 세팅 경험이 많은 사람이 있다면 BOJ와 문제지 중 한 쪽을 유일한 원천^{single source of truth}으로 두고 작업하도록 하는 경우를 볼 수 있습니다. 가령 지문 작업은 BOJ에서만 하고 마지막 날에 모든 문제를 문제지에 옮긴다던가, 아니면 반대로 하는 식입니다.

그래도 여전히 몇 가지 문제가 있습니다. 가령 문제지를 Google Docs나 Word 등에서 작업하고 BOJ Stack에 붙여넣으면 포매팅이 영 이상해집니다.

• BOJ에 문제를 올리려면 HTML이 꽤 깨끗해야 합니다. 개인적으로 좋은 제약조건이라고 생각합니다. 근데 워드 프로세서는 일반적으로 그렇지 않죠. 이 제약 때문에 워드 프로세서에서 바로 붙여넣기할 수 없습니다.

• 그렇다고 메모장에 붙여넣은 후 거기서 다시 가져오자니 열심히 만들어 둔 예쁜 리스트와 수식들이 전부 깨집니다. 공들여 만든 수식 $X=\frac{p_1l_1+p_2l_2+\cdots +p_Nl_N}{p_1+p_2+\cdots +p_N} =\frac{\sum_{i=1}^{N}p_il_i}{\sum_{i=1}^{N}p_i}$를 붙여넣었더니 X=p1l1+p2l2++pNlNp1+p2++pN=i=1Npilii=1Npi가 되어 있는 건 그다지 유쾌한 경험은 아니겠죠.

반대로 가자니… BOJ 수식 렌더 방식은 LaTeX인데, 이걸 그대로 지원하는 워드 프로세서는 잘 없는 것 같고, 그렇다고 Markdown 기반으로 작업하자니 글자에 색상을 못 넣는다거나 그림 포매팅을 자유롭게 하지 못하는 등의 제약이 많습니다.¹

워드 프로세서를 사용하지 않는다면 어떨까요? 프로그래밍 문제의 디스크립션에는 수식이 정말 많이 등장하기 때문에 ICPC를 비롯한 여러 대회에서 여러 세터들이 LaTeX로 세팅하는 편입니다. 요즘에는 문제 제작에 있어서 필수불가결한 플랫폼인 Codeforces의 Polygon 플랫폼도 디스크립션을 LaTeX로 입력하도록 하고 있으며, UCPC도 LaTeX로 문제지를 세팅하고 있습니다.

BOJ의 수식 렌더 방식이 LaTeX라니 뭔가 순조롭게 옮길 수 있을 것 같습니다. 하지만 LaTeX에도 문제가 많습니다. 가령…

• 수식뿐 아니라 본문에서도 여러 명령어를 사용할 수 있습니다. 예를 들어 \alpha 명령어는 그리스 문자 α를 입력합니다.

• 리스트도 명령어를 쳐서 만듭니다. \begin{enumerate} ... \end{enumerate} 등입니다.

• 기타 LaTeX만의 이상한 점들이 있습니다. 예를 들어 '는 무조건 오른쪽 닫는 작은따옴표입니다. ``는 왼쪽 여는 큰따옴표를 렌더합니다.

결국 지금까지는 어떻게 하든 문제마다 디스크립션을 한 땀 한 땀 옮겨 줘야 하는 경우가 대부분이었습니다. 제 경우에는 이런 작업을 2019/2020/2021년 서강대학교 프로그래밍 대회, 2020/2021 겨울/2021 여름 신촌 연합, UCPC 2020의 일곱 번의 대회에서 모든 문제에 대해 해 왔고 올해도 숨은 왼쪽 여는 따옴표 찾기를 하고 싶지는 않았습니다.

그래서 만들었습니다: 디스크립션 툴

그래서 LaTeX, 특히 Polygon 플랫폼과 많은 대회들이 사용하는 olymp.sty 형식 디스크립션들을 복사-붙여넣기할 수 있는 HTML로 바꿔 주는 툴을 만들었습니다. latex-utensils를 이용해 LaTeX를 파싱해 AST로 만들고, AST를 탐색하면서 다시 HTML로 빌드해 주는 툴입니다. 생성되는 HTML은 BOJ Stack 가이드라인을 최대한 따르려고 노력합니다.

원하는 경우 MathJax를 사용하지 않고 sup, sub, em 등을 이용해 수식을 렌더하도록 할 수 있습니다. 이 모드에서 렌더한 모든 수식도 BOJ 가이드라인을 최대한 따르려고 노력합니다. 예를 들어,

• LaTeX에서는 연산자와 문자 사이에 띄어쓰기가 없더라도 변환된 HTML에는 자동으로 띄어쓰기가 들어갑니다.

• 수식 안에 있는 모든 문자는 HTML로 변환할 때 이탤릭이 됩니다.

• \times는 ×가 됩니다. - (빼기 기호)는 −가 됩니다.

라이트 버전 MathJax라고 생각하시면 됩니다. 아직 안 되는 것들도 있습니다. 명령어 재정의와 tabular 환경, 그리고 이미지 지원이 대표적인 예인데, 이미지 지원을 제외하고는 아마 다른 대회에서 출제/검수를 맡게 될 때 만들지 않을까 싶습니다.

바뀐 워크플로우

이제 Polygon 패키지 혹은 문제지를 만들고, 변환기의 도움을 받아 HTML로 변환한 뒤 BOJ Stack에 복사/붙여넣기만 하면 됩니다.

디스크립션 작업을 버전 관리가 되는 Polygon 혹은 실시간 편집이 되는 Overleaf의 둘 중의 하나로 일원화할 수 있어서 플랫폼 간의 컨플릭트가 사라지고, LaTeX에서 HTML 또는 HTML에서 LaTeX로 변환하는 과정을 더 이상 손으로 하지 않아도 되기 때문에 실수할 여지도 줄어들고 시간도 아낄 수 있습니다. 디스크립션 변환할 시간에 틀린 풀이 하나 더 짜고 데이터 하나 더 만들어 넣을 수 있게 되었습니다.

이미 UCPC 2022의 모든 문제를 이 툴을 사용해 변환했습니다. 모든 변환은 클라이언트에서 이루어지니 문제 유출 염려 없이 안심하시고 사용하셔도 괜찮습니다.

ckeditor 대응

Stack은 ckeditor를 쓰고 있는데, 포매팅이 있는 외부 HTML을 복사-붙여넣기하면 시맨틱한 요소를 빼고 모든 포매팅을 지워 버립니다. 아래 스크립트를 실행해 붙여넣기 필터를 전부 없애 줘야 합니다.

var o=CKEDITOR.filter.instances;Object.keys(o).forEach((k)=>o[k].disable())

여담

툴이 완벽하지 않은 부분들이 있으니 버그를 발견하신 경우 GitHub에 이슈 혹은 PR을 남겨 주시면 감사하겠습니다.

각주

1. 디스크립션에서 글자에 색상을 넣지 못하는 건 의외로 중요한 이슈입니다! 특히 입력부에서 제시하는 어떤 문자열을 그대로 출력하라고 할 때 모노스페이스 폰트와 함께 글자 색상을 바꾸면 가독성이 굉장히 향상됩니다. ↑

언어는 도구에 불과하다고들 합니다. 그리고 모든 도구는 용도와 장단점이 있습니다. 알고리즘 문제해결 필드에서 언어라는 도구를 어떻게 사용하면 좋을까요?

프로그래밍 대회에서의 문제해결에 대해 많은 이야기를 할 예정이지만 이제는 코딩 테스트도 알고리즘 문제해결에서 상당한 비중을 차지하고 있기 때문에 먼저 코딩 테스트에 대해 간단하게만 이야기해보겠습니다.

코딩 테스트

코딩 테스트는 기업이 많은 지원자를 세심하게 리뷰하기 힘들기 때문에 두는 스크리닝^screening 과정 중 하나로, 코딩 테스트 문제의 출제 목적은 수험자의 구현력과 논리적 사고력이 일정 수준 이상인지 평가하는 데에 있습니다.

일반적으로 같은 알고리즘을 짠다면 C++로 짜는 게 시간/공간 사용량 면에서 가장 효율적이라고 합니다. 하지만 현업에서 모두가 C++을 사용하지는 않죠? 가령 Typescript로 백엔드 개발을 하는 조직이 있는데 C++로 지원자를 평가한다고 생각해 봅시다. 지원자는 C++에 대한 이해가 부족해 Javascript에서 하던 것처럼 vector<int> 값을 &나 *도 안 붙이고 함수 인자로 넘겨버립니다.¹ 이 얼마나 끔찍한 일인가요? 지원자는 제 실력을 못 내고, 회사는 지원자를 제대로 평가할 수 없게 됩니다.

그래서 일반적으로 코딩 테스트 문제들의 시간 제한과 메모리 제한은 언어마다 다르도록 설정하거나 언어에 따라 배수를 두는 편입니다. 그래서 저는 코딩 테스트를 준비하시는 분들께는 자신이 가장 자신있는 언어 혹은 입문하기 쉬운 언어로 시작하시기를 추천드립니다.

프로그래밍 대회

반면에 프로그래밍 대회들은 C++을 사랑하기로 유명합니다.

• 가장 권위있는 대학생 프로그래밍 대회인 국제 대학생 프로그래밍 대회^ICPC 월드 파이널의 경우 C/C++, Java, Kotlin, Python 채점을 지원하나 Python으로 모든 문제가 풀리는 것을 보장하지 않습니다.

• 국제정보올림피아드^IOI의 경우에는 C++ 제출만을 허용하며, 한국정보올림피아드^KOI의 경우 C/C++, PyPy, Java 채점을 지원하나 C++ 이외의 언어로 해결할 수 있음을 보장하지 않습니다.

왜 그럴까요?

세팅하는 입장에서

문제를 만드는 입장에서 여러 언어의 존재는 참 머리아픈 일입니다. $\mathcal{O}\left(n^2\right)$ 솔루션은 돌게 하고 싶지만 $\mathcal{O}\left(n^2 \log n\right)$은 돌지 않게 하고 싶은 경우에서 C++만 놓고 생길 수 있는 일들에 대해 알아봅시다.

• $\mathcal{O}\left(n^2\right)$ 솔루션 — 1.4초

• $\mathcal{O}\left(n^2\right)$ 솔루션 + mmap fast I/O + Ofast — 1.0초

• $\mathcal{O}\left(n^2 \log n\right)$ 솔루션 — 2.4초

• $\mathcal{O}\left(n^2 \log n\right)$ 솔루션 + mmap fast I/O + Ofast — 2.0초

보통 시간 제한은 틀린 솔루션의 0.5배 시간 미만, 모델 솔루션의 2배 시간 초과 정도로 잡습니다. 그래서 이런 상황이 오면 약간 애매해지게 됩니다. 이제 세터는 어느 장단에 맞출지 생각해 봐야 합니다. 여러 가지 선택지가 있습니다.

• 문제 상황과 $n$을 요리조리 바꿔 보면서 모델 솔루션과 틀린 솔루션 사이의 격차 늘리기

• 상수 최적화를 문제 컨셉으로 잡고 시간 제한을 1.5초로 걸기

• 그냥 fast I/O + Ofast까지 쓰면서 문제를 해결하려고 한 노력을 인정해 주기 위해 시간 제한을 2.0초로 걸기

• 이미 기획된 난이도 커브를 벗어나더라도 아예 $\mathcal{O}\left(n^2 \log n\right)$를 정해로 두고 시간 제한을 4.0초로 걸기

여기에 이제 Python이 추가된다고 해 봅시다. 발생할 수 있는 일들은 이렇습니다.

• C++ 기준으로 시간 제한을 1.5초로 줬는데 Python $\mathcal{O}\left(n^2\right)$ 코드가 2.0초에 도는 경우

• C++ 기준으로 시간 제한을 1.5초로 주고 대회 플랫폼의 추가 시간 규정에 따라 추가 시간을 6.5초로 줬는데, Python의 $\mathcal{O}\left(n^2 \log n\right)$ 솔루션이 4.0초에 도는 경우

• 온갖 짓을 다 해서 최적화한 Python $\mathcal{O}\left(n^2\right)$ 코드가 2.4초에 도는 경우

• 온갖 짓을 다 해서 최적화한 Python 코드가 결국 메모리를 1GB 이상 사용해서 터지고, 메모리를 최적화하려고 봤더니 이번엔 시간이 터지는 경우

• Python으로 풀면 현저히 쉬워짐

• Python 코드가 set이나 dict를 사용²

결국 언어가 하나 추가될 때마다 모든 언어에 대해 문제 상황과 시간 제한, 그리고 데이터를 다시 고민해야 하는 상황에 빠집니다! 특히 언어별로 추가 시간을 주지 않는 일반적인 ICPC 스타일 대회의 경우 시간 제한 설정의 난이도는 말 그대로 기하급수적으로 증가합니다. 솔루션을 작성하는 데 있어서도 언어별로 조심해야 할 점들이 다른 건 말할 것도 없구요.

이렇게 여러 언어를 대응하는 것은 공수가 많이 드는 일이기 때문에 보통은 C++ 솔루션만 작성하고 다른 언어의 통과를 보장하지 않습니다. 알고리즘 대회에서 코드 간 형평성은 시간 복잡도를 기준으로 결정하는 것이 가장 좋다고 생각하는 입장에서는 언어별 추가 시간을 줬다가 Python에서 비효율적인 시간 복잡도로 작성한 코드가 통과할 수도 있고요.

참가자 입장에서

그래서 프로그래밍 대회 참가자 입장에서는 C++ 스탯만 쌓아도 충분합니다. 프로그래밍 대회들이 C++에서 풀기 까다로운 문제들을 잘 안 내는 것도 있습니다.

하지만 해결가능성이 C++만으로 보장되더라도, 보통은 다른 언어들의 사용을 어느 정도 허용하기 때문에 여러 언어들의 사용 방법을 알아 둬서 나쁠 건 전혀 없습니다. 문제를 읽고 머릿속에서 코드 길이 견적을 내 봤는데 C++ 코드보다 Python 코드 길이가 훨씬 짧다면, Python으로 코드를 짜고 해결 시각에서 상당한 우위를 점할 수 있습니다.

또한 언어별로 특징적인 기능들이 존재하는 경우 이 기능들을 최대한 활용해 문제해결 도움을 받을 수도 있습니다. C++이 아닌 언어에서 문제해결이 현저히 쉬워지는 몇 가지 예를 소개합니다.

문자열 다루기 — Python

문자열 파싱은 Python에서 쉬워지는 경우가 많습니다.

• C++의 std::string은 일반적으로 다른 언어에는 있는 split이 없고, char를 하나하나 처리하기 싫다면 std::istringstream 등을 이용해야 합니다.

• C++의 경우 비 ASCII 문자의 처리가 어렵습니다. 비 ASCII 문자들은 나오면 안 된다고 생각하는 것과 별개로….

• C++의 정규식은 활용하기가 귀찮게 되어 있습니다.

• Python의 f-string이 너무 강력합니다.

C++로 문자열에서 숫자들을 찾는 정규식을 구현하면 이렇게 됩니다.

regex re("\\d");
string str;

auto begin = sregex_iterator(str.begin(), str.end(), re);
auto end = sregex_iterator();
for (auto iter = begin; iter != end; iter++) {
    smatch match = *iter;
    cout << match.str() << " ";
}
cout << endl;

Python으로는 비슷한 작업을 아래와 같이 할 수 있습니다.

import re

p = re.compile('\\d')
result = p.findall(str)
print(result)

크고 정확한 수 다루기 — Python, Java, Kotlin

C++에서 가장 큰 부호 있는 정수 자료형은 $2^{63}-1 \approx 9.2 \times 10^{18}$까지를 표현할 수 있습니다.³ 많은 문제들의 $N$ 제한이 $10^{18}$을 잘 초과하지 않는 이유이기도 합니다.

하지만 이 범위를 넘어가는 수의 사칙연산이 필요하다면 직접 구현체를 만들어야 합니다. 특히 큰 수의 곱셈과 나눗셈의 경우 단순히 $\mathcal{O}\left(1\right)$로 생각할 수 있는 문제가 아닙니다. $n$자리 곱셈을 초등학교에서 하듯이 구현하면 $\mathcal{O}\left(n^2\right)$의 시간이 걸리며, 더 효율적인 곱셈 방법이 필요하다면 $\mathcal{O}\left(n^{\log_2 3}\right)$의 Karatsuba 알고리즘 혹은 $\mathcal{O}\left(n \log n\right)$의 FFT를 짤 수 있어야 합니다.

Java와 Kotlin의 경우 $9.2 \times 10^{18}$을 초과할 수 있는 BigInteger를 지원합니다. Python은 아예 정수형 자체에 범위가 없고, 다룰 수 있는 수의 이론적 상/하한이 없습니다. 곱셈은 OpenJDK의 경우 자릿수에 따라 나이브, Karastuba 혹은 Toom–Cook 알고리즘을 사용하며, CPython의 경우에도 자릿수가 작으면 나이브, 크면 Karatsuba 알고리즘을 사용합니다.

정수 곱셈 문제들을 FFT로 풀 수 있듯이 이 사실에 기반해 FFT 문제를 Python 정수로 풀 수도 있기는 합니다. 아래는 이동 (BOJ #1607)를 실제로 Python으로 해결한 코드입니다. Karatsuba는 FFT보다 느린 경우가 많기 때문에 굳이 추천하지는 않고 대충 이런 방법도 있다는 걸 보여드리기 위해 남깁니다.

정확한 유리수 표현^{arbitrary precision}이 필요한 경우 Python decimal과 Java BigDecimal을 사용할 수 있습니다. 추가로 Python은 어떤 유리수도 표현 및 계산할 수 있는 Fraction 모듈을 제공합니다.

특히 Google Code Jam에서는 제한이 $10^{18}$을 초과하는 큰 수를 다루는 문제들이 종종 등장하므로 알아 두면 좋습니다.

• Cutting Cake — World Finals 2021 A번 (BOJ #22917)

• Append Sort — Round 1A 2021 A번 (BOJ #22890)

• Roaring Years — Round 1C 2021 C번 (BOJ #22897)

• Fair and Square — Qualification 2013 C3번 (BOJ #12341): 예전 문제지만 좋은 문제라고 생각해서 살짝 추천해 봅니다.

모듈로 곱셈 역원 — Python

C++에서 mod $p$의 나눗셈을 하려면 보통 Fermat의 소정리($n \times n^{p-2} \bmod p = 1$)를 바탕으로 분할 정복을 이용한 거듭제곱을 구현합니다.

놀랍게도 Python의 내장 pow 함수는 서로소인 $n$과 $m$에 대해 $n \bmod m$를 빠르게 구할 수 있습니다. 심지어 $m$이 소수가 아니어도 됩니다. C++에서는 $m$이 소수가 아닌 경우에는 Euler’s totient function 혹은 확장 Euclidean 알고리즘 구현에 대해 알고 있어야 합니다.

잉여역수 구하기 (#15995)는 Python으로 무려 두 줄만에 해결할 수 있습니다.

다각형의 bool 연산 다루기 – Java, Kotlin

다각형의 bool 연산(and, or, xor 등)은 C++로 직접 구현할 경우 상당히 다루기 힘든 주제입니다. Java의 java.awt.geom은 이런 작업들을 처리해 주는 구현체입니다. 단순다각형뿐만 아니라 원, 타원, 2-3차 베지어 곡선 등으로 이루어진 도형의 불 연산을 처리할 수 있고, 구한 도형의 꼭짓점 정보 등을 쉽게 구할 수 있습니다.

java.awt.geom 패키지를 활용해 문제를 해결하면 난이도가 꽤 낮아지는 문제들의 예시로는 이런 것들이 있습니다.

• 다각형의 확장 (#2664) — KOI 1997 고등부 1번

• Abstract Art (#15805) — ECNA 2017 A번

• Drawing Character (#15632) — 제1회 구데기컵 🦁번

다만 충분히 효율적이지는 않기 때문에 모든 다각형의 불 연산 문제에서 사용할 수 있는 것은 아닙니다. 예를 들어 Lonely mdic (BOJ #10900)이나 직사각형의 합집합(BOJ #2185) 같은 문제는 geom만으로 해결하기는 어렵습니다. 메모리를 많이 사용한다는 Java 언어 자체의 한계도 존재합니다.

정리하면

누군가 알고리즘 문제해결을 코딩 테스트가 아닌 대회 준비로 시작한다면 저는 주저 없이 C++을 추천할 것입니다. 적어도 2020년대에는 C++만 배워도 대회에 등장하는 모든 문제를 해결할 수 있을 겁니다.

하지만 C++이 모든 경우에서 제일 좋은 툴은 아닙니다. 도구상자에 여러 도구들이 있다면 특정 상황에서 조금 더 편한 도구들을 꺼내 쓰는 것이 좋을 수 있습니다. 도구의 장단점을 정확히 알고 적재적소에 가져다 쓰는 것도 경쟁 프로그래머의 역량이라고 생각합니다.

각주

1. C++에서는 모든 함수 인자가 기본적으로 값을 복사해 전달되며 vector<int>와 같은 동적 배열 타입도 그렇습니다. 반면 Javascript 등의 언어는 기본 자료형이 아닌 모든 함수 인자는 레퍼런스를 복사해 전달됩니다. ↑

2. Python의 set과 dict는 룩업에 $\mathcal{O}\left(n\right)$가 되도록 하는 데이터를 제작하기 쉽습니다. 이는 사실 C++의 std::unordered_map도 마찬가지입니다. 일반적으로 라이브러리 내부 자료 구조의 동작을 묻는 것은 문제의 포커스에서 벗어나 있기는 하지만, 대회 컨셉과 형식에 따라(예를 들어 참가자가 다른 참가자의 제출을 저격할 수 있는 TopCoder 혹은 Codeforces 등) 고려할 여지가 있습니다. ↑

3. G++이라면 __int128을 써서 $2^{127}-1 \approx 1.7 \times 10^{38}$까지는 어찌어찌 타협을 볼 수도 있겠습니다. ↑