[Index] 알고리즘 목차 정리

알고리즘 글을 모아 두는 목차다. 이름에 링크가 걸린 알고리즘만 글이 있다. 지금은 정렬 네 편(버블 · 선택 · 삽입 · 퀵)뿐이고, 링크가 없는 줄은 앞으로 쓸 글의 자리다. 그 줄은 한 줄 설명과 용어 링크로 무엇을 하는 알고리즘인지만 적어 둔다.

같은 알고리즘이 두 표에 나오기도 한다. 표 하나는 「무엇을 하는가」(정렬 · 탐색)로 묶었고, 다른 표는 「어떤 방식으로 푸는가」(분할 정복 · 그리디 같은 풀이 방식)로 묶었기 때문이다. 퀵 정렬은 정렬을 하는 알고리즘이면서 분할 정복으로 푸는 알고리즘이라 두 표에 다 들어간다.

알고리즘

정렬 알고리즘 (Sorting)

배열의 원소를 작은 것부터 큰 것 순서로 늘어놓는 알고리즘이다.

알고리즘 이름	설명
버블 정렬	가장 간단한 정렬 알고리즘. 이웃한 두 원소를 비교해 자리를 바꾼다.
선택 정렬	매번 최솟값을 선택하여 정렬.
삽입 정렬	맨 앞 원소 하나를 「정렬된 부분」으로 보고 시작해, 다음 원소를 그 앞의 정렬된 원소들과 뒤에서부터 비교하며 알맞은 자리에 끼워 넣는다.
퀵 정렬	분할 정복 방식의 정렬 알고리즘. 피벗을 기준으로 작은 쪽과 큰 쪽으로 나눈다.
병합 정렬 (Merge Sort)	배열을 원소 하나가 남을 때까지 반씩 나눈 뒤, 정렬된 두 조각을 합치기를 되풀이한다. 원소 하나짜리 조각은 그 자체로 정렬되어 있어서 「정렬된 두 배열」이 여기서 생긴다.
힙 정렬	힙 자료구조(부모가 자식보다 항상 크거나 작은 트리 모양 자료구조)를 이용한 정렬.

탐색 알고리즘 (Searching)

배열이나 그래프에서 원하는 값이나 노드를 찾는 알고리즘이다.

알고리즘 이름	설명
선형 탐색 (Linear Search)	처음부터 끝까지 순서대로 모든 원소를 확인.
이진 탐색 (Binary Search)	정렬된 배열에서 가운데 값과 비교해 찾는 범위를 반씩 줄인다.
BFS (Breadth-First Search, 너비 우선 탐색)	그래프를 출발점에서 가까운 노드부터 한 겹씩 넓혀 가며 탐색. 그래서 간선 수가 가장 적은 경로를 찾는다.
DFS (Depth-First Search, 깊이 우선 탐색)	그래프를 한 길로 끝까지 들어갔다가 되돌아오며 탐색. 두 노드 사이의 경로가 있는지, 사이클이 있는지 확인할 때 쓴다.

그래프 알고리즘 (Graph)

그래프에서 최단 경로나 모든 노드를 잇는 방법 같은 것을 구하는 알고리즘이다. 아래 표의 처음 세 최단 경로 알고리즘(다익스트라 · 벨만-포드 · 플로이드-워셜)은 간선마다 거리 같은 숫자가 붙은 가중치 그래프를 다룬다.

알고리즘 이름	설명
다익스트라 (Dijkstra)	출발점 하나에서 다른 모든 노드까지의 최단 경로. 가중치가 음수인 간선이 없을 때만 쓴다.
벨만-포드 (Bellman-Ford)	출발점 하나에서 다른 모든 노드까지의 최단 경로. 음수 간선이 있어도 되고, 음수 사이클이 있으면 찾아낸다(음수 사이클이 있으면 최단 경로가 정해지지 않아서 그 사실을 알려야 한다).
플로이드-워셜 (Floyd-Warshall)	출발점 하나가 아니라, 노드 두 개를 짝지은 모든 조합 각각의 최단 경로를 한 번에 구한다.
크루스칼 (Kruskal)	최소 신장 트리. 유니온-파인드 사용.
프림 (Prim)	최소 신장 트리. 우선순위 큐 사용.
위상 정렬 (Topological Sort)	DAG의 노드를 「앞서야 하는 것이 먼저 오게」 한 줄로 늘어놓는다. 예: 과목 선수 관계로 수강 순서 정하기.

동적 계획법 (Dynamic Programming, DP)

동적 계획법은 같은 작은 문제가 여러 번 나올 때 한 번 구한 답을 적어 두고 다시 쓰는 풀이 방식이다. 아래는 그 방식으로 푸는 대표 문제들이다.

알고리즘 이름	설명
0/1 배낭 (Knapsack)	무게 한도가 있는 가방에 물건을 골라 담아 가치 합을 최대로 만든다. 「0/1」은 물건마다 통째로 넣거나(1) 안 넣거나(0) 둘 중 하나라 쪼개 넣을 수 없다는 뜻이다.
LIS (최장 증가 부분 수열)	수열에서 값이 점점 커지게 고를 수 있는 부분 수열의 최대 길이.
LCS (최장 공통 부분 수열)	두 문자열에 공통으로 들어 있는 부분 수열의 최대 길이.
동전 거스름 (Coin Change)	어떤 동전 체계에서든 최소 동전 수나 거슬러 주는 경우의 수를 구한다. 아래 그리디의 거스름돈 문제와 달리 동전 체계를 가리지 않는다.

분할 정복 (Divide & Conquer)

분할 정복은 보통 재귀로 구현하며, 큰 문제를 같은 모양의 작은 문제로 나눠 각각 풀고 답을 합치는 풀이 방식이다. 정렬 · 탐색 표에 있던 알고리즘 중 이 방식으로 푸는 것이 여기 다시 나온다.

알고리즘 이름	설명
병합 정렬 (Merge Sort)	리스트를 분할 후 병합해 정렬. 정렬 표의 병합 정렬과 같은 알고리즘이다.
퀵 정렬 (Quick Sort)	피벗 기준 분할 후 정렬.
이진 탐색 (Binary Search)	범위를 가운데에서 나눠 한쪽만 다시 탐색. 나눈 작은 문제가 하나뿐이고 합칠 것도 없지만, 「같은 모양의 작은 문제로 나눠 푼다」는 점이 같아서 분할 정복으로 분류한다.
최근접 점 쌍 (Closest Pair)	평면 위 여러 점 중 서로 가장 가까운 두 점의 거리 계산.

그리디 알고리즘 (Greedy)

그리디 알고리즘은 매 단계에서 지금 가장 좋아 보이는 것을 고르고 되돌리지 않는 풀이 방식이다.

알고리즘 이름	설명
활동 선택 (Activity Selection)	시작 · 종료 시간이 있는 활동(예: 회의) 중 시간이 겹치지 않게 최대한 많이 고른다. 일찍 끝나는 것을 먼저 고르면 남은 시간이 가장 많이 남는다.
인터벌 스케줄링	구간(인터벌, 시작점과 끝점이 있는 범위) 중 겹치지 않는 것을 최대한 많이 고른다. 활동 선택과 같은 문제를 구간이라는 말로 부르는 이름이다.
허프만 코딩 (Huffman Coding)	자주 나오는 글자에 짧은 비트, 드문 글자에 긴 비트를 줘서 데이터를 압축한다. 전체 비트 수가 가장 적은 접두사 코드를 만든다.
거스름돈 문제 (Greedy Coin)	큰 동전부터 낸다. 500 · 100 · 50 · 10원 같은 특정 동전 체계에서만 최소 동전 수가 된다(안 되는 예는 그리디 알고리즘 용어 페이지에 있다). 다른 체계는 DP 표의 동전 거스름으로 푼다.

백트래킹 (Backtracking)

백트래킹은 하나씩 골라 나가다가 답이 안 되는 길이면 바로 앞 선택으로 되돌아가는 풀이 방식이다.

알고리즘 이름	설명
N-Queen	N×N 체스판에 퀸 N개를 서로 공격하지 않게 놓는다. 퀸은 같은 가로줄 · 세로줄 · 대각선에 있는 말을 공격하므로, 어느 두 퀸도 한 줄이나 대각선에 같이 있으면 안 된다.
순열/조합 생성	모든 순열·조합 나열.
부분집합 합 (Subset Sum)	주어진 합을 만드는 부분집합 탐색.
스도쿠 해결	「가로줄 · 세로줄 · 3×3 상자 안에 같은 숫자가 두 번 나오면 안 된다」 같은 규칙(제약)을 어기지 않는 숫자만 채워 넣으며 푼다.

문자열 알고리즘 (String)

긴 문자열 안에서 짧은 문자열을 찾는 패턴 매칭 같은 일을 하는 알고리즘이다.

알고리즘 이름	설명
KMP	접두사-접미사 테이블로 텍스트 길이 n과 패턴 길이 m의 합에 비례하는 시간(선형 시간, O(n+m). 빅오 표기 참고)에 패턴 매칭.
라빈-카프 (Rabin-Karp)	롤링 해시 기반 문자열 검색.
Z-Algorithm	문자열의 각 위치에서 시작하는 부분이 문자열 맨 앞부분과 몇 글자까지 같은지를 선형 시간에 계산한다. 패턴 매칭에 쓴다.
트라이 (Trie)	알고리즘이 아니라 트라이 자료구조다. 문자열 집합 검색/자동완성.
접미사 배열 & LCP	정렬된 접미사와 공통 접두사 길이로 「이 부분 문자열이 있나」, 「몇 번 나오나」 같은 질문에 답한다.

---

자신만의 철학을 만들어가는 중입니다.

---

최상단으로 이동했습니다!