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

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

OJ들 (Online Judge)

  • BOJ,백준: Baekjoon Online Judge
  • CF,코포: Codeforces
  • 앳코: Atcoder
  • USACO: USA Computing Olympiad
  • xOI: (지명) Olympiad in Informatics (ex. InternationalOI, BalticOI, KoreaOI, JpaneseOI,...)
  • ICPC: International Collegiate Programming Contest

기본 용어들

  • PS: Problem Solving (문제 풀이)
  • CP: Competitive Programming (경쟁 프로그래밍)
  • CS: Computer Science (컴퓨터 과학)
  • STL: Standard Template Library (표준 템플릿 라이브러리)
  • 맞왜틀: 맞는 것 같은데 왜 틀리지
  • 틀왜맞: 틀릴 것 같은데 왜 맞지
  • 솔브닥: Solved.ac 티어 안내 서비스
  • 업솔빙: $\frac{\mathrm{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}$의 약자. '다음을 만족하는' 이라는 뜻이다.
  • ∎: 증명 완료
  • $\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 (사이클이 없는 유향 그래프)
  • MST: Min/Max Spanning Tree (최소/최대 스패닝 트리)
  • HLD: Heavy Light Decomposition (트리 중-경 분해)

수학

  • BI: Big Integer
  • FFT: Fast Fourier Transform (고속 푸리에 변환)
  • GCD: Greatest Common Divisor (최대공약수)
  • LCM: Least Common Multiple (최소공배수)
  • 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 Substring (최장 공통 부분문자열)
  • MSB: Most Significant Bit (최상위 비트)
  • MS(1or0)B: Most Significant (1or0) Bit (최상위 (1or0) 비트)
  • LS(1or0)B: Least Significant (1or0) Bit (최하위 (1or0) 비트)
  • SA: Suffix Array (접미사 배열)

그외

  • CCW: Counter Clockwise (반시계 방향, 혹은 세 점간의 방향 관계를 알아내는 알고리즘)
  • D&C: Divide and Conquer (분할정복)
  • DP: Dynamic Programming (동적계획법)
  • LIS: Longest Increasing Subsequence (최장 증가 부분수열)
  • 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님, o98123님


댓글 (16개) 댓글 쓰기


pentagon03 1년 전

좋은 글이네요!


dohoon 1년 전

감사합니다!


ronaldo 1년 전

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

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

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

SA -> Suffix Array / Simulated Annealing


dohoon 1년 전

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

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


bally14 1년 전

와~!좋은 글이네요^^


dohoon 1년 전

감사합니다!


yedamdamdam007 1년 전

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


dohoon 1년 전

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


hs9200 1년 전

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


ksjlinker 1년 전

백준에는 다양한 용어들이 있었군요. 좋은 정보 감사합니다.


dohoon 1년 전

"백준 저지"에 한정된 용어들은 아닙니다! 알고리즘 문제 풀이 문화 전반에 걸친 용어라고나 할까요? 전 정보를 여기저기서 듣고 정리했을 뿐입니당..! 많은 도움 되셨길 바랍니닷



fman1335 1년 전


dohoon 1년 전

감사합니당


o98123 8달 전

LIS가 문자열에 들어가나요?


dohoon 8달 전

자연스럽게 LCS 옆에 끼어있었네요 ㅋㅋㅋ 수정했습니다. 감사합니다!