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

www.acmicpc.net/blog/view/102

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

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

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 티어 안내 서비스
• 업솔빙: absorbing+upsolving2 (≈대회 때 못 푼 문제/헷갈리는 문제를 곱씹어보는 과정)
• 예제: 문제에서 주어진 input과 output
• 테케: 테스트 케이스의 약자로, 예제의 일반화. 조건을 만족한다면 다 통용해서 사용함.
• 올솔: All Solve! 다 풀어낸 경우
• NGD: 노가다. 수학에서 자주 쓰여서 자연스럽게 PS에서도 통용됨.
• wlog: WithoutLossOfGenerality의 약자. 일반성을 잃지 않는다는 뜻인데, 예를 들어 a,b,c 세 수의 관계가 대칭적일 경우 a≤b≤c라고 순서를 강제하는 것이 있다.
• isw: IntheSameWay의 약자. 직역하면 같은 방식으로. 값만 바뀌고 동일한 구조를 유지하는 경우 똑같은 것을 또 쓰는 것을 막기 위함이다.
• s.t.: suchthat의 약자. '다음을 만족하는' 이라는 뜻이다.
• ∎: QED (유클리드가 증명을 끝마친 후 "이것이 보여져서 참이다" 정도의 의미를 라틴어로 적었던 것)
• i.e.: idest의 약자. 영어로는 that is 정도의 의미이다. '즉,'과 같은 의미이다. (사실 '즉'이 더 짧은 것 같은데?)
• ∀: for all이라는 뜻. "모든 ~에 대해서"라고 할 때 사용한다.
• ∃: 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님