알고리즘

공간 복잡도는 입력 증가에 따른 최대 저장 공간을 분석한다. 입력·출력·보조 공간, 복사와 참조, 재귀·제너레이터·캐시를 구분하고 LCS·배낭의 공간 압축과 실제 메모리 측정을 검증 예제로 설명한다. 공간 복잡도(space complexity)는 입력 크기가 늘 때 알고리즘이 사용하는 저장 공간이 어떻게 증가하는지 분석하는 개념이다. 특정 컴퓨터에서 몇 MB를 썼는지 측정하는 것과 관련은 있지만 같은 수치는 아니다. 입력·출력

이분 탐색은 단조적인 비교·판정 결과를 이용해 후보 구간을 줄이며 경계를 찾는 알고리즘이다. 이 문서는 lower·upper bound, 중복과 범위 조회, 최소 용량과 정수 제곱근 응용, 정확성·종료 증명과 실제 대조 검사를 설명한다. 이분 탐색(binary search), 또는 이진 탐색은 비교나 판정 결과를 이용해 후보 구간의 한쪽을 버리며 답을 찾는 방법이다. 정렬된 배열의 값 검색이 대표적이지만, 더 일반적으로는 거짓

시간 복잡도는 입력 크기에 따른 알고리즘 작업량의 증가를 분석한다. 이 문서는 O·Ω·Θ, 최선·최악·기댓값·분할 상환 분석을 구분하고, 반복문·재귀·복사·해시·전처리 비용을 실제 연산 횟수 예제로 계산한다. 시간 복잡도는 입력 크기에 따라 알고리즘의 작업량이 어떻게 증가하는지 표현하는 개념이다. “이 함수는 0.2초 걸린다”는 특정 실행의 측정과 다르다. 같은 알고리즘도 컴퓨터, 언어, 입력 내용에 따라 실제 시간이 달라지므

알고리즘은 문제의 입력을 올바른 출력으로 바꾸는 계산 절차다. 이 문서는 탐색·정렬·완전 탐색·탐욕법·동적 계획법·그래프를 실제 예제로 설명하고, 정확성의 근거와 시간·공간 비용, 전제 위반과 검증 방법을 함께 다룬다. 알고리즘은 주어진 문제를 해결하기 위해 수행하는 명확한 절차다. 프로그램이 특정 언어와 실행 환경에서 동작하는 구현이라면, 알고리즘은 그 구현이 따라야 하는 계산의 방법에 초점을 둔다. 같은 탐색 절차를 Pyt

위상 정렬은 방향 비순환 그래프에서 모든 간선 u→v에 대해 u가 v보다 앞서도록 정점을 나열하는 것이다. 진입 차수가 0인 정점을 반복 제거하거나 DFS 종료 순서를 이용한다. 가능한 순서는 하나가 아닐 수 있다. 작업 B가 A의 결과를 필요로 하면 A→B로 표현한다. 위상 순서에 따라 실행 계획을 세우면 선행 작업이 뒤에 놓이지 않는다. 방향 사이클이 있으면 위상 정렬은 불가능하다. 결과가 모든 정점을 포함했는지 확인해야

강한 연결 요소는 방향 그래프에서 서로 왕복 도달 가능한 정점들의 최대 집합이다. 두 정점이 같은 요소에 속하려면 양방향 도달성이 필요하다. 각 요소를 하나의 정점으로 압축하면 요소 사이의 그래프는 방향 비순환 그래프가 된다. A→B→C→A가 있고 C→D만 있다면 A, B, C는 한 요소가 되지만 D는 별도 요소다. D에서 돌아오는 경로가 없기 때문이다. 단순히 간선이 이어져 있다는 약한 연결성과 구별한다. 코사라주와 타잔 알

프림 알고리즘은 현재 만든 트리와 바깥 정점을 잇는 가장 가벼운 간선을 반복 선택하는 최소 신장 트리 알고리즘이다. 하나의 시작 정점에서 트리를 확장한다. 바깥 정점마다 트리에 연결하는 최소 간선 비용을 관리하고 우선순위 큐로 선택할 수 있다. A에서 시작했다면 A에서 나가는 가장 가벼운 간선을 고르고, 다음에는 이미 포함된 정점 전체에서 바깥으로 나가는 간선을 비교한다. 다익스트라의 키는 시작점부터의 누적 거리지만 프림의 키

크루스칼 알고리즘은 간선을 가중치순으로 살피며 사이클을 만들지 않는 간선을 선택하는 최소 신장 트리 알고리즘이다. 서로 다른 연결 요소를 잇는 간선만 채택한다. 서로소 집합 자료구조로 두 정점이 이미 연결되었는지 검사할 수 있다. 가중치 1, 2, 5인 삼각형에서는 1과 2를 선택하면 모든 정점이 연결되므로 5인 간선은 제외한다. 간선 정렬 비용이 대체로 O(E log E)을 차지한다. 입력이 연결되지 않은 경우 선택 간선 수

최소 신장 트리는 연결된 무방향 가중 그래프의 모든 정점을 연결하면서 간선 가중치 합을 최소로 하는 트리이다. V개 정점을 연결하는 신장 트리는 V−1개 간선을 가진다. 크루스칼과 프림 알고리즘이 대표적인 구성 방법이다. 여러 건물을 연결하는 케이블 총길이를 줄이는 모형에 쓸 수 있다. 한 건물에서 각 건물까지의 이동 거리를 모두 최소화하는 문제와는 다르다. 그래프가 연결되지 않았다면 전체 신장 트리는 없고 각 연결 요소의 최

플로이드 워셜 알고리즘은 모든 정점 쌍 사이의 최단 거리를 동적 계획법으로 계산하는 알고리즘이다. 중간 정점으로 k를 허용할 때 d[i][j]와 d[i][k]+d[k][j] 중 작은 값을 선택한다. 전형적인 구현은 O(V³) 시간과 O(V²) 공간을 사용한다. 도시 수가 작고 모든 도시 쌍의 이동 비용이 필요하면 거리 행렬을 한 번 계산한 뒤 질의에 답할 수 있다. 중간 정점 k를 바깥 반복으로 두는 상태 정의를 지켜야 한다.

벨만 포드 알고리즘은 음수 간선을 허용하는 단일 시작점 최단 경로 알고리즘이다. 도달 가능한 음수 사이클도 탐지할 수 있다. 모든 간선에 대한 거리 완화를 반복한다. 정점 V개에서 단순 경로는 최대 V−1개 간선을 가지므로 그만큼의 단계가 기본 근거가 된다. 어떤 경로의 간선 비용이 4와 −2이면 전체 비용은 2이다. 음수 간선이 있다는 이유만으로 최단 경로가 정의되지 않는 것은 아니다. 시작점에서 도달 가능한 음수 사이클을

다익스트라 알고리즘은 음수가 아닌 간선 가중치를 가진 그래프에서 한 시작점의 최단 거리를 구하는 알고리즘이다. 현재 잠정 거리가 가장 작은 정점을 선택하고 이웃으로 가는 거리를 완화한다. 우선순위 큐를 이용해 다음 정점을 효율적으로 고른다. A→B가 2, A→C가 7, B→C가 3이면 C까지의 거리는 직접 가는 7보다 B를 거치는 5가 짧다. 음수 간선이 있으면 거리 확정 논리가 깨질 수 있다. 중복 항목을 큐에 넣는 구현은

깊이 우선 탐색은 한 경로를 더 진행할 수 있을 때까지 따라간 뒤 돌아와 다른 경로를 조사하는 그래프 탐색이다. 재귀 호출이나 명시적인 스택으로 구현한다. 진입·종료 시점을 구별하면 위상 정렬과 연결 구조 분석에 활용할 수 있다. 폴더 구조를 따라 내려가 자식들을 모두 처리하고 부모로 돌아오는 탐색을 생각할 수 있다. 그래프에서는 순환을 막기 위한 방문 상태가 필요하다. 긴 경로를 재귀로 처리하면 호출 스택 한계에 닿을 수 있

너비 우선 탐색은 시작점에서 가까운 단계의 정점을 먼저 방문하는 그래프 탐색이다. 보통 FIFO 큐를 사용한다. 발견한 정점을 큐에 넣고 앞에서 꺼내며 이웃을 조사한다. 인접 리스트에서 정점 V개와 간선 E개를 처리하는 비용은 O(V+E)이다. 모든 이동 비용이 같은 미로에서는 출발점에서 한 칸, 두 칸 거리의 위치를 순서대로 찾으므로 최소 이동 횟수를 얻을 수 있다. 방문 표시는 큐에 넣을 때 관리하면 중복 등록을 줄일 수

선택 정렬은 아직 정렬하지 않은 부분에서 최솟값을 찾아 앞쪽의 확정 위치로 옮기는 정렬이다. 첫 단계에서는 전체 최솟값을, 다음 단계에서는 남은 부분의 최솟값을 고른다. 비교 횟수는 입력의 기존 정렬 정도와 관계없이 대체로 이차 규모이다. 3, 1, 2에서 1을 찾아 첫 원소와 교환하면 1, 3, 2가 된다. 남은 두 원소를 처리하면 정렬이 끝난다. 일반적인 교환 구현은 안정적이지 않다. 교환 횟수는 O(n)으로 적지만 최솟값

삽입 정렬은 앞쪽의 정렬된 부분에 다음 원소를 알맞은 위치로 끼워 넣는 정렬이다. 원소보다 큰 앞의 값들을 한 칸씩 옮기고 빈자리에 원소를 넣는다. 최악 O(n²)이지만 이미 정렬된 입력은 선형 시간에 처리하는 구현이 가능하다. 2, 5까지 정렬된 상태에서 3을 처리하면 5를 오른쪽으로 옮기고 그 자리에 3을 넣는다. 작은 배열이나 거의 정렬된 입력에 유용하지만 큰 무작위 입력에는 이동 횟수가 많다. 같은 키를 건너뛰지 않도록

기수 정렬은 키를 자릿수나 비트 묶음으로 나누고 각 부분을 처리하여 전체 순서를 만드는 방법이다. 낮은 자리부터 처리하는 LSD 방식은 각 단계의 안정성이 중요하다. 자릿수 d와 한 자리의 범위 k를 쓰는 구현은 대략 O(d(n+k)) 비용으로 분석한다. 세 자리 양의 정수를 일의 자리, 십의 자리, 백의 자리 순서로 안정 정렬하면 앞서 정리한 낮은 자리의 순서가 보존된다. 음수, 가변 길이 문자열과 부동소수점은 표현 규칙에

계수 정렬은 제한된 범위의 정수 키가 몇 번 나타나는지 세어 정렬하는 방법이다. 입력 크기를 n, 키 범위를 k라 하면 대표적인 구현은 O(n+k) 시간과 계수 배열을 사용한다. 누적 개수를 이용하면 원소를 결과의 위치에 배치할 수 있다. 0부터 100까지의 시험 점수를 정렬할 때 각 점수의 개수를 세면 비교를 반복하지 않고 점수순 결과를 만들 수 있다. 키 범위가 매우 크고 입력은 적다면 계수 배열이 비효율적이다. 키만 다시

힙 정렬은 힙에서 우선순위가 가장 높은 원소를 반복적으로 꺼내 정렬하는 방법이다. 배열을 최대 힙으로 만든 뒤 루트의 최댓값을 마지막 미정렬 위치로 옮긴다. 힙 범위를 줄이고 조건을 복구하는 과정을 반복한다. 최대 힙에서 가장 큰 원소를 뒤로 보내면 배열 끝에서부터 오름차순 결과가 확정된다. 전형적인 배열 구현은 최악 O(n log n), 추가 공간 O(1)이지만 안정적이지 않다. 같은 점근적 시간이라도 메모리 접근 패턴 때문

퀵 정렬은 피벗을 기준으로 원소를 분할하고 각 부분을 재귀적으로 정렬하는 알고리즘이다. 분할이 균형적이면 평균적인 실행 비용은 O(n log n)이지만, 나쁜 분할이 반복되면 O(n²)이 된다. 무작위화는 특정 입력 순서의 영향을 줄이는 방법이다. 피벗 5를 기준으로 작은 값과 큰 값을 나누면 피벗을 사이에 두고 각 부분을 독립적으로 정렬할 수 있다. 같은 값이 많다면 세 부분 분할도 고려한다. 일반적인 제자리 구현은 안정 정

병합 정렬은 작은 부분들을 정렬한 뒤 두 정렬된 결과를 병합하는 분할 정복 정렬이다. 두 부분의 앞 원소를 비교하며 더 작은 것을 결과로 옮긴다. 균등하게 나누는 일반적인 구현의 시간 복잡도는 O(n log n)이다. 정렬된 1, 4와 2, 3을 병합하면 앞 원소를 차례로 비교해 1, 2, 3, 4를 얻는다. 같은 키에서는 왼쪽을 먼저 선택하면 안정성을 유지할 수 있다. 배열 구현은 일반적으로 O(n) 보조 공간을 사용한다.

비교 정렬은 키 사이의 비교 결과를 이용해 순서를 결정하는 정렬 알고리즘의 부류이다. 병합 정렬과 퀵 정렬 등이 속한다. 서로 다른 n개 원소에는 n!가지 입력 순서가 있다. 비교 의사결정 트리로 이 경우들을 구별해야 하므로 일반적인 비교 정렬에는 최악 Ω(n log n)의 비교 하한이 있다. 정수뿐 아니라 사용자 정의 객체도 일관된 비교 함수가 있으면 비교 정렬로 처리할 수 있다. 이 하한은 비교만으로 순서를 알아내는 모형의

안정 정렬은 비교 키가 같은 원소들의 입력 순서를 결과에서도 유지하는 정렬이다. 안정성은 정렬 결과의 동률 처리 성질이다. 시간 복잡도나 오류 없이 실행된다는 일반적인 의미의 안정성과 구별한다. 이름순으로 정렬한 직원 목록을 부서 기준으로 안정 정렬하면 같은 부서 안에서는 앞서 만든 이름순이 유지된다. 원래 입력 순서가 불명확하면 안정 정렬만으로 재현 가능한 결과를 얻지 못할 수 있다. 데이터베이스 결과처럼 입력 순서가 보장되

정렬 알고리즘은 정한 순서 관계에 맞게 원소들을 재배열하는 절차이다. 데이터의 종류와 요구 조건에 따라 적절한 방법이 달라진다. 시간 복잡도 외에도 추가 메모리, 안정성, 기존 정렬 정도와 외부 저장 장치 사용 여부를 비교한다. 비교 함수가 일관된 순서를 정의해야 한다. 상품을 가격 오름차순으로 정렬하되 같은 가격에서는 등록 시각을 기준으로 정렬하면 결과 순서를 명확히 정할 수 있다. 숫자를 문자열로 비교하면 10이 2보다 앞

누적 합은 시작부터 각 위치까지의 합을 미리 저장하여 구간 합 질의를 빠르게 처리하는 방법이다. P[0]=0, P[i+1]=P[i]+A[i]로 두면 반열린 구간 [l,r)의 합은 P[r]−P[l]이다. 전처리 O(n) 후 질의 하나를 O(1)에 처리한다. 배열 3, 1, 4의 누적 합은 0, 3, 4, 8이다. 인덱스 1부터 3 직전까지의 합은 8−3=5로 계산한다. 원소가 바뀌면 이후 누적 값도 영향을 받는다. 잦은 갱신과

슬라이딩 윈도는 연속 구간의 양 끝을 이동시키며 필요한 집계 상태를 갱신하는 기법이다. 고정 길이 구간의 합은 나가는 값을 빼고 새 값을 더해 유지할 수 있다. 가변 길이에서는 조건을 만족할 때까지 구간을 늘리거나 줄인다. 길이 3인 구간의 합을 차례로 구할 때 첫 합을 만든 뒤 한 칸 이동할 때마다 원소 두 개만 반영하면 된다. 합이 일정 값 이하인 구간을 찾는 단순한 가변 윈도는 음수가 섞이면 단조성이 깨질 수 있다. 구간

두 포인터는 배열 등의 두 위치를 함께 이동시키며 조건을 만족하는 범위를 찾는 기법이다. 포인터가 한 방향으로만 이동하면 각 원소를 제한된 횟수만 방문할 수 있다. 위치 이동을 정당화하는 정렬 조건이나 단조성이 핵심이다. 정렬된 배열에서 합이 목표값인 두 원소를 찾을 때 양 끝에서 시작한다. 합이 작으면 왼쪽을, 크면 오른쪽을 움직여 후보를 줄인다. 포인터 두 개를 사용했다고 자동으로 O(n)이 되는 것은 아니다. 매번 뒤로

메모이제이션은 함수의 입력에 대응하는 결과를 저장해 같은 계산의 반복을 줄이는 기법이다. 재귀형 동적 계획법에서 자주 사용한다. 호출 때 먼저 저장된 결과를 확인하고, 없다면 계산해 보관한다. Python의 functools.cache는 이런 방식의 캐시를 제공한다. 피보나치 수를 단순 재귀로 구하면 같은 n을 여러 번 계산한다. 각 n의 결과를 저장하면 서로 다른 상태만 계산하게 된다. 결과가 시간이나 외부 상태에 의존하면

동적 계획법은 반복되는 부분 문제의 결과를 저장하고 의존 관계에 따라 계산하여 전체 문제를 푸는 방법이다. 상태의 의미, 상태 사이의 전이, 초기값과 계산 순서를 정한다. 보통 상태 수와 상태 하나의 전이 비용을 곱해 시간 복잡도를 분석한다. 계단을 한 번에 1칸 또는 2칸 오르는 경우의 수는 직전 두 상태의 합으로 계산할 수 있다. 같은 높이의 경우의 수를 매번 재귀로 다시 구하지 않는다. 상태에 필요한 정보를 빼면 서로 다

탐욕 알고리즘은 각 단계에서 정한 기준에 가장 유리한 선택을 하며 해를 구성하는 방법이다. 국소적으로 좋은 선택이 전체 최적해로 이어지는 문제 구조가 필요하다. 교환 논증이나 안전한 선택의 성질로 선택 규칙을 정당화한다. 겹치지 않는 활동을 가장 많이 고르는 문제에서는 끝나는 시간이 가장 이른 활동부터 선택하는 전략이 성립한다. 단순히 가장 짧은 활동부터 고르는 규칙과는 다르다. 그럴듯한 규칙만으로 최적성을 보장할 수 없다.

분할 정복은 문제를 더 작은 문제들로 나누어 해결하고 그 결과를 결합하는 알고리즘 설계 방법이다. 분할 크기, 하위 문제 수, 결합 비용이 전체 성능을 결정한다. 재귀가 더 작은 입력으로 진행하는 조건과 직접 풀 수 있는 종료 조건을 정의한다. 병합 정렬은 배열을 두 부분으로 나누어 정렬한 후 순서대로 합친다. 각 단계의 결합이 선형이고 단계 수가 로그 규모라 O(n log n)이 된다. 재귀를 사용한다는 사실만으로 분할 정복

백트래킹은 부분 해를 확장하다가 조건을 만족할 수 없으면 이전 상태로 돌아가 다른 선택을 탐색하는 방법이다. 선택, 재귀 탐색, 선택 취소의 순서로 상태를 관리한다. 가지치기는 해당 분기에서 유효한 해가 나올 수 없다는 근거가 있어야 한다. 체스판에 퀸을 한 행씩 놓으며 이미 놓인 퀸과 같은 열이나 대각선이면 그 선택을 중단한다. 모든 배치를 끝까지 만들고 검사할 필요가 줄어든다. 가지치기가 있어도 최악의 탐색 공간은 클 수

완전 탐색은 가능한 후보를 빠짐없이 조사하여 조건을 만족하는 해를 찾는 방법이다. 입력 규모가 작을 때 기준 구현으로도 유용하다. 후보를 생성하는 규칙과 검사 조건을 분리한다. 후보 수가 2ⁿ이나 n!처럼 늘어날 수 있으므로 입력 크기에 따른 전체 연산량을 먼저 추산한다. 원소 4개의 부분집합은 16개이다. 각 부분집합의 합을 계산해 목표값과 비교하면 누락 없는 검사가 가능하다. 후보 생성 자체의 중복이나 누락을 검증해야 한다