문서 둘러보기
상태 기계 복제
상태 기계 복제는 여러 복제본이 같은 초기 상태에서 같은 명령들을 같은 순서로 처리하게 하여 같은 상태와 결과를 유지하는 분산 시스템 구성 방식이다. 명령 처리의 결정성과 입력 순서의 일치가 핵심 조건이다.
FLP 불가능성 정리
FLP 불가능성 정리는 완전 비동기 분산 시스템에서 하나의 프로세스 중단 가능성만 있어도 결정적 합의 알고리즘의 모든 허용 실행에 대한 종료를 보장할 수 없다는 결과다. 합의가 언제나 실패한다는 뜻이 아니라 종료하지 않는 허용 실행이 존재한다는 뜻이다.
CAP 정리
CAP 정리는 통신 분할이 가능한 분산 읽기와 쓰기 서비스에서 선형화 가능한 일관성과 모든 정상 노드 요청에 대한 응답을 함께 보장할 수 없다는 한계를 다룬다. 세 기능 중 아무 두 개를 평상시에 골라 쓰라는 단순한 분류표와는 다르다.
비잔틴 장군 문제
비잔틴 장군 문제는 일부 참여자가 서로 모순되는 정보를 보내는 상황에서도 정상 참여자들이 같은 결정에 도달하게 할 수 있는지를 다루는 분산 합의 문제다. 단순히 멈춘 서버를 견디는 문제보다 강한 장애를 고려한다.
벡터 시계
벡터 시계는 프로세스별 논리 계수를 함께 유지하여 분산 사건의 인과적 선후 관계를 표현하는 방식이다. 적절히 갱신된 벡터들을 성분별로 비교하면 선후 관계와 서로 인과적으로 비교되지 않는 사건을 구분할 수 있다.
일관 해싱
일관 해싱은 항목을 서버나 버킷에 배정할 때 대상 집합의 작은 변화가 전체 항목의 대규모 재배정으로 번지지 않도록 하는 해싱 방식이다. 서버가 추가되거나 빠지는 분산 캐시 등의 환경에서 배치 변화의 범위를 줄이는 데 활용한다.
Paxos
Paxos는 분산된 참여자들이 제안된 값에 합의하도록 하는 알고리즘 계열이다. 기본적인 단일 값 합의에서는 서로 다른 값이 동시에 최종 선택되지 않게 하며, 이를 반복해 명령열에 합의하는 시스템을 구성할 수 있다.
Raft
Raft는 여러 서버가 같은 명령 로그에 합의하도록 하는 분산 합의 알고리즘이다. 리더 선출, 로그 복제와 안전성 규칙을 나누어 설명하며, 일부 서버가 중단되어도 과반수와 통신할 수 있는 조건에서 진행할 수 있다.
람포트 시계
람포트 시계는 분산 시스템의 사건에 논리적 번호를 붙여 인과적 선후 관계와 모순되지 않는 순서를 만드는 방식이다. 실제 시각이나 경과 시간을 측정하는 시계가 아니라 프로세스의 사건과 메시지 전달 순서를 표현한다.
CRDT
CRDT는 여러 복제본이 독립적으로 갱신되더라도 정해진 전달 조건과 연산 규칙 아래 같은 상태로 수렴하도록 설계한 복제 자료형이다. 동시 갱신을 나중에 임의로 조정하기보다 병합과 갱신의 성질에 수렴 조건을 담는다.
티 다이제스트
티 다이제스트는 수치 데이터의 분위수와 분포상 위치를 작은 요약으로 추정하는 자료구조다. 계속 들어오는 관측값을 전부 보관하고 정렬하는 대신 요약을 갱신하여 중앙값이나 높은 백분위수 등을 근사한다.
쿠쿠 필터
쿠쿠 필터는 항목의 짧은 지문을 해시 기반 버킷에 저장하여 집합 포함 여부를 근사 검사하는 자료구조다. 블룸 필터처럼 잘못된 양성 결과가 가능하며, 삽입했던 항목을 삭제하는 기능도 지원할 수 있다.
하이퍼로그로그
하이퍼로그로그는 데이터에 등장한 서로 다른 항목의 수를 작은 요약 정보로 추정하는 확률적 자료구조다. 중복을 제거한 개수를 근사하며, 전체 항목 목록을 보관하는 정확한 집합과는 저장 내용과 기능이 다르다.
스킵 리스트
스킵 리스트는 정렬된 연결 리스트에 여러 높이의 전방 연결을 두어 탐색을 빠르게 하는 자료구조다. 노드 높이를 무작위로 선택하는 표준 방식에서는 탐색, 삽입, 삭제의 기대 시간 복잡도가 O(log n)이다.
블룸 필터
블룸 필터는 항목이 집합에 들어 있는지를 작은 공간으로 검사하는 확률적 자료구조다. 정상적으로 항목을 추가하고 유지한 기본 필터는 없는 항목을 있다고 답할 수 있지만, 추가된 항목을 없다고 답하지는 않는다.
카운트 민 스케치
카운트 민 스케치는 여러 해시 함수와 작은 계수 배열로 항목의 등장 횟수를 근사하는 자료구조다. 모든 항목의 정확한 빈도표를 보관하기 어려운 데이터 스트림에서 메모리 사용량과 추정 오차를 조절하는 데 쓰인다.
파울리 Z 게이트
파울리 Z 게이트는 |0⟩를 그대로 두고 |1⟩의 진폭 부호를 바꾸는 한 큐비트 양자 게이트다. α|0⟩+β|1⟩를 α|0⟩−β|1⟩로 보내며 두 성분 사이의 상대 위상을 π만큼 바꾼다.
아다마르 게이트
아다마르 게이트 H는 한 큐비트의 계산 기저 상태를 |+⟩와 |−⟩ 상태로 바꾸는 양자 게이트다. H|0⟩=(|0⟩+|1⟩)/√2, H|1⟩=(|0⟩−|1⟩)/√2이며 두 번 적용하면 원래 상태로 돌아온다.
파울리 X 게이트
파울리 X 게이트는 한 큐비트의 |0⟩와 |1⟩를 서로 바꾸는 양자 게이트다. α|0⟩+β|1⟩를 β|0⟩+α|1⟩로 보내며 계산 기저에서는 고전적인 NOT과 같은 비트 반전 규칙을 갖는다.
양자 회로
양자 회로는 큐비트에 적용하는 게이트와 측정을 순서대로 나타내는 계산 모형이자 도식이다. 선은 큐비트를, 기호는 연산을 나타내며 보통 왼쪽에서 오른쪽으로 시간 순서를 읽는다.
초밀집 부호화
초밀집 부호화는 미리 공유한 얽힘 한 쌍을 이용해 큐비트 하나를 전송하여 고전 비트 두 개를 전달하는 프로토콜이다. 수신자는 자신의 큐비트와 전달받은 큐비트를 함께 측정해 네 메시지를 구별한다.
CNOT 게이트
CNOT 게이트는 제어 큐비트가 |1⟩일 때 표적 큐비트에 NOT 연산을 적용하는 두 큐비트 양자 게이트다. 계산 기저에서는 |c,t⟩를 |c,t⊕c⟩로 보내며 중첩 상태에는 이 규칙을 선형적으로 적용한다.
양자 순간이동
양자 순간이동은 미리 공유한 얽힘과 고전 통신을 사용해 한 계의 미지 양자상태를 다른 계에 재현하는 프로토콜이다. 물질 자체를 순간적으로 옮기거나 빛보다 빠르게 메시지를 전하는 기술은 아니다.
양자 네트워크
양자 네트워크는 양자상태를 전송하거나 공유하여 양자 장치들을 연결하는 네트워크다. 광자에 정보를 부호화하고 얽힘 같은 양자 자원을 이용하며, 고전 통신망과 함께 동작하도록 설계된다.
큐비트
큐비트는 두 차원 양자계로 표현하는 양자정보의 기본 단위다. 순수상태는 |ψ⟩=α|0⟩+β|1⟩로 쓰며 복소수 진폭은 |α|²+|β|²=1을 만족한다. 계산 기저로 측정하면 결과는 0 또는 1이다.
그레이 코드
그레이 코드는 순서상 이웃한 코드가 한 비트만 다르도록 구성한 이진 코드다. 여러 비트가 동시에 바뀌는 전환을 피하도록 순서를 배치한다. 대표적인 반사형 이진 그레이 코드는 정수 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와 같은 일차부등식으로 나타낼 수 있으며, 여러 조건의 공통 해를 기하적으로 구하는 문제로 다룬다.
들로네 삼각분할
들로네 삼각분할은 평면의 점들을 삼각형으로 연결하되 각 삼각형 외접원의 내부에 다른 입력 점이 없도록 만든 삼각분할이다. 원주 위의 다른 점은 허용되므로 빈 원 조건은 원의 내부에 관한 조건이다.
보로노이 다이어그램
보로노이 다이어그램은 주어진 기준점들 중 어느 점이 가장 가까운지에 따라 공간을 나눈 구조다. 평면의 유클리드 거리를 사용하는 경우 각 기준점의 영역은 그 점까지의 거리가 다른 기준점까지의 거리보다 작거나 같은 위치들의 집합으로 나타낼 수 있다.
최소 포함 원
최소 포함 원은 평면의 주어진 점을 모두 내부 또는 경계에 포함하는 원 가운데 반지름이 가장 작은 원이다. 유한한 비어 있지 않은 점 집합에 대해 하나로 결정되며, 모든 입력 점이 원주 위에 있어야 하는 것은 아니다.
최근접 점 쌍 문제
최근접 점 쌍 문제는 주어진 점들 중 서로의 거리가 가장 짧은 두 점을 찾는 문제다. 평면의 유클리드 거리를 기준으로 모든 쌍을 비교하면 O(n²)이 걸리지만, 정렬과 분할 정복을 결합하면 O(n log n)에 해결할 수 있다.
모노톤 체인
모노톤 체인은 평면의 점들을 좌표의 사전식 순서로 정렬하고 위쪽과 아래쪽 경계 사슬을 만들어 볼록 껍질을 구하는 알고리즘이다. 앤드루의 알고리즘이라고도 하며 일반적인 비교 정렬을 사용하면 O(n log n) 시간이 걸린다.
볼록 다각형 내부 판정
볼록 다각형 내부 판정은 한 점이 주어진 볼록 다각형의 내부나 경계에 속하는지 결정하는 문제다. 꼭짓점이 경계 순서로 주어지면 한 꼭짓점에서 만든 삼각형 구간을 이진 탐색하여 전처리 뒤 질의마다 O(log n)에 판정할 수 있다.
신발끈 공식
신발끈 공식은 단순다각형의 꼭짓점 좌표를 경계 순서대로 이용해 넓이를 구하는 공식이다. 이웃한 두 점의 좌표로 만든 행렬식들을 더하고 절댓값의 절반을 취한다. 오목한 단순다각형에도 적용할 수 있다.
선분 교차 판정
선분 교차 판정은 두 선분이 공통점을 갖는지 결정하는 계산이다. 평면에서는 CCW 방향 판정과 좌표 구간의 겹침을 함께 사용해 교점을 직접 계산하지 않고도 판별할 수 있다.
CCW 판정
CCW 판정은 평면의 세 점을 순서대로 보았을 때 반시계 방향으로 꺾이는지, 시계 방향인지, 한 직선에 놓이는지를 결정하는 계산이다. 두 벡터로 만든 2행 2열 행렬식의 부호를 사용하며 볼록 껍질과 선분 교차 알고리즘의 기본 연산이다.
자비스 행진
자비스 행진은 평면 점 집합의 볼록 껍질을 바깥쪽 꼭짓점부터 하나씩 이어 만드는 알고리즘이다. 각 단계에서 전체 점을 살펴 다음 경계점을 고르며 입력점 수 n과 껍질 꼭짓점 수 h에 대해 O(nh) 시간이 걸린다.
그레이엄 스캔
그레이엄 스캔은 평면의 점들을 기준점에 대한 각도 순으로 정렬한 뒤 볼록 껍질의 꼭짓점을 스택으로 추리는 알고리즘이다. 비교 정렬을 사용하는 일반적인 구현은 n개 점에 대해 O(n log n) 시간이 걸린다.
풍동
풍동은 시험부에 공기 흐름을 만들어 모형이나 물체의 공기역학적 특성을 측정하는 장치다. 물체를 고정하고 공기를 흘려 상대 운동을 재현하며 힘, 모멘트, 압력 등의 자료를 얻는다.
정규 언어
정규 언어는 유한 오토마타가 정확히 인식할 수 있는 형식 언어다. 여기서 언어는 일정한 알파벳 위의 문자열 집합을 뜻하며 자연언어의 문법적 올바름과는 다른 개념이다.
튜링 기계
튜링 기계는 유한한 제어 상태, 기호를 읽고 쓰는 헤드, 제한 없이 확장할 수 있는 테이프로 계산을 나타내는 모형이다. 현재 상태와 읽은 기호에 따라 쓰기와 이동, 상태 변경을 수행한다.
결정적 유한 오토마타
결정적 유한 오토마타는 현재 상태와 입력 기호가 주어졌을 때 다음 상태가 하나로 정해지는 유한 상태 문자열 인식기다. 보통 모든 상태와 입력 기호 쌍에 전이를 정하는 완전한 형태로 정의한다.
비결정적 유한 오토마타
비결정적 유한 오토마타는 같은 상태와 입력 기호에서 여러 다음 상태를 허용할 수 있는 유한 상태 문자열 인식기다. 전체 입력을 처리하여 수용 상태에 도달하는 경로가 하나라도 있으면 문자열을 수용한다.
유한 상태 기계
유한 상태 기계는 유한한 상태들과 입력에 따른 상태 전이로 동작을 나타내는 계산 모형이다. 현재 상태에 필요한 정보를 요약하고 새 입력을 읽을 때 정한 규칙에 따라 다음 상태로 옮겨 간다.
부분 문자열
부분 문자열은 원래 문자열에서 연속한 구간을 취해 얻는 문자열이다. 중간 문자를 건너뛰어 고르는 부분 수열과 구별하며 접두부와 접미부도 부분 문자열의 특수한 경우다.
접두부 (문자열)
문자열의 접두부는 맨 앞에서 시작하는 연속한 부분이다. 문자열 전체와 빈 문자열도 접두부에 포함하며 전체보다 짧은 접두부는 진접두부라고 구별한다.
접미부 (문자열)
문자열의 접미부는 맨 끝까지 이어지는 연속한 부분이다. 문자열 전체와 빈 문자열도 포함하며 전체보다 짧은 접미부를 진접미부라고 한다.
레벤슈타인 거리
레벤슈타인 거리는 한 문자열을 다른 문자열로 바꾸는 데 필요한 문자 삽입, 삭제, 치환의 최소 횟수다. 각 연산 비용을 1로 두는 기본 형태에서 두 문자열의 차이를 수치로 나타낸다.
해밍 거리
해밍 거리는 길이가 같은 두 문자열에서 같은 위치의 값이 다른 자리 수다. 이진 문자열에서는 두 비트열을 같게 만들기 위해 바꾸어야 하는 비트 수로 해석한다.
최장 공통 부분 문자열
최장 공통 부분 문자열은 여러 문자열 안에 연속해서 나타나는 공통 구간 중 길이가 가장 긴 것이다. 중간 문자를 건너뛸 수 있는 최장 공통 부분 수열과 구별한다.
최장 공통 부분 수열
최장 공통 부분 수열은 여러 문자열에서 순서를 유지하며 뽑아낼 수 있는 공통 문자 나열 중 길이가 가장 긴 것이다. 문자들이 원문에서 연속해 있을 필요는 없다.
KMP 알고리즘
KMP 알고리즘은 패턴의 반복 구조를 미리 분석하여 텍스트에서 패턴을 찾는 문자열 검색 알고리즘이다. 비교에 실패해도 이미 일치한 부분의 정보를 활용해 불필요한 재검사를 줄인다.
문자열
문자열은 문자를 순서 있게 나열한 데이터다. 같은 문자들을 포함하더라도 순서가 다르면 다른 문자열이며 길이가 0인 빈 문자열도 다룬다.
문자열 검색
문자열 검색은 텍스트 안에서 주어진 패턴 문자열이 나타나는 위치를 찾는 문제다. 패턴이 연속해서 정확히 일치하는 검색과 오차를 허용하는 검색을 구별한다.
최악의 경우 분석
최악의 경우 분석은 같은 크기의 입력들 중 알고리즘의 자원 사용량이 가장 큰 경우를 기준으로 비용을 평가하는 방법이다. 실행 시간뿐 아니라 메모리나 비교 횟수에도 적용할 수 있다.
평균의 경우 분석
평균의 경우 분석은 입력의 확률 분포를 정하고 그 분포에 대한 알고리즘 비용의 기댓값을 구하는 방법이다. 무엇을 얼마나 자주 입력한다고 가정하는지가 결과의 일부다.
제자리 정렬
제자리 정렬은 원래 원소가 저장된 공간을 재사용하여 정렬하는 방식이다. 전체 원소를 담는 별도의 결과 배열을 두는 방식과 구별하며, 추가 공간의 허용 범위는 사용하는 정의와 구현에 따라 확인해야 한다.
빅오 표기법
빅오 표기법 O(g(n))은 함수의 증가율에 대한 점근적 상한을 나타낸다. 알고리즘 분석에서는 입력이 충분히 커졌을 때 비용이 g(n)의 일정한 상수배를 넘지 않는다는 뜻으로 사용한다.
세타 표기법
세타 표기법 Θ(g(n))은 함수가 충분히 큰 입력에서 g(n)의 양의 상수배 사이에 놓인다는 뜻이다. 점근적 상한과 하한을 함께 주므로 증가율을 같은 차수로 묶는다.
공간 복잡도
공간 복잡도는 입력 크기에 따라 알고리즘이 필요로 하는 메모리 공간이 어떻게 증가하는지 나타내는 척도다. 입력 자체를 포함하는 전체 공간과 계산 중 추가로 쓰는 보조 공간을 구별해야 한다.
시간 복잡도
시간 복잡도는 입력 크기에 따라 알고리즘의 계산 비용이 어떻게 증가하는지 나타내는 척도다. 실제 경과 시간을 초로 한 번 측정한 값과 구별하며 비교 횟수 등 정한 계산 모형의 연산 수로 분석한다.
계수 정렬
계수 정렬은 각 키가 나타나는 횟수를 세고 그 정보를 이용해 원소를 배치하는 정렬 알고리즘이다. 정수 키의 범위가 원소 수에 비해 작을 때 유용하다.
기수 정렬
기수 정렬은 키를 자리나 부분 단위로 나누어 여러 번 배치하는 정렬 알고리즘이다. 낮은 자리부터 처리하는 방식에서는 매 단계 같은 자리값을 가진 원소의 상대 순서를 유지해야 한다.
안정 정렬
안정 정렬은 정렬 키가 같은 원소들의 입력 순서를 결과에서도 유지하는 정렬이다. 정렬 결과의 대소 관계가 맞는지와 같은 키의 상대 순서를 보존하는지는 별개의 성질이다.
버블 정렬
버블 정렬은 이웃한 두 원소를 비교해 순서가 잘못되었으면 교환하는 과정을 반복하는 정렬 알고리즘이다. 오름차순에서는 한 번의 순회로 큰 값이 뒤쪽으로 이동한다.
힙 정렬
힙 정렬은 힙 자료 구조로 최댓값이나 최솟값을 반복해서 선택하여 원소를 정렬하는 비교 기반 알고리즘이다. 배열 안에 최대 힙을 만들고 가장 큰 원소를 뒤쪽부터 확정하는 방식이 대표적이다.
백트래킹
백트래킹은 후보 해를 단계적으로 만들며 선택지를 탐색하고, 조건을 만족할 수 없는 경로에서는 이전 선택으로 돌아가는 탐색 기법이다. 해 하나를 찾거나 가능한 모든 해를 구하는 데 사용할 수 있다.
탐욕 알고리즘
탐욕 알고리즘은 단계마다 그 시점의 기준에서 가장 유리한 선택을 하며 해를 구성하는 방법이다. 그리디 알고리즘이라고도 하며 각 단계의 좋은 선택이 전체 최적해로 이어지는지는 문제별로 증명해야 한다.
메모이제이션
메모이제이션은 함수의 입력과 계산 결과를 저장해 두었다가 같은 입력이 다시 들어오면 저장한 결과를 사용하는 기법이다. 반복되는 부분 문제의 중복 계산을 줄이는 데 쓰인다.
분할 정복
분할 정복은 문제를 더 작은 부분 문제로 나누어 각각 해결한 뒤 그 결과를 결합하는 알고리즘 설계 방식이다. 부분 문제에도 같은 구조를 적용하는 재귀적 형태가 흔하다.
이진 거듭제곱
이진 거듭제곱은 지수의 이진 표현을 이용해 제곱을 반복하고 필요한 값만 곱하여 거듭제곱을 계산하는 방법이다. 지수가 커져도 곱셈 횟수를 지수의 자릿수에 비례하도록 줄일 수 있다.
에라토스테네스의 체
에라토스테네스의 체는 정해진 범위의 소수들을 한꺼번에 찾는 알고리즘이다. 작은 소수의 배수들을 차례로 제외하여 남은 수를 소수로 판별한다.
확장 유클리드 알고리즘
확장 유클리드 알고리즘은 두 정수의 최대공약수와 함께 그 최대공약수를 원래 두 수의 정수 계수 합으로 나타내는 계수를 구하는 방법이다.
인접 리스트
인접 리스트는 그래프의 각 정점에 연결된 이웃이나 간선을 따로 모아 저장하는 표현 방식이다. 기본적인 저장 공간은 정점 수 V와 간선 수 E에 대해 O(V+E)이다.
인접 행렬
인접 행렬은 그래프의 정점 쌍 사이의 연결을 행렬의 원소로 나타낸 것이다. 정점이 V개이면 기본 표현은 V×V 행렬이며 간선의 존재나 가중치 등을 저장할 수 있다.
동적 배열
동적 배열은 원소 수의 변화에 맞춰 내부 저장 공간을 다시 확보할 수 있는 배열 기반 자료 구조이다. 실제 원소 수와 확보된 용량을 구별하며 필요할 때 더 큰 배열로 옮기는 방식 등이 쓰인다.
분할 상환 분석
분할 상환 분석은 연산 하나의 최악 비용만 따로 보는 대신 연속된 연산 전체의 비용을 분석하여 연산당 비용의 한계를 구하는 방법이다. 입력의 확률 분포를 가정하는 평균 경우 분석과는 다르다.
경로 압축
경로 압축은 서로소 집합 자료 구조에서 대표를 찾는 동안 지나간 원소들의 부모를 루트 쪽으로 바꾸어 이후 탐색을 짧게 하는 기법이다. 집합의 구성원은 그대로 두고 내부 트리의 모양을 바꾼다.
서로소 집합 자료 구조
서로소 집합 자료 구조는 원소들을 겹치지 않는 여러 집합으로 나누어 관리하고 집합의 합치기와 소속 확인을 지원하는 자료 구조이다. 주요 연산 이름을 따라 유니온 파인드라고도 부른다.
비순환 유향 그래프
비순환 유향 그래프는 방향을 따라 이동해서 처음 정점으로 돌아오는 순환이 없는 유향 그래프이다. 영어 약칭 DAG로 부르며 선후 관계나 의존 관계를 표현하는 데 쓰인다.
위상 정렬
위상 정렬은 유향 그래프의 모든 정점을 각 간선의 출발점이 도착점보다 앞서도록 일렬로 나열하는 것이다. 유한 그래프에서는 유향 순환이 없을 때에만 가능하다.
벨만-포드 알고리즘
벨만-포드 알고리즘은 간선을 반복해서 완화하여 한 출발점에서의 최단 거리를 구하는 알고리즘이다. 음수 간선을 허용하며 출발점에서 도달 가능한 음수 순환을 검출할 수 있다.
플로이드-워셜 알고리즘
플로이드-워셜 알고리즘은 중간에 거칠 수 있는 정점을 하나씩 늘려 모든 정점 쌍의 최단 거리를 구하는 동적 계획법 알고리즘이다. 정점 수가 V일 때 기본 시간 복잡도는 O(V³)이다.
다익스트라 알고리즘
다익스트라 알고리즘은 간선 가중치가 음수가 아닌 그래프에서 한 출발점으로부터의 최단 거리를 구하는 알고리즘이다. 아직 확정하지 않은 정점 중 거리 후보가 가장 작은 정점을 반복해서 선택한다.
크루스칼 알고리즘
크루스칼 알고리즘은 가중 무향 그래프의 간선을 가벼운 순서로 살피며 순환을 만들지 않는 간선을 선택하는 최소 신장 트리 알고리즘이다. 분리된 트리들을 합쳐 가는 방식으로 동작한다.
프림 알고리즘
프림 알고리즘은 가중 무향 그래프의 최소 신장 트리를 구하는 탐욕 알고리즘이다. 한 정점에서 시작해 현재 트리와 바깥 정점을 잇는 가장 가벼운 간선을 반복해서 선택한다.
Codex 사용량
Codex와 ChatGPT Work에서 작업에 따라 소모되는 요금제 포함 사용량이다. 고정된 질문 횟수와 같지 않으며 API 과금과 구별된다.
The X Subscription
Grok과 Cursor, X의 유료 기능을 연결하는 통합 구독 체계다. 기존 별도 구독의 유지와 통합 구독 전환은 구별된다.