PS (Problem Solving)

용어 정리

채점 결과

• AC: Accepted = 맞았습니다!!
• MLE: Memory Limit Exceeded = 메모리 초과
• PE: Presentation Error = 출력 형식이 잘못되었습니다
• OLE: Output Limit Exceed = 출력 초과
• RE: Runtime Error = 런타임 에러
• TLE: Time Limit Exceeded = 시간 초과
• WA: Wrong Answer = 틀렸습니다
• UB: Undefined Behavior, 배열 인덱스 밖으로 벗어난 곳을 참조하는 경우가 대표적

알고리즘 약어

그래프

• 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 (모의 담금질 기법)
• BT: BackTracking (백트랙킹)
• BS: Binary Search (이진 탐색)