알고리즘 용어집

알고리즘 분야의 개념 56개를 한 장에 모았습니다. 가지치기 · 격자 · 비터비 · 비용 · 공간 복잡도 · 그래프 모델링 등 — 코드베이스에서 뽑아 뜻과 관계를 정리했습니다.

가지치기 (pruning)
지금까지의 선택으로는 답이 될 수 없음이 확실한 가지를 더 내려가지 않고 버린다
격자 · 비터비 · 비용 (Viterbi)
글자 경계마다 노드를 두고 사전 후보를 간선으로 깐 격자에서, 단어 비용 + 연접 비용의 합이 가장 낮은 경로를 비터비로 고른다. 노리는 규칙이 아니라 이 비용으로 자른다
공간 복잡도 (space complexity, auxiliary space)
입력 크기에 따라 추가로 쓰는 메모리가 늘어나는 정도. 재귀 호출 스택도 포함한다
그래프 모델링
관계를 정점과 간선으로 표현하고 그 위를 순회한다. 최단 단계 거리는 BFS, 경로 · 순환 탐지는 DFS, 의존 순서는 위상 정렬로 푼다
깊이 우선 탐색 (DFS, depth-first search)
한 경로를 끝까지 파고든 뒤 되돌아와 다른 경로를 본다. 재귀나 스택으로 구현하고, 방문 중 · 방문 끝 상태를 나누면 순환을 찾는다. O(V+E)
너비 우선 탐색 (BFS, breadth-first search, flood fill)
시작점에서 가까운 정점부터 큐로 한 겹씩 넓혀 방문한다. 가중치 없는 그래프에서 최소 간선 수 경로를 준다. O(V+E)
다양성 · 비즈니스 규칙
같은 것만 몰리지 않게 하고 운영 규칙(가중치 · 제외)을 건다. 모델 점수 위에 얹는 하드 규칙이라 평가 지표와 충돌할 수 있다
덴스 · ANN (approximate nearest neighbor, dense retrieval, kNN, 벡터 검색)
뜻이 가까운 것을 벡터 근사 최근접 탐색으로 찾는다. 바꿔 말한 질의 · 다국어 · 설명형에 강하고, 모델이 못 본 고유명사 · 숫자 · 코드에 약하다
동적 계획법 (dynamic programming, DP, 동적 프로그래밍)
겹치는 부분 문제의 답을 표에 저장해 한 번만 계산한다. 위에서 내려가며 저장(메모이제이션)하거나 작은 문제부터 표를 채운다(타뷸레이션). 최적 부분 구조가 있어야 한다
랭킹
합친 후보의 최종 순서를 정한다 — 피처 결합(규칙) → Learning to Rank → 리랭킹 모델로 갈수록 후보는 줄고 문서당 비용은 는다
랭킹 손실 세 갈래 (listwise, pairwise, pointwise)
포인트와이즈(문서 하나의 점수) · 페어와이즈(두 문서의 순서) · 리스트와이즈(목록 전체 지표). LambdaMART 는 nDCG 변화량을 그래디언트에 넣는 리스트와이즈 계열
리랭킹 모델 (reranker, re-ranking)
상위 후보만 무거운 모델로 다시 채점한다. 신경망 리랭커는 GPU 없이는 성립하기 어렵고, 트리 모델 LTR 은 CPU 로 된다
리트리벌 (retrieval, 리트리벌, first-stage retrieval)
키워드 · 덴스(그리고 학습형 스파스) 검색이 각자 상위 후보를 낸다. 1단계가 놓친 문서는 2단계가 되살릴 수 없어서 리랭킹보다 1단계 재현율이 먼저다
마트료시카 임베딩 (MRL, Matryoshka Representation Learning)
앞쪽 차원만 잘라 써도 뜻이 보존되게 학습한 임베딩(MRL). 2560 차원 모델을 1024 로 잘라 저장하는 식으로 메모리와 정확도를 맞바꾼다
메모이제이션 (memoization, top-down DP)
같은 인자로 부른 함수의 결과를 저장해 두고 다시 부르면 저장값을 돌려준다. 재귀형 DP 의 구현 방법이다
백트래킹 (backtracking, N-Queens, permutation, combination)
후보를 하나씩 골라 해를 늘려 가다가 조건을 어기면 직전 선택으로 되돌아가 다른 후보를 본다. 가망 없는 가지를 일찍 잘라야 쓸 만한 속도가 나온다
밴딧 · 탐색 (multi-armed bandit, MAB)
팔(노출 후보)마다 보상 분포를 갖고 확실한 팔을 쓰면서 불확실한 팔을 시험한다. 보상이 즉시 오는 1단계 문제라 강화학습 본체는 쓰지 않는다. 고정 기간 A/B 대신 트래픽을 이기는 쪽으로 옮겨 간다
베타-베르누이 켤레 (Beta-Bernoulli)
클릭/노출 같은 성공·실패 관측에 베타 분포 사전을 두면 사후도 베타 분포다(α = 클릭 + α₀, β = 비클릭 + β₀). Thompson Sampling 이 팔마다 여기서 표본을 뽑아 순서를 정한다
복잡도 분석
입력 크기 n 이 커질 때 시간과 메모리가 어떻게 늘어나는지 점근적으로 셈해 자료 구조와 알고리즘을 비교한다
분할 상환 분석 (amortized analysis, 상환 분석, accounting method, potential method)
가끔 비싼 연산을 전체 연산 수로 나눠 한 번당 평균 비용을 셈한다. 동적 배열의 확장처럼 드물게 O(n) 이 섞여도 삽입 한 번은 O(1) 로 본다
분할 정복 (divide and conquer)
문제를 겹치지 않는 작은 문제로 나눠 재귀로 풀고 결과를 합친다. 병합 정렬 · 퀵 정렬 · 이진 탐색이 이 틀이고, 비용은 마스터 정리로 셈한다
분해 비용 재학습
정답 분해가 붙은 도메인 코퍼스로 비용표(CRF)를 다시 배운다. 형태소 분석기의 「지도학습」은 이 층을 가리킨다. 라벨 코퍼스가 없으면 착수가 아니다
비터비 알고리즘 (Viterbi)
격자에서 총비용 최소 경로를 왼쪽에서 오른쪽으로 한 번 훑어 찾는 동적 계획법. 노드마다 「여기까지의 최소 비용과 직전 간선」만 남긴다
빅오 표기법 (Big-O, 점근 표기법)
증가율의 상한을 가장 큰 항만 남겨 적는 표기. 상수와 낮은 차수 항은 버린다. O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
성향 역수 가중 (IPS, IPW, propensity clipping)
로그 정책이 그 노출을 고를 확률(성향)의 역수로 가중해 다른 정책의 지표를 추정한다(IPS). 성향이 작으면 가중이 폭발해 하한으로 자른다(clipping)
순환 의존 (cycle, circular dependency, 순환)
의존 관계가 한 바퀴 돌아 자기 자신에게 돌아오는 상태. 위상 순서가 존재하지 않아 어떤 것부터 처리할지 정할 수 없다
스택 오버플로 (stack overflow, StackOverflowError)
재귀가 너무 깊어 호출 스택 메모리를 넘는 상태. 반복문과 명시적 스택으로 바꾸거나 깊이를 제한한다
스파스 · BM25 (BM25, Okapi BM25, sparse retrieval, lexical retrieval, 키워드 검색)
글자가 맞는 것을 찾는다. 빈도 포화(k1)와 문서 길이 정규화(b)를 더한 TF-IDF 계열로, 렉시컬 검색의 기본값이다. 고유명사 · 정확 일치 · 희귀어에 강하다
시간 복잡도 (time complexity)
입력 크기에 따라 연산 횟수가 늘어나는 정도. 보통 최악의 경우를 빅오로 적는다
안정 정렬 (stable sort)
정렬 키가 같은 원소들의 원래 순서를 유지하는 정렬. 여러 기준으로 차례로 정렬할 때 필요하다(병합 정렬은 안정, 퀵 정렬은 아니다)
알고리즘 설계 기법
문제의 구조를 보고 푸는 틀을 고른다. 쪼개서 합치기(분할 정복), 부분 답 재사용(동적 계획법), 매 순간 최선(탐욕), 모든 후보를 되돌아가며 시도(백트래킹), 구간을 밀며 한 번에 훑기(투 포인터 · 슬라이딩 윈도), 무작위화
위상 정렬 (topological sort, Kahn's algorithm)
방향 비순환 그래프(DAG)의 정점을 모든 간선이 앞에서 뒤로 향하게 나열한다. 진입 차수 0 부터 꺼내는 칸 알고리즘이나 DFS 종료 역순으로 구한다. 빌드 · 작업 의존 순서에 쓴다
의도 → 필터 승격
뜻을 검색어에서 빼 필터로 옮긴다. BM25 레그에만 걸고 벡터 레그는 원문을 받는다. 문서 쪽에 받을 신호가 없는 의도는 필터로 만들지 않는다 — 있는 결과까지 지운다
이진 탐색 (binary search, lower bound, upper bound)
정렬된 배열에서 가운데와 비교해 절반을 버리며 찾는다. O(log n). 같은 값이 여럿이면 처음 · 끝 위치(lower bound · upper bound)를 찾는다
일관 해싱 (consistent hashing, 해시 링)
노드와 키를 같은 해시 링에 올려 키를 시계 방향 첫 노드에 둔다. 노드가 늘거나 줄 때 옮겨지는 키가 전체의 1/N 정도로 줄어든다
임베딩 모델
문서와 검색어를 같은 벡터 공간으로 보내는 모델. 양쪽이 같은 모델이어야 한다
재귀 (recursion, tailrec)
함수가 더 작은 입력으로 자기 자신을 부른다. 트리처럼 자기 닮은 구조를 순회할 때 자연스럽고, 깊이가 깊으면 스택 오버플로를 조심한다(Kotlin 은 tailrec 으로 꼬리 재귀를 반복문으로 바꾼다)
재채점 · 오버샘플 (oversample factor)
양자화 벡터로 k 의 몇 배를 뽑은 뒤 원본 벡터로 다시 채점해 상위 k 를 낸다. 배수를 올리면 정확도가 오르고 지연이 는다
정규화
대소문자 · 공백 · 기호 · 전각/반각을 통일한다. 색인과 질의가 같은 규칙이어야 하고, 질의 벡터 캐시의 키도 이 결과다
정렬 (sort, sorting algorithm)
원소를 비교 기준에 따라 순서대로 나열한다. 비교 정렬의 하한은 O(n log n) 이고 병합 · 퀵 · 힙 정렬이 여기 닿는다. 값의 범위가 좁으면 비교 없이 O(n) 에 가까운 계수 · 기수 정렬을 쓴다
조합 폭발 (combinatorial explosion, exponential blow-up)
입력이 조금 늘 때 살펴볼 후보 수가 지수 · 계승으로 늘어 계산이 끝나지 않는 상태
중복 부분 문제 (overlapping subproblems)
재귀로 풀 때 같은 부분 문제가 여러 번 나오는 성질. 이것이 있어야 답을 저장하는 동적 계획법이 이득이다
최적 부분 구조 (optimal substructure)
전체 문제의 최적해가 부분 문제의 최적해로 이뤄지는 성질. 동적 계획법과 탐욕 알고리즘의 전제다
컨텍스추얼 밴딧 (contextual bandit)
팔의 보상을 문맥(시간대 · 기기 · 이전 클릭)의 함수로 배운다. 팔당 노출이 수백 건은 쌓인 뒤의 일이다
코사인 유사도 (cosine, cosinesimil)
두 벡터의 각도로 재는 유사도(내적 ÷ 크기의 곱). 정규화된 벡터에선 내적과 같다. 텍스트 벡터 검색의 기본 거리
쿼리 언더스탠딩 (query understanding, 검색어 의도 분석)
검색어에서 뜻을 읽어 필터 · 잔여 검색어 · 정책 스위치로 가른다. 같은 낱말이 셋 중 어디로 가느냐가 결과를 가른다 — 필터는 안 맞으면 탈락, 검색어는 점수 경쟁, 스위치는 순위 규칙을 바꾼다
쿼리 임베딩
검색어를 벡터화한다. 같은 검색어는 다시 만들지 않는다. 질의 타워를 어디에 두느냐가 지연과 품질의 교환을 정한다
키워드 유형 분류
검색어의 낱말을 유형 · 분류 · 대상 · 스톱워드로 가른다
탐색 · 활용 (explore-exploit)
확실히 좋은 팔을 쓰는 것(활용)과 불확실한 팔을 시험하는 것(탐색)의 균형. 탐색이 0 이면 새 후보는 영영 못 올라온다
탐색과 정렬
원소를 기준에 따라 나열하고, 정렬된 데이터에서 원하는 값을 반씩 줄여 찾는다. 정렬 비용을 한 번 내면 이후 탐색이 싸진다
탐욕 알고리즘 (greedy algorithm, 그리디, interval scheduling)
매 단계에서 지금 가장 좋아 보이는 선택을 하고 되돌아보지 않는다. 탐욕 선택 속성과 최적 부분 구조가 증명될 때만 최적해를 준다(구간 스케줄링 · 허프만 · 다익스트라)
하이브리드 RRF
점수 스케일이 다른 두 후보 목록을 합친다. BM25 점수와 코사인은 단위가 달라 그대로 더하면 큰 쪽이 이긴다. 융합 전에 두 레그에 같은 필터를 건다
형태소 분석
조사 · 어미를 떼고 어간을 남긴다. 「아이와」가 「아이」+「와」로 갈리는 노이즈도 여기서 난다
CRF (Conditional Random Field, 조건부 무작위장)
조건부 무작위장(Conditional Random Field). 문장 전체를 보고 각 위치의 라벨(형태소 경계·품사) 열을 확률로 매기는 판별 모델. MeCab 계열은 학습한 CRF 가중치를 단어 비용·연접 비용으로 바꿔 사전에 굽는다
Learning to Rank (LTR)
(쿼리, 문서, 등급) 라벨로 재정렬 함수를 배운다. 트리 모델은 GPU 없이 상위 N 을 몇 ms 에 다시 채점한다. 토큰이 어긋난 문서는 여기까지 오지 않는다
RRF (Reciprocal Rank Fusion, 하이브리드 결합, 키워드 · 벡터 결합)
Reciprocal Rank Fusion — 각 목록의 순위 역수 1/(k + rank)를 더해 합친다. 점수를 안 봐 스케일 · 분포에 무관하고 튜닝할 값이 k 하나(관례 60)다

다른 분류