알고리즘 문제해결의 관점에서 프로그래밍 언어라는 것은

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

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

코딩 테스트

© 프로그래머스

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

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

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

프로그래밍 대회

반면에 프로그래밍 대회들은 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를 사용2

결국 언어가 하나 추가될 때마다 모든 언어에 대해 문제 상황과 시간 제한, 그리고 데이터를 다시 고민해야 하는 상황에 빠집니다! 특히 언어별로 추가 시간을 주지 않는 일반적인 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}$까지를 표현할 수 있습니다.3 많은 문제들의 $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}$을 초과하는 큰 수를 다루는 문제들이 종종 등장하므로 알아 두면 좋습니다.

모듈로 곱셈 역원 — 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 패키지를 활용해 문제를 해결하면 난이도가 꽤 낮아지는 문제들의 예시로는 이런 것들이 있습니다.

다만 충분히 효율적이지는 않기 때문에 모든 다각형의 불 연산 문제에서 사용할 수 있는 것은 아닙니다. 예를 들어 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}$까지는 어찌어찌 타협을 볼 수도 있겠습니다. ↑

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.