문서 둘러보기
p-군
p-군은 고정된 소수 p에 대해 모든 원소의 위수가 p의 거듭제곱인 군이다. 유한군에서는 군의 위수가 pⁿ인 것과 동치다. 여기서 n은 0 이상인 정수이며 항등원의 위수 1도 p⁰으로 포함한다.
멱영군
멱영군은 중심을 차례로 확장해 만드는 상부 중심열이 유한 단계 안에 군 전체에 도달하는 군이다. 가환군은 멱영군이며, 사원수군처럼 가환이 아니면서 멱영인 군도 있다.
가해군
가해군은 군 전체에서 항등원 부분군까지 내려가는 유한한 부분군 열을 잡되, 각 단계의 부분군이 바로 앞 단계에서 정규이고 그 몫군이 가환군이 되도록 할 수 있는 군이다. 군 자체가 가환군이어야 하는 것은 아니다.
사원수군
사원수군 Q₈은 사원수 1, −1, ±i, ±j, ±k의 여덟 원소로 이루어진 곱셈군이다. i²=j²=k²=ijk=−1을 만족하며 ij=k와 ji=−k이므로 가환군이 아니다.
실로 정리
실로 정리는 유한군의 소수 거듭제곱 위수 부분군의 존재와 켤레 관계, 개수를 제한하는 정리다. |G|=pᵃm이고 p가 m을 나누지 않을 때 위수 pᵃ인 부분군을 실로 p-부분군이라 한다.
가환화
군 G의 가환화는 교환자 부분군 [G,G]로 나눈 몫군 G/[G,G]와 자연스러운 몫사상이다. 비가환인 곱의 순서 차이를 몫에서 없애 가환군을 얻으며, 가환군으로 가는 모든 군 준동형은 이 몫사상을 통해 인수분해된다.
완전군
완전군은 자기 자신의 교환자 부분군과 같은 군이다. 즉 G=[G,G]이며 가환화 G/[G,G]는 자명한 군이다. 비가환 단순군은 완전군이지만 완전군이 반드시 단순군인 것은 아니다.
교환자 (군론)
군론의 교환자는 두 원소가 교환하는지를 나타내는 군 원소다. 여기서는 [a,b]=aba⁻¹b⁻¹로 정의한다. [a,b]=e인 것과 ab=ba인 것은 동치이며, 교환자의 값을 읽을 때는 사용한 정의를 확인해야 한다.
교환자 부분군
교환자 부분군 [G,G]는 군 G의 모든 교환자로 생성되는 부분군이다. G의 정규부분군이며 몫군 G/[G,G]는 가환군이다. G가 이미 가환군이면 교환자 부분군은 항등원만으로 이루어진다.
정규화군
군 G의 부분군 H의 정규화군 N_G(H)는 gHg⁻¹=H를 만족하는 G의 원소 g 전체다. H를 켤레로 옮겨도 같은 부분군으로 유지하는 원소들을 모은 군이며 H는 그 안에서 정규부분군이 된다.
단순군
단순군은 자명한 군이 아니면서 정규부분군이 항등원만의 부분군과 군 전체 두 개뿐인 군이다. 모든 부분군이 없어야 한다는 뜻은 아니며, 정규성이 없는 부분군은 존재할 수 있다.
순열의 순환 분해
순열의 순환 분해는 유한집합의 순열을 서로 겹치지 않는 순환들의 곱으로 나타내는 방법이다. 각 순환은 원소가 순열을 반복 적용받으며 차례로 이동하다가 출발점으로 돌아오는 경로를 기록한다.
교대군
교대군 Aₙ은 n개 원소의 순열 중 짝순열만 모은 군이다. 대칭군 Sₙ의 정규부분군이며 n≥2일 때 위수는 n!/2다. 여기서 짝순열이란 짝수 개의 전치를 합성해서 나타낼 수 있는 순열을 뜻한다.
전치 (순열)
순열에서 전치는 서로 다른 두 원소를 맞바꾸고 나머지는 그대로 두는 순열이다. 보통 (a b)로 쓰며 같은 전치를 두 번 합성하면 항등순열이 된다. 모든 유한 순열은 전치들의 합성으로 나타낼 수 있다.
클라인 사원군
클라인 사원군은 원소가 네 개이며 비항등원 세 개의 위수가 모두 2인 군이다. 2원소 순환군 두 개의 직접곱 C₂×C₂로 나타낼 수 있고, 원소가 네 개인 순환군 C₄와는 동형이 아니다.
군의 직접곱
군의 직접곱 G×H는 순서쌍들의 집합에 좌표별 군 연산을 준 구조다. (g₁,h₁)(g₂,h₂)=(g₁g₂,h₁h₂)로 계산하며 각 좌표에서는 해당 군의 연산을 사용한다.
류 방정식 (군론)
군론의 류 방정식은 유한군의 원소 수를 중심의 크기와 중심 밖 켤레류들의 크기의 합으로 나타낸 식이다. 각 비중심 켤레류에서 대표원 aᵢ를 하나씩 고르면 |G|=|Z(G)|+Σᵢ[G:C_G(aᵢ)]이다.
코시 정리 (군론)
군론의 코시 정리는 유한군 G의 위수를 나누는 소수 p에 대해 위수가 p인 원소가 G 안에 존재한다는 정리다. 그 원소가 생성하는 순환부분군의 위수도 p이므로 소수 위수의 부분군 존재를 함께 보장한다.
중심화군
중심화군은 군의 특정 원소 또는 부분집합의 모든 원소와 교환하는 군 원소들을 모은 부분군이다. 한 원소 a에 대해 C_G(a)={g∈G | ga=ag}로 나타낸다. 군 전체와 교환해야 하는 중심보다 조건이 약하다.
켤레류
켤레류는 군의 한 원소 a를 gag⁻¹ 꼴로 바꾸어 얻는 모든 원소들의 집합이다. 여기서 g는 군 전체를 움직인다. 같은 켤레류에 속한다는 관계는 동치관계이며 군을 서로 겹치지 않는 켤레류들로 분할한다.
중심 (군론)
군의 중심 Z(G)는 G의 모든 원소와 교환하는 원소들의 집합이다. Z(G)={z∈G | zg=gz, 모든 g∈G}로 나타낸다. 군의 연산이 얼마나 가환적인지와 관련되지만 도형의 중앙에 놓인 점을 가리키는 말은 아니다.
케일리 정리 (군론)
군론의 케일리 정리는 모든 군이 어떤 순열군과 동형으로 나타날 수 있다는 정리다. 특히 원소가 n개인 유한군은 n개 원소 집합의 대칭군 Sₙ의 부분군과 동형이다. 추상적인 군의 연산을 원소들의 자리 바꾸기로 표현할 수 있음을 뜻한다.
군 동형
군 동형은 두 군 사이의 연산을 보존하는 전단사 대응이다. 동형인 군은 원소의 이름이나 표현이 달라도 같은 군 구조를 갖는다. f:G→H가 전단사이고 모든 a,b∈G에서 f(ab)=f(a)f(b)이면 동형이다.
군 자기동형
군 자기동형은 한 군에서 자기 자신으로 가는 군 동형이다. 원소들을 전단사로 다시 배치하면서 군의 연산을 보존한다. 같은 군 G의 모든 자기동형은 함수 합성 아래 군을 이루며 이를 Aut(G)라고 쓴다.
위수 (군론)
군론에서 군의 위수는 군에 속한 원소의 개수이고, 군 원소의 위수는 그 원소를 반복해 연산하여 처음 항등원으로 돌아오는 양의 횟수다. 같은 용어를 사용하지만 군 전체의 크기와 특정 원소의 주기를 구분해야 한다.
핵 (군 준동형)
군 준동형 f:G→H의 핵은 H의 항등원으로 보내지는 G의 원소들의 집합이다. ker f={g∈G | f(g)=e_H}로 나타낸다. 핵은 G의 정규부분군이며 준동형이 서로 다른 원소를 얼마나 구분하는지 파악하는 데 쓰인다.
가환군
가환군은 군의 모든 원소 a와 b에 대해 ab=ba가 성립하는 군이다. 아벨군이라고도 한다. 군의 공리인 결합법칙에 더해 연산의 순서를 바꾸어도 결과가 같다는 교환법칙을 만족한다.
대칭군
대칭군 Sₙ은 n개 원소로 이루어진 집합의 모든 순열을 함수의 합성으로 결합한 군이다. 군의 원소는 자리 바꾸기라는 변환 자체이며, 유한한 경우 원소 수는 n!이다.
이면체군
이면체군은 정다각형을 제자리에 보존하는 회전과 반사로 이루어진 대칭군이다. 정n각형에 대해 회전 n개와 반사 n개가 있어 원소 수는 2n개다. 보통 Dₙ으로 쓰지만 D₂ₙ으로 쓰는 관례도 있어 표기의 기준을 확인해야 한다.
군 준동형
군 준동형은 두 군 사이에서 군의 연산을 보존하는 함수다. f:G→H가 모든 a,b∈G에 대해 f(ab)=f(a)f(b)를 만족하면 준동형이며, 왼쪽의 곱은 G에서 오른쪽의 곱은 H에서 계산한다.
몫군
몫군 G/N은 군 G의 정규부분군 N에 대한 잉여류들을 원소로 갖는 군이다. 연산은 (aN)(bN)=abN으로 정의한다. 정규성 덕분에 같은 잉여류를 나타내는 대표원을 바꾸어도 결과 잉여류가 달라지지 않는다.
순환군
순환군은 하나의 원소를 반복해서 연산하고 역원을 사용하여 모든 원소를 얻을 수 있는 군이다. 곱셈 표기에서는 G=⟨a⟩={aᵏ | k∈Z}로 나타낸다. 이때 a를 생성원이라고 하며 순환군은 유한할 수도 무한할 수도 있다.
정규부분군
정규부분군은 군 G의 부분군 N 중에서 모든 g∈G에 대해 gNg⁻¹=N을 만족하는 부분군이다. 동치인 조건은 gN=Ng가 모든 g에서 성립한다는 것이다. 여기서의 등식은 집합의 등식이지 모든 원소가 서로 교환한다는 뜻은 아니다.
부분군
부분군은 군 G의 부분집합 중에서 G의 연산을 그대로 사용하여 스스로 군이 되는 집합이다. 부분집합의 원소에 새 연산을 붙이는 것이 아니라 원래 군의 연산과 항등원 및 역원을 이어받는다는 점이 중요하다.
잉여류
잉여류는 군의 부분군에 속한 모든 원소를 같은 군 원소로 곱하여 얻는 집합이다. H≤G와 g∈G에 대해 gH={gh | h∈H}는 왼쪽 잉여류이고 Hg={hg | h∈H}는 오른쪽 잉여류다.
라그랑주 정리 (군론)
군론의 라그랑주 정리는 유한군의 부분군 크기가 원래 군의 크기를 나눈다는 정리다. 부분군 H에 대해 |G|=[G:H]|H|이며 [G:H]는 H의 왼쪽 잉여류 개수인 지수다. 군의 원소가 생성하는 순환부분군에도 적용된다.
궤도-안정자 정리
궤도-안정자 정리는 군 작용에서 한 원소가 움직일 수 있는 위치의 수와 그 원소를 고정하는 대칭의 수를 연결하는 정리다. 유한군 G가 집합 X에 작용하면 |G|=|Orb(x)||Stab(x)|이다.
군 작용
군 작용은 군의 원소를 집합의 원소를 바꾸는 변환으로 해석하되 군의 곱과 변환의 합성이 서로 맞도록 정한 구조다. 왼쪽 작용에서는 항등원 e가 e·x=x를 만족하고, g·(h·x)=(gh)·x가 모든 원소에 대해 성립한다.
번사이드 보조정리
번사이드 보조정리는 대칭으로 같다고 보는 대상들의 종류 수를 고정점 개수의 평균으로 구하는 정리다. 유한군 G가 유한집합 X에 작용할 때 궤도 수는 (1/|G|)Σ₍g∈G₎|Fix(g)|이며 Fix(g)는 g를 적용해도 변하지 않는 원소들의 집합이다.
다항계수
다항계수는 여러 종류의 항을 정해진 횟수만큼 선택하거나 배열하는 경우의 수를 나타내는 수다. n₁+⋯+nᵣ=n인 음이 아닌 정수들에 대해 n!/(n₁!⋯nᵣ!)로 정의하며 다항정리에서 대응하는 단항식의 계수가 된다.
다중집합
다중집합은 원소의 순서는 구분하지 않지만 각 원소가 나타나는 횟수는 구분하는 집합과 비슷한 대상이다. 보통의 집합과 달리 같은 원소를 여러 번 포함할 수 있으며, 그 횟수를 중복도라고 한다.
다항정리
다항정리는 여러 항의 합을 음이 아닌 정수 거듭제곱으로 전개하는 공식이다. (x₁+⋯+xᵣ)ⁿ의 각 항 x₁ⁿ¹⋯xᵣⁿʳ의 계수는 n!/(n₁!⋯nᵣ!)이며, 지수들은 음이 아닌 정수이고 합이 n이어야 한다.
하키 스틱 항등식
하키 스틱 항등식은 파스칼의 삼각형에서 한 대각선을 따라 놓인 이항계수들의 합을 하나의 이항계수로 나타내는 공식이다. 정수 n≥r≥0에서 Σₖ₌ᵣⁿ binom(k,r)=binom(n+1,r+1)이다. 삼각형에서 항들을 잇는 모양 때문에 붙은 이름이다.
반더몬드 항등식
반더몬드 항등식은 두 집단에서 나누어 선택하는 경우의 수를 이항계수의 합으로 나타내는 항등식이다. 음이 아닌 정수 m, n, r에 대해 Σₖ₌₀ʳ binom(m,k)binom(n,r−k)=binom(m+n,r)이며, 선택할 수 없는 경우의 이항계수는 0으로 둔다.
뤼카 정리 (이항계수)
이항계수에 대한 뤼카 정리는 소수 p로 나눈 이항계수의 나머지를 p진법의 각 자리 이항계수로 구하는 정리다. n과 k를 같은 자리수의 p진법으로 쓰면 binom(n,k)≡∏ binom(nᵢ,kᵢ) mod p이며, nᵢ와 kᵢ는 대응하는 자리 숫자다.
르장드르 공식 (계승)
계승에 대한 르장드르 공식은 n!의 소인수분해에서 소수 p의 지수를 구하는 공식이다. n이 음이 아닌 정수이고 p가 소수이면 vₚ(n!)=⌊n/p⌋+⌊n/p²⌋+⌊n/p³⌋+⋯이다. pᵏ가 n보다 커지면 해당 항은 0이 된다.
소수 계수 함수
소수 계수 함수 π(x)는 주어진 실수 x 이하의 소수가 몇 개인지 나타내는 함수다. 소수의 개수를 세므로 정수 값을 가지며, 소수 지점을 지날 때마다 1씩 증가하는 계단 함수다. 기호 π(x)는 원주율 π와 다른 용도로 쓰인다.
소수계승
소수계승은 일정한 범위의 소수들을 각각 한 번씩 곱한 값이다. 프라이모리얼이라고도 하며 # 기호를 사용한다. n#는 보통 n 이하의 모든 소수의 곱을 뜻하고, pₖ#는 k번째 소수 pₖ까지의 소수 곱을 뜻한다.
체비쇼프 함수
정수론의 체비쇼프 함수는 소수의 자연로그를 누적하는 두 함수 θ(x)와 ψ(x)다. θ는 x 이하의 소수를 한 번씩 반영하고, ψ는 x 이하의 소수 거듭제곱마다 밑 소수의 로그를 반영한다. 소수의 분포를 가중 합으로 다룰 때 사용한다.
폰 망골트 함수
폰 망골트 함수 Λ(n)는 양의 정수 n이 소수 p의 양의 정수 거듭제곱 pᵏ이면 ln p를 주고, 그렇지 않으면 0을 주는 수론적 함수다. 여기서 ln은 자연로그다. 소수 자체뿐 아니라 그 제곱과 세제곱 등에서도 0이 아닌 값을 갖는다.
리우빌 함수
리우빌 함수 λ(n)는 양의 정수 n의 소인수를 중복까지 포함해 센 개수의 홀짝에 따라 1 또는 −1을 주는 수론적 함수다. 그 개수를 Ω(n)이라 쓰면 λ(n)=(−1)^Ω(n)이다. Ω(1)=0이므로 λ(1)=1이다.
완전 곱셈적 함수
완전 곱셈적 함수는 모든 양의 정수 a와 b에 대해 f(ab)=f(a)f(b)를 만족하는 수론적 함수다. 서로소인 경우에만 이 등식을 요구하는 곱셈적 함수보다 강한 조건이며, 소수 거듭제곱에서도 f(pᵏ)=f(p)ᵏ가 성립한다.
디리클레 합성곱
디리클레 합성곱은 두 수론적 함수 f와 g를 약수에 대한 합으로 결합하는 연산이다. (f∗g)(n)=Σ₍d|n₎f(d)g(n/d)로 정의한다. 같은 위치의 함수값끼리만 곱하는 점별 곱과 구별된다.
곱셈적 함수
곱셈적 함수는 서로소인 양의 정수 a와 b에 대해 f(ab)=f(a)f(b)를 만족하는 수론적 함수다. 보통 f(1)=1인 함수를 대상으로 하며, 서로소 조건 없이 같은 등식이 성립하는 완전 곱셈적 함수와 구분한다.
제곱 인수가 없는 수
제곱 인수가 없는 수는 1보다 큰 완전제곱수로 나누어떨어지지 않는 양의 정수다. 소인수분해에 같은 소수가 두 번 이상 나타나지 않는다는 조건과 같다. 1도 포함하며 소수뿐 아니라 6이나 10처럼 합성수인 예도 있다.
뫼비우스 반전 공식
정수론의 뫼비우스 반전 공식은 약수에 대해 합한 함수에서 원래 함수를 복원하는 공식이다. g(n)=Σ₍d|n₎f(d)이면 f(n)=Σ₍d|n₎μ(d)g(n/d)이며, μ는 뫼비우스 함수다. 두 합 모두 n의 양의 약수를 대상으로 한다.
뫼비우스 함수
정수론의 뫼비우스 함수 μ(n)는 양의 정수 n의 소인수 구조에 따라 −1, 0, 1 중 하나를 주는 함수다. 같은 소인수가 두 번 이상 나타나면 0이고, 서로 다른 소수 k개의 곱이면 (−1)ᵏ이다. 특별히 μ(1)=1로 둔다.
더피 정사각형
더피 정사각형은 정수 분할의 페러스 다이어그램 안에 들어가는 가장 큰 정사각형이다. 왼쪽 위 모서리에 맞추어 잡을 수 있으며, 크기는 보통 한 변을 이루는 칸의 개수로 나타낸다. 분할과 그 켤레 분할의 더피 정사각형 크기는 같다.
켤레 분할
켤레 분할은 정수 분할의 페러스 다이어그램에서 행과 열을 맞바꾸어 얻는 분할이다. 원래 분할과 같은 정수를 분할하지만 각 항의 크기와 항의 개수는 달라질 수 있다. 전치 분할이라고도 한다.
페러스 다이어그램
페러스 다이어그램은 정수 분할의 각 항을 한 행의 점이나 칸의 개수로 나타낸 그림이다. 큰 항부터 위쪽에 놓고 행들을 같은 쪽으로 정렬하여, 분할의 크기와 항의 개수를 기하적으로 읽을 수 있게 한다.
순서 있는 정수 분할
순서 있는 정수 분할은 양의 정수를 양의 정수들의 합으로 나타내면서 항의 순서를 구분하는 표현이다. 영어로 composition이라고 한다. 순서를 무시하는 정수 분할과 달리 2+3과 3+2를 서로 다른 표현으로 센다.
정수 분할
정수 분할은 음이 아닌 정수를 양의 정수들의 합으로 나타내되 더하는 항들의 순서를 구분하지 않는 표현이다. 같은 수가 여러 번 나타날 수 있으며, 보통 큰 항부터 작은 항으로 정렬해 적는다. 0에는 빈 분할 하나가 있다고 정한다.
완전순열
완전순열은 서로 다른 원소들을 재배열하되 어느 원소도 원래 위치에 남지 않는 순열이다. 고정점이 없는 순열이라고도 한다. n개 원소의 완전순열 개수는 보통 Dₙ 또는 !n으로 나타내며, 모든 순열의 수인 n!과 구별한다.
제1종 스털링 수
제1종 스털링 수는 순열을 순환으로 분해했을 때 순환의 개수에 따라 순열을 세는 수다. 부호 없는 값 c(n,k)는 n개 원소의 순열 중 정확히 k개 순환을 가진 것의 개수이며, 부호 있는 값은 s(n,k)=(−1)ⁿ⁻ᵏc(n,k)로 정의한다.
벨 수
벨 수 Bₙ은 서로 다른 n개 원소로 이루어진 집합을 비어 있지 않은 부분집합들로 분할하는 모든 방법의 수다. 블록의 개수는 고정하지 않으며 블록 사이의 순서는 구분하지 않는다. B₀=1에서 시작해 1, 1, 2, 5, 15, 52로 이어진다.
제2종 스털링 수
제2종 스털링 수 S(n,k)는 서로 다른 n개의 원소를 비어 있지 않은 k개의 부분집합으로 분할하는 방법의 수다. 부분집합들 사이에 순서는 부여하지 않으며, 각 원소는 정확히 하나의 부분집합에 속한다.
카탈랑 수
카탈랑 수는 올바른 괄호열이나 볼록 다각형의 삼각분할 등 여러 조합 구조의 개수를 나타내는 수열이다. C₀=1에서 시작하며 일반항은 Cₙ=binom(2n,n)/(n+1)이다. 처음 값은 1, 1, 2, 5, 14, 42로 이어진다.
그레이 코드
그레이 코드는 순서상 이웃한 코드가 한 비트만 다르도록 구성한 이진 코드다. 여러 비트가 동시에 바뀌는 전환을 피하도록 순서를 배치한다. 대표적인 반사형 이진 그레이 코드는 정수 n을 n XOR (n>>1)로 변환해 얻는다.
트립 (자료 구조)
트립은 키에 대해서는 이진 탐색 트리의 순서를, 별도의 우선순위에 대해서는 힙의 순서를 만족하는 자료 구조다. 우선순위를 독립적으로 무작위 배정하는 대표적인 방식에서는 탐색, 삽입, 삭제를 기대 O(log n)에 처리한다.
제곱근 분할
제곱근 분할은 배열 등을 대략 제곱근 크기의 블록으로 나누고 블록별 정보를 미리 저장하여 연산을 줄이는 기법이다. 구간 합의 경우 완전히 포함되는 블록은 저장된 합을 사용하고 양 끝의 일부 원소만 직접 계산한다.
세그먼트 트리
세그먼트 트리는 배열의 구간 정보를 트리 형태로 저장하여 구간 질의와 값 변경을 처리하는 자료 구조다. 대표적인 구현에서는 합이나 최솟값을 결합해 저장하며, 한 원소의 갱신과 구간 질의를 각각 O(log n)에 수행한다.
펜윅 트리
펜윅 트리는 배열의 누적 합과 원소 값의 변화를 효율적으로 관리하는 자료 구조다. 이진 인덱스 트리 또는 BIT라고도 부른다. 대표적인 합 연산 구현에서는 한 원소에 값을 더하는 갱신과 접두 구간의 합을 O(log n)에 처리하며 O(n) 공간을 사용한다.
희소 테이블
희소 테이블은 길이가 2의 거듭제곱인 구간들의 계산 결과를 미리 저장하여 배열의 구간 질의에 답하는 자료 구조다. 값이 바뀌지 않는 배열에서 반복적으로 최솟값이나 최댓값을 묻는 경우에 특히 유용하다.
라빈-카프 알고리즘
라빈-카프 알고리즘은 패턴과 본문의 일정 길이 구간에 대한 해시를 비교하여 일치 후보를 찾는 문자열 검색 알고리즘이다. 구간을 한 칸씩 이동하며 해시를 갱신하는 방식을 이용하며, 정확한 검색에서는 해시가 같은 후보의 실제 문자도 확인한다.
문자열 해싱
문자열 해싱은 문자열을 일정한 범위의 수로 대응시켜 비교나 검색에 활용하는 기법이다. 같은 규칙에서 같은 문자열은 같은 해시를 갖지만, 해시가 같다는 사실만으로 문자열이 반드시 같다고 결론 내릴 수는 없다.
아호-코라식 알고리즘
아호-코라식 알고리즘은 여러 패턴을 하나의 본문에서 함께 찾는 문자열 검색 알고리즘이다. 패턴들의 트라이에 실패 링크와 출력 정보를 더하여, 본문을 왼쪽부터 읽으면서 여러 패턴의 일치 상태를 함께 추적한다.
접미사 배열
접미사 배열은 문자열의 모든 접미사를 사전식 순서로 정렬한 뒤 각 접미사의 시작 위치를 저장한 배열이다. 긴 문자열들을 배열에 복사하는 대신 원래 문자열의 인덱스로 정렬 결과를 나타내며, 문자열 검색과 반복 부분 분석에 사용한다.
마나커 알고리즘
마나커 알고리즘은 문자열의 각 중심에서 만들 수 있는 회문 부분 문자열의 범위를 선형 시간에 구하는 알고리즘이다. 회문을 전부 문자열로 나열하는 대신 중심별 최대 반지름을 저장하여 전체 회문 정보를 압축한다.
Z 함수 (문자열)
문자열의 Z 함수는 각 위치에서 시작하는 부분과 문자열의 맨 앞부분이 연속해서 얼마나 일치하는지 나타낸 배열이다. 이미 확인한 일치 구간을 재사용하면 길이 n인 문자열의 모든 값을 O(n)에 계산할 수 있다.
선분 합집합의 길이
선분 합집합의 길이는 하나의 직선 위에 놓인 여러 선분이 덮는 부분의 전체 길이다. 겹치는 부분은 한 번만 세므로 각 선분의 길이를 단순히 더한 값과 다를 수 있다. 끝점을 정렬해 덮인 구간을 누적하면 O(n log n)에 계산할 수 있다.
반평면 교집합
반평면 교집합은 평면을 직선으로 나눈 한쪽 영역들을 동시에 만족하는 점의 집합이다. 경계를 포함하는 반평면은 ax+by≤c와 같은 일차부등식으로 나타낼 수 있으며, 여러 조건의 공통 해를 기하적으로 구하는 문제로 다룬다.
들로네 삼각분할
들로네 삼각분할은 평면의 점들을 삼각형으로 연결하되 각 삼각형 외접원의 내부에 다른 입력 점이 없도록 만든 삼각분할이다. 원주 위의 다른 점은 허용되므로 빈 원 조건은 원의 내부에 관한 조건이다.
보로노이 다이어그램
보로노이 다이어그램은 주어진 기준점들 중 어느 점이 가장 가까운지에 따라 공간을 나눈 구조다. 평면의 유클리드 거리를 사용하는 경우 각 기준점의 영역은 그 점까지의 거리가 다른 기준점까지의 거리보다 작거나 같은 위치들의 집합으로 나타낼 수 있다.
최소 포함 원
최소 포함 원은 평면의 주어진 점을 모두 내부 또는 경계에 포함하는 원 가운데 반지름이 가장 작은 원이다. 유한한 비어 있지 않은 점 집합에 대해 하나로 결정되며, 모든 입력 점이 원주 위에 있어야 하는 것은 아니다.
민코프스키 합
민코프스키 합은 두 점 집합에서 점을 하나씩 선택해 더하여 만들 수 있는 모든 점의 집합이다. A+B={a+b | a∈A, b∈B}로 나타내며, 평면 도형의 합은 면적을 더하거나 두 도형을 겹쳐 놓는 연산과 다르다.
최근접 점 쌍 문제
최근접 점 쌍 문제는 주어진 점들 중 서로의 거리가 가장 짧은 두 점을 찾는 문제다. 평면의 유클리드 거리를 기준으로 모든 쌍을 비교하면 O(n²)이 걸리지만, 정렬과 분할 정복을 결합하면 O(n log n)에 해결할 수 있다.
모노톤 체인
모노톤 체인은 평면의 점들을 좌표의 사전식 순서로 정렬하고 위쪽과 아래쪽 경계 사슬을 만들어 볼록 껍질을 구하는 알고리즘이다. 앤드루의 알고리즘이라고도 하며 일반적인 비교 정렬을 사용하면 O(n log n) 시간이 걸린다.
볼록 다각형 내부 판정
볼록 다각형 내부 판정은 한 점이 주어진 볼록 다각형의 내부나 경계에 속하는지 결정하는 문제다. 꼭짓점이 경계 순서로 주어지면 한 꼭짓점에서 만든 삼각형 구간을 이진 탐색하여 전처리 뒤 질의마다 O(log n)에 판정할 수 있다.
픽의 정리
픽의 정리는 꼭짓점이 정수 격자점에 놓인 단순다각형의 넓이를 내부 격자점 수와 경계 격자점 수로 구하는 정리다. 내부 점이 I개, 경계 점이 B개이면 넓이는 I + B/2 − 1이다.
신발끈 공식
신발끈 공식은 단순다각형의 꼭짓점 좌표를 경계 순서대로 이용해 넓이를 구하는 공식이다. 이웃한 두 점의 좌표로 만든 행렬식들을 더하고 절댓값의 절반을 취한다. 오목한 단순다각형에도 적용할 수 있다.
선분 교차 판정
선분 교차 판정은 두 선분이 공통점을 갖는지 결정하는 계산이다. 평면에서는 CCW 방향 판정과 좌표 구간의 겹침을 함께 사용해 교점을 직접 계산하지 않고도 판별할 수 있다.
CCW 판정
CCW 판정은 평면의 세 점을 순서대로 보았을 때 반시계 방향으로 꺾이는지, 시계 방향인지, 한 직선에 놓이는지를 결정하는 계산이다. 두 벡터로 만든 2행 2열 행렬식의 부호를 사용하며 볼록 껍질과 선분 교차 알고리즘의 기본 연산이다.
자비스 행진
자비스 행진은 평면 점 집합의 볼록 껍질을 바깥쪽 꼭짓점부터 하나씩 이어 만드는 알고리즘이다. 각 단계에서 전체 점을 살펴 다음 경계점을 고르며 입력점 수 n과 껍질 꼭짓점 수 h에 대해 O(nh) 시간이 걸린다.
그레이엄 스캔
그레이엄 스캔은 평면의 점들을 기준점에 대한 각도 순으로 정렬한 뒤 볼록 껍질의 꼭짓점을 스택으로 추리는 알고리즘이다. 비교 정렬을 사용하는 일반적인 구현은 n개 점에 대해 O(n log n) 시간이 걸린다.
원에 외접하는 사각형
원에 외접하는 사각형은 안쪽의 한 원이 네 변 모두에 접하는 볼록사각형이다. 변 길이를 차례로 a와 b와 c와 d라 하면 a + c = b + d가 성립하고, 넓이는 내접원 반지름과 반둘레의 곱으로 구할 수 있다.
심슨 직선
심슨 직선은 삼각형의 외접원 위의 한 점에서 세 변을 포함하는 직선에 내린 수선의 발들이 놓이는 직선이다. 수선의 발이 원래 변의 바깥 연장선에 생기는 경우도 포함한다.
외접원
외접원은 다각형의 모든 꼭짓점을 지나는 원이다. 한 직선 위에 놓이지 않은 세 점으로 이루어진 삼각형에는 외접원이 하나 존재하며, 그 중심인 외심은 세 변의 수직이등분선이 만나는 점이다.
내접원
내접원은 다각형 안쪽에서 그 다각형의 모든 변에 접하는 원이다. 퇴화하지 않은 삼각형에는 내접원이 하나 존재하며, 중심인 내심은 세 내각 이등분선의 교점이다.
방심
방심은 삼각형의 방접원의 중심이다. 한 꼭짓점의 내각 이등분선과 나머지 두 꼭짓점의 외각 이등분선이 만나는 점으로 얻으며, 삼각형 하나에 서로 다른 방심 세 개가 있다.
방접원
방접원은 삼각형의 한 변과 나머지 두 변의 연장선에 접하면서 삼각형 밖에 놓이는 원이다. 중심은 방심이며 한 삼각형에 세 방접원이 존재한다. 꼭짓점을 지나는 외접원과는 다르다.