PS 용어 정리

2019. 5. 25. 00:35알고리즘 문제풀기/기타 주제

PS(Problem Solving), CP(Competitive Programming), 알고리즘 문제 해결, 정보 문제풀이, 올림피아드 문제 풀이, …

이 분야를 지칭하는 표현이 여럿 있습니다. 보통

  • 문제가 주어진다. 이때 이 문제의 일부(실제로 계산해야 하는 수열, 그래프, 그림 등)는 아직 주어지지 않았다.
  • 그 문제를 해결하는 알고리즘을 생각해야 한다.
  • 알고리즘의 모든 과정을 실제로 구현한다. 위에서 말한 '문제의 일부'를 입력받아 문제를 푸는 프로그램을 만든다.
  • 프로그램의 소스 코드를 제출한다.
  • 몇 개의 데이터를 통해 채점하여 옳은가를 확인한다.

위의 과정을 가리킵니다. 알고리즘 기반의 사고 능력 필요로 하기 때문에 '알고리즘'이라는 단어로 지칭하기도 합니다. 알고리즘 및 컴퓨터 프로그래밍 능력은 컴퓨터과학 및 컴퓨터공학에 속하고 이 이름이 정보과학이라는 이름과 교차해 쓰이기도 해, '정보과학'과 관련지어 지칭하는 경우도 있습니다. 한국정보올림피아드 혹은 국제정보올림피아드에서 출제하는 문제 역시 온전히 이 쪽이기 때문에 '정보 올림피아드 문제'로 대강 지칭할 수도 있습니다.

그런데 이 분야의 모든 문제가 이렇지는 않습니다. 이를테면...

  • 문제의 일부가 모두 주어져 있는 경우. output-only라고 불리는 문제 종류가 그렇습니다.
  • 소스 코드를 제출하지 않는 경우. 2015년 즈음의 구글 코드 잼 대회가 그랬습니다. 작성한 프로그램을 실행한 결과를 제출했습니다.
  • 프로그램 전체를 작성하지 않는 경우. grader 방식으로 불리는 문제 종류가 그렇습니다.

하지만 이런 문제들이 요구하는 생각은 비슷하기 때문에 대체로 한 가지로 묶어 부르고는 합니다.

PS와 CP 간의 차이는 이렇습니다.

  • PS (problem solving, 문제 풀이): 그 과정이야 어떻게 되었든 문제를 푼다는 점에 주목한 표현입니다. 때문에 꼭 컴퓨터로, 프로그래밍 언어를 사용한다는 법도 없지요.
    수학에서도 같은 용어를 사용합니다. 수학 올림피아드 등의 대회에 출제되는 문제도 설명하기는 어려우나 일정한 스타일을 가지고 있거든요. 이쪽 문제를 모아놓고 토론하는 유명한 포럼 사이트 Art of Problem Solving도 있습니다. 수학 PS가 프로그래밍 PS와 비슷한 점도 많습니다.
  • CP (competitive programming, 경쟁 프로그래밍): 이 분야의 문제 풀이가 많이들 대회 단위로 진행되고, 제한 시간 내에 더 일찍, 더 많이 푼 사람이 더 높은 등수를 가지게 되기 때문에 붙은 이름입니다. 반대로 시간 제한 없이 느긋하게 생각하며 문제를 푸는 경우에는 어울리지 않는 표현이라고 할 수도 있습니다.

일본에서는 표현이 거의 통일된 것 같습니다. 競技プログラミング(경기 프로그래밍), 혹은 줄여서 競プロ(きょうプロ라고 읽습니다)라는 단어인데, CP와 거의 같은 맥락으로 보입니다. 중국에서는 심플하게 프로그래밍 대회(程序设计竞赛)라는 표현을 많이 쓰는 것 같고, 경쟁 프로그래밍(竞争编程)도 간간이 쓰이는 듯합니다.

저는 어느 용어든 좋지만 통일을 해야 한다는 입장이고, 블로그에서는 PS를 많이 사용하고자 합니다.

 

업솔빙 (upsolving)

대회가 끝난 후에 문제를 푸는 걸 말합니다. 풀이를 알게 된 후 그걸 코딩하는 경우에도 쓸 수 있고, 아니어도 쓸 수 있습니다.

 

문제 세트 (problem set)

문제 모음입니다. 보통 시간 잡고 대회를 치룰 수 있는 수준의 문제 모음을 말합니다. 혹은 특정 대회의 문제를 묶어서 말하기도 합니다. APIO 2017 세트라고 하면 rainbow, merchant, koala 이렇게 세 문제를 말하겠지요.

한 문제 세트를 쭉 돌며 푸는 일을 '세트를 돌다' 혹은 '세트를 돌리다'라고 말합니다.

 

데이터 세트(data set), 테스트 세트(test set), 테스트 케이스(test case)

채점하는 데 사용하는 파일을 의미합니다. 테스트 케이스 하나하나는 각각 한 번씩 채점을 할 수 있는 가장 작은 단위이고, 그런 케이스가 모두 묶인 것이 데이터 세트 혹은 테스트 세트입니다.

 

정보 올림피아드(Olympiad in Informatics, OI)

글을 분리했습니다. (링크)

 

어셉, AC, Accepted, 맞았습니다!!, 틀렸습니다, WA, TLE, MLE, …

각각의 테스트 케이스에 대한 판정이 여러 가지가 있고, 사이트나 시스템마다 표현이 다릅니다. 이런 판정을 verdict라고 합니다.

  • Accepted=AC=맞았습니다!!=억셉=어셉

백 점짜리 풀이입니다. ACCEPTED 혹은 AC로 표시되며, 한국어로는 '맞았습니다'라는 표기가 일반적입니다. (BOJ 말고는 쓰는 사이트를 못 봤습니다.) 보통 진한 초록색으로 표시됩니다. 보면 기분이 좋아지는 마법의 단어와 색깔입니다.

  • Wrong Answer (WA)=틀렸습니다

프로그램이 시간 내에 작동했고 무언가 답을 출력했는데, 정답과 다르거나 정답의 조건을 만족하지 않는 경우입니다. 말 그대로 틀렸습니다. 보통 빨간색으로 표시됩니다. 이 아이를 만날 땐 항상 초록색을 기대하고 있는 타이밍이기 때문에 누구나 상심이 큽니다. 단어만 봐도 마음의 상처가 생기는 것 같네요. 하지만 틀린 걸요. 어쩔 수 없죠.

  • Time Limit Exceeded (TLE): 시간 제한 초과입니다.
  • Memory Limit Exceeded (MLE): 메모리 제한 초과입니다.
  • Runtime Error (RE): 프로그램이 접근 불가능한 주소에 접근하거나, 해서는 안 되는 동작을 시도하거나, return code가 0이 아닌 경우에 주로 발생합니다.
  • Compilation Error (CE): 컴파일에 실패한 경우입니다.

WA_TLE라는 닉네임을 사용하는 일본 분이 있습니다.

 

올솔 (올 솔브 all solve)

말 그대로 대회에 나온 문제를 전부 다 풀기입니다.

저는 오프라인 대회에서는 올 솔브를 해 본적이 없는데, 성공한다면 남은 시간동안 뭘 할지 잘 모르겠습니다. 테트리스나 해야 할까요? 사실 매번 오프라인 대회를 칠 때마다 "이번엔 00분만에 다 풀고 테트리스를 해야겠다"는 사람들이 많은데 다들 테트리스 잘 하고 계신가 모르겠네요.

 

좌셋

되게 이상한 용어입니다. 모든 문제가 풀렸고, 모든 문제를 푼 사람은 없는 대회의 문제 세트를 말합니다. 특징은

  • 아무도 안 푼 문제가 없으므로, 출제진 입장에서 일단 데이터를 준비하는 노력에 보람이 있었습니다. 또 "이걸 이 시간 내에 어떻게 풀어!"라고 할 법한 문제는 없었다는 뜻이구요.
  • 모든 문제를 푼 사람이 없으므로 모든 참가자가 끝날 때까지 문제를 고민해야 했고, 또 만점자가 수두룩해 변별력이 없는 대회가 되지도 않았습니다.

때문에 좋은 대회였다고 할 만합니다. 어원에 대해서 들은 적은 있는데 제가 자세히 모르는 내용이라 넘어가겠습니다.

 

CMS (Contest Management System)

IOI 2012에 사용된 이후로 널리 알려진 대회 관리 시스템입니다. KOI에서도 2013년부터 CMS를 사용했습니다.

GitHub의 cms-dev/cms 리포지터리(링크)에서 오픈 소스로 개발이 이루어집니다. 처음에는 Python 2 기반이었는데 최근 버전에서는 완전히 3으로 migrate한 것 같네요. (Issue #286)

 

온라인 저지 (Online Judge)

문제의 풀이 소스를 제출하면 채점 후 결과를 알려주는 사이트 전반의 통칭입니다. PS 계열 커뮤니티와 웹 사이트(링크) 글에 예시가 있습니다.

 

제곱, 세제곱, 로그, 로그 제곱, 루트, 선형, 서브리니어, …

시간복잡도 혹은 공간복잡도를 가리킬 때 사용하는 표현입니다.
"엔 제곱", "엔 세제곱", "엔 로그 엔", "엔 로그제곱 엔", "엔루트엔" 등 N을 넣어 말하기도 합니다.

문제에서 가장 주요하게 커지는 변수가 N이라고 하면,

  • "제곱"인 알고리즘은 O(N²)
  • "세제곱"인 알고리즘은 O(N³)
  • "로그"인 알고리즘은 O(NlgN) (혹은 여러 번 사용하는 동작에서 각각이 O(lgN))
  • "로그 제곱"인 알고리즘은 O(Nlg²N)
  • "루트"인 알고리즘은 O(N√N)
  • "선형"인 알고리즘은 O(N)
  • "서브리니어"인 알고리즘은 선형보다 적은, 즉 o(N)

의 시간복잡도 혹은 공간복잡도를 가리킬 때 보통 사용합니다. 하지만 꼭 이 규칙을 따르지 않는 경우도 많습니다.

예를 들어, 플로이드 알고리즘은 세제곱, 다익스트라는 로그, merge sort tree는 로그 제곱이라고 말합니다. 정렬된 배열에서 원소 찾기는 로그에 되지만, 제약조건이 없는 배열에서 특정 원소를 찾는 서브리니어 알고리즘은 없습니다.

풀어서 쓰면 다음과 같습니다.

  • 플로이드 알고리즘은 정점의 개수 V에 대해 O(V³)에 작동합니다.
    물론 세제곱이라고만 말하면 명확하지 않습니다. '세제곱'인 항이 예를 들면 간선의 개수일 수도 있으니까요.
    즉 알고리즘의 입력으로 주어지는 변수 중 어떤 것이 기준인지에 대해서 엄밀하지 않은 표현이지만, 대부분 맥락을 통해 추측할 수 있습니다.
  • 다익스트라 알고리즘은 정점 개수 V, 간선 개수 E인 그래프에 대해 (binary heap 혹은 BBST를 사용하는 일반적인 경우에) O((E+V)lgV)의 시간이 소요됩니다.
    PS에서 푸는 대부분의 문제에서는 E가 V와 (규모 면에서) 비슷하기 때문에 O(ElgV)라고도 말합니다.
    게다가 여기에는 N이라는 변수가 한 군데도 없지만, O(NlgN)이라고 말해도 의미 전달이 되기 때문에 "다익스트라는 엔 로그 엔이지." 하고 말할 수도 있습니다.
  • Merge sort tree는 2차원 점을 저장하는 자료구조입니다. 점들의 한쪽 축 좌표를 모두 압축했다면, N개의 점을 저장할 때 전처리 O(NlgN)의 시간이 소요되고, 직사각형 영역의 점의 개수를 질의하는 쿼리에 O(lg²N)의 시간으로 대답할 수 있습니다. 그럼 쿼리의 개수가 Q개일 때 O(Qlg²N)의 시간이 소요되겠네요.
    그런데 마찬가지로 대충 "엔 로그제곱 엔"이나 "로그 제곱"이라고만 지칭해도 이해합니다. 쿼리 당 "로그 제곱"이라는 말은 확실히 맞는 말이지요. 그리고 merge sort tree를 사용하는 문제에서는 Q와 N이 모두 10만의 규모인 경우가 많기 때문에, 결과적으로 어느 값을 어느 자리에 쓰드 "십만 로그제곱 십만"이라서 큰 오해도 아닌 셈입니다.
  • 정렬된 배열에서 이분 탐색을 사용하면, 배열의 크기가 N일 때 O(lgN)번의 비교로 원하는 원소의 존재 여부를 알 수 있습니다.
    물론 두 원소의 비교가 단순하지 않다면 (예를 들어 문자열이나 리스트를 사전순 비교할 경우) 시간복잡도가 O(lgN)이 아닐 수도 있겠지만, 그런 경우에는 듣는 사람도 그 점을 생각하고 있을 테니 크게 중요하지 않겠습니다.
    반면 조건이 없는 배열은 최악의 경우 모든 원소를 비교해야 하므로 최소한 Θ(N)의 시간이 시간이 걸리고, 이보다 개선할 방법이 없습니다. 즉 선형보다 빠른, 다르게 말하면 서브리니어(sublinear)한 방법은 없습니다.

 

 

'알고리즘 문제풀기 > 기타 주제' 카테고리의 다른 글

PS 대회 모음  (0) 2019.07.04
정보 올림피아드  (0) 2019.06.16
PS 계열 커뮤니티와 웹 사이트  (4) 2019.04.23
PS 토픽 모음  (1) 2019.04.21
CMS 세팅 (워커 등 분리)  (1) 2018.08.02