알고리즘 문제풀이를 함에 있어서 자주 접하게 될 용어들

이런 약자들에 대해 다룬 글이 하나쯤은 있었을 것 같지만, 잘 나오지 않아서 정리해 보았습니다. 이런 종류의 글은 백준 블로그에 어울리지 않았을까 하는 생각이지만, 저도 처음 써보는 거라 이상한 점 있으시면 피드백 주세요^^

OJ들 (Online Judge)

  • BOJ: Baekjoon Online Judge
  • CF: Codeforces
  • 앳코: Atcoder
  • LA: Live Archive
  • WF: World Finals
  • USACO: USA Computing Olympiad
  • AOJ: Algospot Online Judge

기본 용어들

  • PS: Problem Solving (문제 풀이)
  • CP: Competitive Programming (경쟁 프로그래밍)
  • CS: Computer Science (컴퓨터 과학)
  • STL: Standard Template Library (표준 템플릿 라이브러리)
  • 맞왜틀: 맞는 것 같은데 왜 틀리지
  • 틀왜맞: 틀릴 것 같은데 왜 맞지
  • 솔브닥: Solved.ac 티어 안내 서비스
  • 업솔빙: $\frac{absorbing + upsolving}{2}$ (≈대회 때 못 푼 문제/헷갈리는 문제를 곱씹어보는 과정)
  • 예제: 문제에서 주어진 input과 output
  • 테케: 테스트 케이스의 약자로, 예제의 일반화. 조건을 만족한다면 다 통용해서 사용함.
  • 올솔: All Solve! 다 풀어낸 경우
  • NGD: 노가다. 수학에서 자주 쓰여서 자연스럽게 PS에서도 통용됨.
  • $\mathrm{wlog}$: $\mathrm{Without\, Loss\, Of\, Generality}$의 약자. 일반성을 잃지 않는다는 뜻인데, 예를 들어 $a, b, c$ 세 수의 관계가 대칭적일 경우 $a\leq b\leq c$라고 순서를 강제하는 것이 있다.
  • $\mathrm{isw}$: $\mathrm{In\; the\; Same\; Way}$의 약자. 직역하면 같은 방식으로. 값만 바뀌고 동일한 구조를 유지하는 경우 똑같은 것을 또 쓰는 것을 막기 위함이다.
  • $\mathrm{s.t.}$: $\mathrm{such\; that}$의 약자. '다음을 만족하는' 이라는 뜻이다.
  • ∎: QED (유클리드가 증명을 끝마친 후 "이것이 보여져서 참이다" 정도의 의미를 라틴어로 적었던 것)
  • $\mathrm{i.e.}$: $\mathrm{id\; est}$의 약자. 영어로는 that is 정도의 의미이다. '즉,'과 같은 의미이다. (사실 '즉'이 더 짧은 것 같은데?)
  • $\forall$: for all이라는 뜻. "모든 ~에 대해서"라고 할 때 사용한다.
  • $\exists$: exists라는 뜻. "~인 ~가 존재한다"라고 할 때 사용한다.

채점 결과

  • AC: Accepted = 맞았습니다!!
  • CE: Compile Error = 컴파일 에러
  • MLE: Memory Limit Exceeded = 메모리 초과
  • PE: Presentation Error = 출력 형식이 잘못되었습니다
  • OLE: Output Limit Exceed = 출력 초과
  • RE: Runtime Error = 런타임 에러
  • TLE: Time Limit Exceeded = 시간 초과
  • WA: Wrong Answer = 틀렸습니다
  • UB: Undefined Behavior, 배열 인덱스 밖으로 벗어난 곳을 참조하는 경우가 대표적. 링크 : UB에 관한 evenharder님의 글 참고!
  • 더 참고할 만한 것들: 링크 : 틀리는 이유에 관한 백준님의 글 참고!

알고리즘 약어 📌

그래프

  • APSP: All Pairs Shortest Path (모든 쌍 최단경로)
  • SSSP: Single Soure Shortest Path (한 점에서 시작하는 최단경로)
  • AVL: Adelson-Velskii Landis (아델슨-벨스키 란디스 이진 탐색 트리)
  • DFS: Depth First Search (깊이 우선 탐색)
  • BFS: Breadth First Search (너비 우선 탐색)
  • BST: Binary Search Tree (이진 탐색 트리)
  • DAG: Directed Acyclic Graph (사이클이 없는 유향 그래프)
  • GPC: General Path Cover (일반 경로 커버)
  • MPC: Minimum Path Cover (최소 경로 커버)
  • MST: Min/Max Spanning Tree (최소/최대 스패닝 트리)
  • LCT: Link Cut Tree (링크 컷 트리)
  • HLD: Heavy Light Decomposition (트리 중-경 분해)

수학

  • BI: Big Integer
  • FFT: Fast Fourier Transform (고속 푸리에 변환)
  • GCD: Greatest Common Divisor (최대공약수)
  • LCM: Least Common Multiple (최소공배수)
  • MCM: Matrix Chain Multiplication (행렬 연쇄곱)
  • CRT: Chinese Remainder Theorem (중국인의 나머지 정리)

자료구조

  • DS: Data Structure (자료구조)
  • BIT: Binary Indexed Tree (이진 인덱스 트리 a.k.a. 펜윅 트리)
  • DSU: Disjoint Set Union (분리 집합 a.k.a. 유니온-파인드)
  • 세그: Segment Tree (구간 트리)

문자열

  • LCA: Lowest Common Ancestor (최소 공통 조상)
  • LCP: Longest Common Prefix (최장 공통 접두사)
  • LCS: Longest Common Subsequence (최장 공통 부분수열)
  • LIS: Longest Increasing Subsequence (최장 증가 부분수열)
  • MSB: Most Significant Bit (최상위 비트)
  • MS(1or0)B: Most Significant (1or0) Bit (최상위 (1or0) 비트)
  • LS(1or0)B: Least Significant (1or0) Bit (최하위 (1or0) 비트)
  • SA: Suffix Array (접미사 배열)

그외

  • CC: Coin Change (동전 교환)
  • CCW: Counter Clockwise (반시계 방향, 혹은 세 점간의 방향 관계를 알아내는 알고리즘)
  • D&C: Divide and Conquer (분할정복)
  • DP: Dynamic Programming (동적계획법)
  • FIFO: First In First Out (선입선출)
  • LIFO: Last In First Out (후입선출)
  • IMPL: implementation (구현)
  • RMQ: Range Min/Max Query (구간 최소/최대 질의)
  • RSQ: Range Sum Query (구간 합 질의)
  • SA: Simulated Anealing (모의 담금질 기법)


*기여: ronaldo님


댓글 (9개) 댓글 쓰기


pentagon03 1달 전

좋은 글이네요!


dohoon 1달 전

감사합니다!


ronaldo 29일 전

LCT -> Link Cut Tree 많이 보진 않았지만 쓰긴 쓰는 것 같네요

HLD -> Heavy-Light Decomposition 많이 쓰는 것 같기도 해요

D&C Optimization -> Divide and Conquer Optimization DP 최적화 관련 내용인 듯 해요

SA -> Suffix Array / Simulated Annealing


dohoon 23일 전

의견 감사해요!! HLD님을 빼먹다니...

분할정복 최적화는 두 단어의 합성이라서 생략했습니다~


bally14 23일 전

와~!좋은 글이네요^^


dohoon 23일 전

감사합니다!


yedamdamdam007 10일 전

와 수고하셨어요! 대단하네요:-)


dohoon 10일 전

감사합니다!! 모두 열심히 공부해요~!


hs9200 5일 전

아 그래서 그동안 용어를 몰랐구나 더 공부해야겠다;;