알고리즘 정리
알고리즘 정리
Time Complexity
알고리즘의 시간 복잡도 측정 가능
- 입력 사이즈 N
- Basic operation 선택
- 2가 N 당 얼마나 계산 필요한지 계산
- n = 102일 경우 시간 복잡도
O(logN) O(N) O(NlogN) O(N2) O(N3) O(2N) O(N!) 0.007µs 0.10µs 0.664µs 10µs 1ms 4 * 1013 years INF
- O(N) (Big-Oh) : Upper Bound, 가장 오래 걸려도 N 시간과 작거나 같게 걸릴 경우
- Ω(N) (Omega) : Lower Bound, 최소한 N 시간과 같거나 오래 걸릴 경우
- θ(N) (Omega) : N 만큼 걸리는 집합 (O와 Ω의 교집합)
- o(N) (Small-Oh) : N 시간 보다 적게 걸리는 모든 집합
- Lower bound 와 Upper bound가 같다면 Optimal한 알고리즘이라 할 수 있음
Swap
배열의 a 인덱스와 b 인덱스의 데이터 교환
Time complexityO(1)Space complexityO(1)
1
2
3
4
5
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
Sort
정렬하는 방법
Bubble sort
현재 인덱스와 다음 인덱스의 데이터만 보고 스왑한다
Time complexityO(N2)Space complexityO(N)
1
2
3
4
5
6
7
int arr[size];
for (int i = size - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
}
Selection sort
정렬되지 않은 데이터 중 가장 작은 수를 찾아서 스왑한다
Time complexityO(N2)Space complexityO(N)
1
2
3
4
5
6
7
8
int arr[size];
for (int i = 0; i < size; i++) {
int min = i;
for (int j = i + 1; j < size; j++)
if (arr[min] > arr[j])
min = j;
swap(arr[min], arr[i]);
}
Insertion sort
현재 인덱스에서 뒤로 데이터를 찾아보면서 알맞은 위치를 찾아 넣는다
Time complexityO(N2)Space complexityO(N)- 정렬이 되었을 경우 한 번 순회하면서 체크하기만 하면 됨 N
1
2
3
4
5
6
7
for (int i = 0; i < arr.size(); i++) {
int current = arr[i];
for (int j = i - 1; j >= 0; j--) {
if (arr[j] < current) break;
else swap(arr[j], arr[j + 1]);
}
}
Merge sort
데이터를 나눈 다음 정렬하고 다시 합친다.
- Divide-and-Conquer
Time complexityO(NlogN)Space complexityO(2N)- Stable하지만 In-place는
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void mergeSort(vector<int>& arr, int start, int end) {
if (start >= end)
return;
else if (end - start == 1) {
if (arr[start] > arr[end])
swap(arr[start], arr[end]);
return;
}
int center = (start + end) / 2;
mergeSort(arr, start, center);
mergeSort(arr, center + 1, end);
vector<int> temp(end - start + 1);
int l = start, r = center + 1, i = 0;
while (l <= center && r <= end) {
if (arr[l] <= arr[r])
temp[i++] = arr[l++];
else
temp[i++] = arr[r++];
}
if (l == center + 1)
while (i < end - start + 1) temp[i++] = arr[r++];
if (r == end + 1)
while (i < end - start + 1) temp[i++] = arr[l++];
for (i = 0; i < end - start + 1; i++)
arr[i + start] = temp[i];
}
Quick sort
피봇을 정해 피봇을 기준으로 작은 것과 큰 것을 나눈 다음 피봇 양쪽을 다시 재귀적으로 정렬한다.
- Divide-and-Conquer
Time complexityO(NlogN)Space complexityO(N)- Stable하지 않지만 In-place
- 재귀적으로 구현 시 Stack memory 많이 잡아 먹을 수도 있음
- 피봇이 계속 가장 크거나 작을 경우 O(N2) 일 수도 있다.
- 파티션을 나눠서 작은 파티션부터 먼저 처리한 다면 Stack Depth 낮출 수 있음
1
2
3
4
5
6
7
8
9
10
11
12
13
void quickSort(vector<int>& arr, int start, int end) {
if (start >= end)
return;
int pivot = start, l = start + 1, r = end;
while (l < r) {
while (l <= end && arr[pivot] > arr[l]) l++;
while (r >= start && arr[pivot] < arr[r]) r--;
if (l <= r) swap(arr[l], arr[r]);
}
swap(arr[r], arr[pivot]);
quickSort(arr, start, r - 1);
quickSort(arr, r + 1, end);
}
Heap Sort
힙을 만들어 배열을 정렬한다.
Time complexityO(NlogN)Space complexityO(N)- In-place, Unstable
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void siftDown(vector<int>& arr, int idx) {
int m = -1;
if (arr.size() > idx * 2 + 1)
m = arr[idx * 2] < arr[idx * 2 + 1] ? idx * 2 : idx * 2 + 1;
else if (arr.size() > idx * 2)
m = idx * 2;
if (m != -1 && arr[idx] > arr[m]) {
swap(arr[idx], arr[m]);
siftDown(arr, m);
}
}
void makeHeap(vector<int>& arr) {
for (int i = arr.size() / 2; i >= 0; i--)
siftDown(arr, i);
}
int pop(vector<int>& arr) {
int top = arr[0];
arr[0] = *(arr.end() - 1);
arr.resize(arr.size() - 1);
siftDown(arr, 0);
return top;
}
vector<int> arr = { 2, 4, 5, 3, 1, 9, 6, 7, 10, 8 };
makeHeap(arr);
while (arr.size() > 0)
printf("%d\n", pop(arr));
External Sorting
외부 디스크를 이용해서 정렬
- 정렬할 데이터가 너무 많아 한 번에 처리가 어려운 경우 사용
- 데이터를 분할해서 정렬해 놓았다가 데이터를 꺼내가면서 정렬 (Merge Sort 처럼)
Search
탐색하는 방법
Sequential search
하나하나 다 찾아봄
Time complexityO(N)Space complexityO(N)
1
2
3
4
5
int arr[size], i;
int query = 10;
for (i = 0; i < size; i++)
if (arr[i] == query) break;
arr[i] == query;
Binary search
정렬된 자료에서 반씩 버려가면서 찾음
- Divide-and-Conquer
Time complexityO(logN)Space complexityO(N)
1
2
3
4
5
6
7
8
9
10
11
int arr[size];
int query = 10;
int low = 0, high = size, center;
while (low != high) {
center = (low + high) / 2;
if (arr[center] < query)
low = center + 1;
else
high = center;
}
arr[query] == query;
Dynamic Programming
Subproblem들의 Overlapping이 없으면 Divide-and-Conquer 하면 되지만 Overlapping이 있을 경우 Dynamic Programming 기법 사용.
- Recursive property를 먼저 찾고
- Bottom-up으로 이전에 저장해 놓은 데이터를 참고하여 문제 해결
- Prinsiple of Optimality 만족해야함 (Optimal 솔루션의 Subproblem이 Optimal 할 경우)
Binomial Coefficient
nCk(조합)은 DP로 표현 가능
- b[i][j] = b[i - 1][j - 1] + b[i - 1][j], (j = 0 이거나 j = i 일 경우 1)
Time complexityO(NK)Space complexityO(NK)
1
2
3
4
5
6
7
int b[11][11];
int n = 10, k = 4;
for (int i = 0; i <= n; i++)
for (int j = 0; j <= min(i, k); j++)
if (j == 0 || i == j) b[i][j] = 1;
else b[i][j] = b[i - 1][j - 1] + b[i - 1][j];
b[n][k]; // 10C4
Floyd Algorithm
Graph에서 임의의 노드 A에서 B노드로 갈 수 있는 가장 짧은 길
- 모든 edge의 weight가 양수 일 경우
- 메인 아이디어 : A노드에서 B노드로 갈 때 1 ~ K 노드 까지만 사용해서 가는 최단 거리
Time complexityO(N3)Space complexityO(N2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Directed weighted graph
int d[5][5] = {
{0, 1, INF, 1, 5},
{9, 0, 3, 2, INF},
{INF, INF, 0, 4, INF},
{INF, INF, 2, 0, 3},
{3, INF, INF, INF, 0}
};
for (int k = 0; k < 5; k++) {
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 5; j++) {
if (d[i][j] > d[i][k] + d[k][j])
d[i][j] = d[i][k] + d[k][j];
}
}
}
TSP (Traveling Salesman Problem)
모든 노드를 지나는 최단 경로 구하기 (Euler cycle 구하기)
- 처음 노드에서 다른 노드를 지나고 다시 돌아오는 경우의 최단 거리 값을 저장해 놓았다가 사용
- 방문한 노드를 bit로 치환해서 사용 eg) 1->2->3의 경우 0111, 1->3->4의 경우 1101
- TSP(current, visited) = min(TSP(next, visited + next) + distance[current][next])
Time complexityO(2N*N2)Space complexityO(N2 + N * (2N - 1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int TSP(int cur, int visited) {
if (visited == (1 << N) - 1)
return dist[cur][0];
if (dp[cur][visited] != INF)
return dp[cur][visited];
for (int i = 0; i < N; i++) {
if (visited & (1 << i) || dist[cur][i] == INF) continue;
dp[cur][visited] = min(dp[cur][visited], TSP(i, visited | (1 << i)) + dist[cur][i]);
}
return dp[cur][visited];
}
TSP(0, 1)
Greedy Approach
현재 최선의 선택을 함
- Local optimal choice
- No reconsideration (이전꺼 다시 고려 안함)
MST (Minimum Spanning Tree)
모든 버택스를 가지는 SubTree 중 Weight의 합이 가장 작은 트리
Prim’s Algorithm
첫 버텍스에서 가장 Weight가 작은 Edge를 선택하고 해당 Edge와 연결된 버택스를 다시 추가한다. 그 후 현재 선택된 버텍스들 중 선택된 Edge를 제외하고 가장 Weight가 작은 Edge를 선택하는 과정을 반복한다.
Kruskal’s Algorithm
Weight 순서대로 Edge를 정렬한 후 Cycle을 만들지 않는 Edge를 순서대로 선택한다.
Single Source Shortest Path
하나의 버텍스에서 출발하여 다른 버텍스들 까지의 최단 거리
Dijkstra’s Algorithm (다익스트라)
현재 버텍스에서 출발하여 가장 Weight가 작은 Edge를 연결하고 연결된 버텍스와 현재 버텍스의 Edge 중 가장 Weight가 작고 Edge의 끝이 아직 선택되지 않은 버텍스를 가리키는 Edge를 선택한다.
- Priority Queue로 빠르게 구현 가능
- 모든 Weight가 양수일 경우
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
graph[K].cost = 0;
priority_queue<pair<int, int>> Q;
Q.push({ 0, K });
while (!Q.empty()) {
pair<int, int> cur = Q.top(); Q.pop();
cur._cost = -cur._cost;
if (graph[cur.id].cost < cur._cost)
continue;
for (vertex& e : graph[cur.id].edges) {
if (graph[e.id].cost == -1 || graph[e.id].cost > cur._cost + e.weight) {
graph[e.id].cost = cur._cost + e.weight;
Q.push({ -graph[e.id].cost, e.id });
}
}
}
Bellman and Ford’s Algorithm (벨만 포드)
현재 버텍스에서 연결된 버텍스에 Edge들의 Weight를 고려해 최소 Weight를 기록하고, 그 후 연결된 버텍스들에서 다시 연결된 버텍스의 Edge들의 Weight를 고려해 최소 Weight를 구하는 것을 반복
- N번 반복해서 만들 수 있음
- 음수 Weight도 가능
- 음수 Cycle은 안됨
1
2
3
4
5
6
7
8
for (int i = 1; i <= N; i++) {
for (int parent = 1; parent <= N; parent++) {
for (pii& child : graph[parent]) {
if (cost[parent] != INF && cost[parent] + child.weight < cost[child.id])
cost[child.id] = cost[parent] + child.weight;
}
}
}
0/1 Knapsack
물건마다 무게와 가치가 정해져있고 크기가 정해진 가방에 물건을 넣어 최대 가치를 만들 수 있는 경우의 수
- 현재 무게에서의 최고 가치 = max(이전까지 최대 가치, 현재 물건의 가치 + 남은 가방 크기에서 최대 가치)
- 아래 예시의 200의 경우 = max(110, 140 + 무게 10의 최고 가치 (60))
-
예시) Item1, 2, 3의 무게가 각각 5, 10, 20 가치가 50, 60, 140 일 경우
p\w 0 5 10 15 25 30 Item1 0 50 50 50 50 50 Item2 0 50 60 110 110 110 Item3 0 50 60 110 190 200
Backtracking (백트랙킹)
먼저 DFS처럼 가본 다음 조건에 맞지 않다면 이전으로 돌아감
- DFS + Bounding Function (Promising function)
n-Queens Problem
n x n 체스판에 n개의 퀸을 서로 공격할 수 없게 놓는 경우는 몇 가지 인가?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int setQueen(int N, int idx) {
if (idx == N) return 1;
int count = 0;
for (int i = 0; i < N; i++) {
bool check = true;
for (int j = idx - 1; j >= 0; j--)
if (visited[j] == i || abs(visited[j] - i) == abs(j - idx)) {
check = false; break;
}
if (check || idx == 0) {
visited[idx] = i;
count += setQueen(N, idx + 1);
}
}
return count;
}
setQueen(N, 0);
Sum-of-subsets Problem
집합이 주어졌을 때 부분 집합의 합이 W가 되는 부분 집합 찾기
- eg) n = 5, W = 21, w{} = { 5, 6, 10, 11, 16 }
- 이진 트리를 만들어 전부 순회해볼 수 있음 (좌측 자식은 선택 했을 경우, 우측 자식은 선택하지 않았을 경우)
- 하지만 백트랙킹 기법을 이용해 W를 넘어섰을 경우 그만 두고 다른 경우의 수를 볼 수 있음
Graph Coloring
그래프의 인접한 곳을 다른 색상으로 칠하기 위해 필요한 최소 색상은?
- 트리를 만들어 인접합 색상이 같은 색일 경우 백트랙킹 기법을 사용해 멈춤
Hamiltonian Circuits Problem
모든 버텍스들을 한 번씩 지나는 경로 (사이클)
- 백트랙킹 기법을 이용해 시작 버텍스부터 이어진 버텍스를 추가해나가다가 이전에 추가된 버텍스이면 다시 돌아오고, 모든 버텍스가 추가 되었을 경우 마지막 버텍스와 시작 버텍스가 이어지는지 체크
0/1 Knapsack Problem
0/1 Knapsack 문제도 백트랙킹 형태로 해결 가능하다
- 이진 트리로 좌측 자식은 물건을 넣었을 경우, 우측 자식은 물건을 넣지 않았을 경우
- 이진 트리마다 현재 남은 무게 만큼 최대 값어치의 가치 저장 (물건을 넣거나 말거나가 아닌, 물건이 조각으로 나뉘어질 수 있을 때 최대 값)
- eg) 물건들 무게 1, 3, 3 가치 10, 15, 20 이고 가방 무게가 5일 경우 최대 가치는 20 + 15 * (2/3) = 30
Branch & Bound
백트랙킹과 유사하지만 Priority Queue를 사용해 최선의 경우 부터 먼저 탐색하고 (Best-first-search) 최선의 경우를 기준으로 삼아서 다른 경우를 가지치기 할 수 있다.