Algorithm VisionMaster Algorithms

인접한 요소를 반복적으로 비교하고 순서가 잘못된 경우 교환하는 가장 기본적인 정렬 알고리즘입니다. 거품이 수면으로 떠오르듯이 큰 값이 점차 배열의 끝으로 이동합니다. 작은 데이터셋이나 정렬의 기본 원리를 이해하기 위한 교육 목적에 가장 적합합니다.

가장 작은 요소를 찾아 반복적으로 앞으로 이동시킵니다. 각 반복마다 남은 요소 중에서 최소값을 "선택"하고 정렬된 부분 뒤에 배치합니다. 최소한의 메모리 사용으로 구현이 간단하지만 입력에 관계없이 항상 O(n²) 시간이 걸립니다.

피벗 요소를 선택하고 배열을 왼쪽에는 작은 값, 오른쪽에는 큰 값으로 분할하는 매우 효율적인 정렬 알고리즘입니다. 평균 O(n log n) 시간 복잡도를 가지며 실제로 가장 널리 사용되는 정렬 방법입니다. 대부분의 프로그래밍 언어에서 내장 정렬 함수의 기초를 형성합니다.

먼저 최대 힙을 구축한 다음 루트 요소를 반복적으로 추출하여 정렬하는 이진 힙 데이터 구조를 사용합니다. 추가 메모리 없이 모든 경우에 O(n log n) 시간 복잡도를 보장합니다. 우선순위 큐 구현의 기초로도 사용됩니다.

각 요소의 발생 횟수를 세고 산술 연산을 통해 위치를 결정하는 비비교 정렬 알고리즘입니다. k가 입력 값의 범위일 때 O(n+k) 시간 복잡도를 달성합니다. 알려진 제한된 범위 내의 정수 정렬에 이상적입니다. 기수 정렬의 기초가 됩니다.

최하위 자릿수부터 최상위 자릿수까지 자릿수별로 요소를 처리하는 비비교 정렬 알고리즘입니다. 각 자릿수 위치에서 계수 정렬을 서브루틴으로 사용합니다. d가 자릿수일 때 O(d(n+k)) 시간을 달성합니다. 정수나 고정 길이 문자열 정렬에 탁월합니다.

멀리 떨어진 요소의 교환을 허용하는 삽입 정렬의 최적화입니다. 1로 감소하는 간격 시퀀스를 사용하여 요소를 최종 위치에 더 빠르게 이동시킵니다. 1959년 Donald Shell이 발명한 알고리즘의 이름을 따서 명명되었습니다.

요소를 여러 버킷에 분배하는 분포 기반 정렬 알고리즘입니다. 각 버킷은 다른 정렬 알고리즘을 사용하여 개별적으로 정렬됩니다. 입력이 범위에 걸쳐 균일하게 분포되어 있을 때 가장 잘 작동합니다. 평균 시간 복잡도는 O(n+k)입니다.

배열을 반으로 나누고, 각 절반을 재귀적으로 정렬한 다음, 다시 병합하는 분할 정복 알고리즘입니다. O(n log n) 시간을 보장하고 안정적이지만 추가 메모리가 필요합니다. 큰 데이터셋과 연결 리스트 정렬에 특히 효과적입니다.

손에 있는 카드를 정렬하는 것처럼 작동합니다 - 각 요소를 한 번에 하나씩 적절한 위치에 삽입합니다. 이미 정렬된 데이터에 대해 O(n) 시간에 실행되므로 작은 배열이나 거의 정렬된 데이터셋에 매우 효율적입니다. 간단하면서도 적응형 알고리즘입니다.

1.3 배수로 줄어드는 더 큰 간격으로 요소를 비교하여 배열 끝의 작은 값("거북이")을 제거하는 버블 정렬의 개선입니다. 간단한 수정으로 성능을 O(n²)에서 실제로 O(n²/2^p)로 극적으로 개선합니다. 작은 알고리즘 조정이 어떻게 상당한 개선을 가져올 수 있는지 보여줍니다.

개념적으로 가장 간단한 정렬 알고리즘 - 요소가 순서대로 있을 때는 앞으로 이동하고, 그렇지 않으면 교환하고 뒤로 이동합니다. 꽃병을 정렬하는 네덜란드 정원 놈의 이름을 따서 명명되었습니다. 삽입 정렬과 유사하지만 구현이 더 간단합니다. O(n²) 복잡도에도 불구하고 정렬 메커니즘을 이해하는 데 교육적 가치가 있습니다.

대상을 중간 요소와 비교하고 검색 공간을 반복적으로 반으로 줄이는 매우 효율적인 검색 방법입니다. O(log n) 시간으로 100만 개의 요소에서 단 20번의 비교로 항목을 찾을 수 있습니다. 사전에서 단어를 찾는 것처럼 작동합니다.

처음부터 끝까지 각 요소를 순차적으로 확인하는 가장 기본적인 검색 방법입니다. 정렬되지 않은 데이터나 단순함이 중요한 작은 배열에 사용됩니다. 구현은 간단하지만 O(n) 시간이 필요한 큰 데이터셋에서는 느려집니다.

그래프를 레벨별로 탐색하여 더 깊이 들어가기 전에 현재 깊이의 모든 정점을 방문합니다. 큐를 사용하며 가중치가 없는 그래프에서 최단 경로를 찾는 데 이상적입니다. 미로 해결, 소셜 네트워크 분석, 노드 간 연결 찾기 등의 응용 프로그램이 있습니다.

역추적하기 전에 각 경로를 따라 가능한 한 깊이 들어가서 그래프를 탐색합니다. 스택이나 재귀를 사용하여 구현되어 재귀적 문제에 자연스럽습니다. 경로 찾기, 순환 감지, 위상 정렬, 미로 생성에 사용됩니다.

가중치가 있는 그래프에서 단일 소스 정점에서 다른 모든 정점까지의 최단 경로를 찾습니다. GPS 내비게이션 시스템과 네트워크 라우팅 프로토콜을 지원합니다. 우선순위 큐를 사용하는 탐욕적 접근법으로 음수가 아닌 가중치에 효율적으로 작동합니다.

휴리스틱을 사용하여 최단 경로를 찾는 최선 우선 탐색 알고리즘입니다. f(n) = g(n) + h(n)을 사용하여 다익스트라 알고리즘과 탐욕적 최선 우선 탐색을 결합합니다. 게임, 로봇 공학, GPS 내비게이션의 효율적인 경로 탐색에 널리 사용됩니다.

가중치 무방향 그래프의 최소 신장 트리(MST)를 찾는 알고리즘입니다. 간선을 가중치 순으로 정렬하고 사이클을 형성하지 않는 간선만 추가하는 탐욕적 접근법을 사용합니다. 효율적인 사이클 감지를 위해 Union-Find를 사용합니다. 네트워크 설계와 클러스터링에 필수적입니다.

시작 정점에서 트리를 성장시켜 최소 신장 트리(MST)를 찾는 알고리즘입니다. 항상 트리 내부 정점과 외부 정점을 연결하는 최소 가중치 간선을 추가합니다. 효율적인 간선 선택을 위해 우선순위 큐를 사용합니다. 밀집 그래프에 이상적입니다.

방향 비순환 그래프(DAG)의 정점을 모든 간선 u→v에 대해 u가 v보다 앞에 오도록 정렬합니다. DFS 기반 접근법을 사용합니다. 의존성 해결, 빌드 시스템, 과목 수강 순서 결정에 필수적입니다.

링크 구조로 웹 페이지 순위를 매기는 구글의 알고리즘입니다. 반복적으로 중요도 점수를 계산합니다.

재귀 스택을 사용한 DFS로 방향 그래프의 순환을 감지합니다. 운영 체제의 순환 의존성 식별, 교착 상태 감지, 위상 정렬을 위한 DAG 검증에 중요합니다. 순회 중 정점 상태를 추적하기 위해 3색 표시(흰색-회색-검정색)를 사용합니다.

음수 가중치를 처리하고 음수 순환을 감지하는 단일 소스 최단 경로 알고리즘입니다. 모든 간선을 V-1번 완화하여 음수 가중치에도 정확한 거리를 보장합니다. 통화 차익 거래 감지, 다양한 비용의 네트워크 라우팅, 다익스트라 알고리즘이 실패하는 상황에 필수적입니다. 속도를 유연성과 교환합니다.

동적 프로그래밍을 사용하여 모든 정점 쌍 간의 최단 경로를 찾는 모든 쌍 최단 경로 알고리즘입니다. O(V³) 복잡도로 모든 정점을 중간 지점으로 고려합니다. 밀집 그래프, 추이적 폐쇄 계산, 그래프 지름 찾기에 필수적입니다. 네트워크 분석에서 깊은 응용을 가진 간단한 구현입니다.

Union-Find 자료 구조를 사용하여 간선을 정렬하고 순환을 만들지 않으면 추가하여 MST를 찾는 탐욕 알고리즘입니다. O(E log E) 복잡도로 희소 그래프에 최적입니다. 네트워크 설계(모든 노드를 연결하는 최소 비용), 클러스터링 알고리즘, 회로 설계의 응용이 있습니다. 정렬과 Union-Find의 우아한 통합을 보여줍니다.

MST를 MST가 아닌 정점에 연결하는 최소 가중치 간선을 추가하여 한 번에 한 정점씩 MST를 성장시키는 탐욕 알고리즘입니다. O(E log V) 복잡도를 위해 우선순위 큐를 사용하며 밀집 그래프에 최적입니다. 인접 행렬에 대해 크루스칼보다 구현이 더 간단합니다. 네트워크 설계, 근사 알고리즘, 탐욕적 선택 이해의 응용이 있습니다.

문자열에서 패턴을 효율적으로 찾는 Knuth-Morris-Pratt 알고리즘입니다. 실패 함수(LPS 배열)를 사용하여 불필요한 비교를 건너뛰어 O(n+m) 시간 복잡도를 달성합니다. 텍스트 검색, DNA 서열 분석, 표절 탐지에 필수적입니다.

나쁜 문자와 좋은 접미사 휴리스틱을 사용하는 효율적인 문자열 검색 알고리즘입니다. 패턴을 오른쪽에서 왼쪽으로 비교하여 불일치 시 큰 점프를 허용합니다. 실제로 준선형 시간을 달성하여 가장 빠른 문자열 매칭 알고리즘 중 하나입니다.

행렬 체인의 최적 괄호화를 찾아 스칼라 곱셈 횟수를 최소화합니다. CLRS 15장의 대표적인 동적 프로그래밍 문제입니다.

중복 계산을 피하기 위해 동적 프로그래밍을 사용하여 피보나치 수를 효율적으로 계산합니다. 지수 시간 재귀 솔루션을 선형 시간 알고리즘으로 변환하는 메모이제이션의 힘을 보여줍니다. 동적 프로그래밍 개념에 대한 고전적인 소개입니다.

두 시퀀스에 동일한 순서로 존재하는 가장 긴 부분 수열을 찾습니다. 동적 프로그래밍을 사용하여 솔루션 테이블을 구축합니다. DNA 서열 정렬, 파일 차이 도구(diff), 표절 감지 등의 응용 프로그램이 있습니다.

한 문자열을 다른 문자열로 변환하는 데 필요한 최소 단일 문자 편집(삽입, 삭제, 대체) 횟수를 계산하는 동적 프로그래밍 알고리즘입니다. 맞춤법 검사, DNA 서열 정렬, 자연어 처리의 기본이 됩니다.

주어진 무게와 가치를 가진 아이템을 선택하여 무게 제한 내에서 총 가치를 최대화하는 고전적인 동적 프로그래밍 문제입니다. 각 아이템은 한 번만 선택할 수 있습니다(0/1). 자원 할당, 포트폴리오 최적화, 화물 적재 등의 응용이 있습니다.

모든 요소가 증가하는 순서인 가장 긴 부분 수열을 찾습니다. 대표적인 동적 프로그래밍 문제입니다.

O(n) 시간에 최대 합을 가진 연속 부분 배열을 찾는 우아한 동적 프로그래밍 알고리즘입니다. 각 단계에서 현재 부분 배열을 확장할지 새로 시작할지를 결정하여 탐욕적 원리와 DP를 결합합니다. 주식 수익 최적화, 신호 처리, DP 최적화 기법 이해에 필수적입니다.

목표 금액을 만드는 데 필요한 최소 동전 개수를 찾는 고전적인 DP 문제입니다. 더 작은 금액으로부터 솔루션을 구축하여 최적 부분 구조를 보여줍니다. 화폐 시스템, 자동 판매기, 자원 할당의 실용적 응용이 있습니다. 변형으로는 거스름돈을 만드는 모든 가능한 방법의 수를 세는 것이 있습니다.

2D 동적 프로그래밍을 사용하여 문자열을 회문으로 분할하는 데 필요한 최소 컷을 찾습니다. 먼저 O(n²)로 회문 테이블을 구축한 다음 최소 컷을 계산합니다. 텍스트 처리, 문자열 최적화, 여러 단계가 있는 복잡한 DP 시연의 응용이 있습니다. 문자열 조작 문제에서 최적 부분 구조를 보여줍니다.

N×N 체스판에 N개의 퀸을 서로 공격하지 않도록 배치합니다. 대표적인 백트래킹 알고리즘입니다.

합성수를 반복적으로 제거하여 n까지의 모든 소수를 찾습니다. 에라토스테네스 (기원전 276-194년)의 이름을 따서 명명되었습니다.

각 숫자가 바로 위의 두 숫자의 합인 이항 계수의 삼각형 배열입니다. 블레즈 파스칼(1623-1662)의 이름을 따서 명명되었으며, 수세기 전부터 수학자들에게 알려져 있었습니다. 이항 전개, 조합론, 피보나치 수와의 연결을 포함한 아름다운 수학적 패턴을 보여줍니다.

기원전 300년경부터 사용된 반복적인 나눗셈을 통해 두 수의 최대공약수를 계산하는 고대 알고리즘입니다. 여전히 널리 사용되는 가장 오래된 알고리즘 중 하나로 수학적 우아함과 효율성을 보여줍니다. 암호학, 분수 단순화, 수론 응용의 기초입니다.

유클리드 GCD를 확장하여 ax + by = gcd(a,b)를 만족하는 베주 계수 x와 y를 찾습니다. RSA 암호학의 모듈러 곱셈 역원 계산, 선형 디오판토스 방정식 해결, 중국인의 나머지 정리에 중요합니다. 고전 알고리즘이 어떻게 현대 계산 문제를 해결하도록 확장되는지 보여줍니다.

데이터를 k개의 클러스터로 분할하는 기본적인 비지도 머신러닝 알고리즘입니다. 점을 가장 가까운 중심에 할당하고 중심 위치를 반복적으로 업데이트합니다. 고객 세분화, 이미지 압축, 탐색적 데이터 분석에 널리 사용됩니다.

각 노드가 문자를 나타내는 효율적인 문자열 저장 및 검색을 위한 트리 데이터 구조입니다. 문자열 길이 m에 대해 O(m) 삽입/검색 연산을 가능하게 합니다. 자동 완성 시스템, 맞춤법 검사기, IP 라우팅(최장 접두사 매칭), 사전 구현에 필수적입니다. 공통 접두사가 있는 큰 문자열 집합에 메모리 효율적입니다.

재귀적 접근 방식을 사용하여 이진 트리에서 두 노드의 최소 공통 조상을 찾습니다. LCA는 두 노드를 모두 자손으로 갖는 가장 깊은 노드입니다. 계층적 데이터(관계 찾기), 노드 간 거리 계산, 버전 관리 시스템(병합 베이스)의 응용이 있습니다. 더 고급 트리 쿼리의 기초입니다.

1962년 Adelson-Velsky와 Landis가 발명한 최초의 자가 균형 이진 검색 트리입니다. 서브트리의 높이 차이를 최대 1로 유지하여 O(log n) 연산을 보장합니다. 삽입/삭제 후 재균형을 위해 네 가지 유형의 회전(LL, RR, LR, RL)을 수행합니다. 데이터베이스, 파일 시스템, 보장된 로그 연산이 중요한 곳에 사용됩니다.

겹치지 않는 최대 활동 수를 선택합니다. 항상 가장 빨리 끝나는 활동을 선택하는 대표적인 그리디 알고리즘입니다.