2-2) 알고리즘 분석 정리

1  for j = 2 to A.length           // 두 번째 원소부터 시작
2      key = A[j]                   // 현재 원소를 key로 저장
3      i = j - 1                    // 정렬된 부분의 마지막 인덱스
4      while i > 0 and A[i] > key   // key보다 큰 원소 찾기
5          A[i+1] = A[i]            // 오른쪽으로 이동
6          i = i - 1                // 왼쪽으로 계속 탐색
7      A[i+1] = key                 // 찾은 위치에 key 삽입

1  l = LEFT(i)           // 왼쪽 자식 인덱스
2  r = RIGHT(i)          // 오른쪽 자식 인덱스
3  if l ≤ A.heap-size and A[l] > A[i]
4      largest = l
5  else largest = i
6  if r ≤ A.heap-size and A[r] > A[largest]
7      largest = r
8  if largest ≠ i        // 자식이 더 크면
9      exchange A[i] with A[largest]
10     MAX-HEAPIFY(A, largest)  // 재귀 호출

1  A.heap-size = A.length
2  for i = ⌊A.length/2⌋ downto 1
3      MAX-HEAPIFY(A, i)

COUNTING-SORT(A, B, n, k)

1  for i = 0 to k
2      C[i] = 0                      // 카운트 초기화
3  for j = 1 to n
4      C[A[j]] = C[A[j]] + 1         // 각 값의 개수 카운트
5  // C[i]는 이제 값 i의 개수
6  for i = 1 to k
7      C[i] = C[i] + C[i-1]          // 누적 합 계산
8  // C[i]는 이제 i 이하 원소의 개수
9  for j = n downto 1         // 역순으로 처리 (안정성)
10     B[C[A[j]]] = A[j]              // 올바른 위치에 배치
11     C[A[j]] = C[A[j]] - 1          // 카운트 감소

RADIX-SORT(A, d)

1  for i = 1 to d
2      use a stable sort to sort array A on digit i (counting sort)

PARTITION(A, p, r)
1  x = A[r]              // 마지막 원소를 pivot으로 선택
2  i = _____             // 작은 원소들의 경계
3  for j = __ to _____  
4      if A[j] ≤ x       
5          i = _____     
6          exchange A[i] <-> ___ 
7  exchange _____ <-> A[r]  
8  return i + 1 

        5
       / \
      3   7
     / \ / \
    2  4 6  8

INORDER-TREE-WALK(x)
    ifx ≠ NIL
INORDER-TREE-WALK(left[x])
        print key[x]
INORDER-TREE-WALK(right[x])

TREE-SEARCH(x, k)
    if x= NILor k= key[x]
return x
    if k< key[x]
return TREE-SEARCH(left[x], k)
else
return TREE-SEARCH(right[x], k)

ITERATIVE-TREE-SEARCH(x, k)
    while x ≠ NILand k ≠ key[x]
        if k< key[x]
            x=left[x]
else
            x=right[x]
return x

TREE-MINIMUM(x)
while left[x] ≠NIL
x= left[x]
return x

TREE-MAXIMUM(x)
while right[x] ≠NIL
x= right[x]
return x

TREE-SUCCESSOR(x)
if right[x] ≠ NIL
return TREE-MINIMUM(right[x])
    y = p[x]
while y ≠ NILandx= right[y]
        x =y
y= p[y]
return y

TREE-INSERT(T, z)
    y= NIL
    x= root[T]
    while x ≠ NIL
        y= x
        if key[z]< key[x]
            x=left[x]
else
            x=right[x]
    p[z]= y
    if y= NIL
        root[T]= z
else if key[z]< key[y]
left[y]= z
else
right[y]= z

TREE-DELETE(T, z)
    ifleft[z]= NILorright[z]= NIL
        y= z
else
        y= TREE-SUCCESSOR(z)

    ifleft[y] ≠ NIL
        x=left[y]
else
        x=right[y]

    if x ≠ NIL
        p[x]= p[y]

    if p[y]= NIL
        root[T]= x
else if y=left[p[y]]
left[p[y]]= x
else
right[p[y]]= x

    if y ≠ z
        key[z]= key[y]

return y

1
 \
  2
   \
    3
     \
      4

#include<iostream>
usingnamespace std;

structNode {
int key;
    Node* left;
    Node* right;
    Node* parent;

Node(int k) :key(k),left(nullptr),right(nullptr),parent(nullptr) {}
};

classBST {
private:
    Node* root;

public:
BST() :root(nullptr) {}

// 탐색
Node* search(int k) {
        Node* x = root;
while (x !=nullptr && k != x->key) {
if (k < x->key)
                x = x->left;
else
                x = x->right;
        }
return x;
    }

// 최솟값
Node* minimum(Node* x) {
while (x->left !=nullptr)
            x = x->left;
return x;
    }

// 최댓값
Node* maximum(Node* x) {
while (x->right !=nullptr)
            x = x->right;
return x;
    }

// 후속자
Node* successor(Node* x) {
if (x->right !=nullptr)
returnminimum(x->right);

        Node* y = x->parent;
while (y !=nullptr && x == y->right) {
            x = y;
            y = y->parent;
        }
return y;
    }

// 삽입
voidinsert(int k) {
        Node* z =newNode(k);
        Node* y =nullptr;
        Node* x = root;

while (x !=nullptr) {
            y = x;
if (z->key < x->key)
                x = x->left;
else
                x = x->right;
        }

        z->parent = y;

if (y ==nullptr)
            root = z;
elseif (z->key < y->key)
            y->left = z;
else
            y->right = z;
    }

// 중위 순회
voidinorder(Node* x) {
if (x !=nullptr) {
inorder(x->left);
            cout << x->key <<" ";
inorder(x->right);
        }
    }

voidinorder() {
inorder(root);
        cout << endl;
    }

Node* getRoot() {return root; }
};

intmain() {
    BST tree;

    tree.insert(5);
    tree.insert(3);
    tree.insert(7);
    tree.insert(2);
    tree.insert(4);
    tree.insert(6);
    tree.insert(8);

    cout <<"Inorder: ";
    tree.inorder();// 2 3 4 5 6 7 8

    Node* found = tree.search(4);
if (found)
        cout <<"Found: " << found->key << endl;

    cout <<"Min: " << tree.minimum(tree.getRoot())->key << endl;// 2
    cout <<"Max: " << tree.maximum(tree.getRoot())->key << endl;// 8

return0;
}

        (7,B)
       /     \
    (3,R)    (18,R)
    /  \      /    \
 (nil) (nil) (10,B) (22,B)
              /  \    /  \
           (8,R)(11,R)(nil)(26,R)

xy
       / \                         / \
      αy         →x   γ
         / \                     / \
        β   γ                   α   β

yx
         / \                       / \
x   γ       →             αy
       / \                           / \
      α   β                         β   γ

LEFT-ROTATE(T, x)
    y=right[x]
right[x]=left[y]
    ifleft[y] ≠ nil[T]
        p[left[y]]= x
    p[y]= p[x]
    if p[x]= nil[T]
        root[T]= y
else if x=left[p[x]]
left[p[x]]= y
else
right[p[x]]= y
left[y]= x
    p[x]= y

RB-INSERT(T, z)
    y= nil[T]
    x= root[T]
while x ≠ nil[T]
        y= x
if key[z]< key[x]
            x= left[x]
else
            x= right[x]
    p[z]= y
if y= nil[T]
        root[T]= z
elseif key[z]< key[y]
        left[y]= z
else
        right[y]= z
    left[z]= nil[T]
    right[z]= nil[T]
    color[z]= RED
    RB-INSERT-FIXUP(T, z)

RB-INSERT-FIXUP(T, z)
    while color[p[z]]= RED
        if p[z]=left[p[p[z]]]
            y=right[p[p[z]]]
            if color[y]= RED
                color[p[z]]= BLACK
                color[y]= BLACK
                color[p[p[z]]]= RED
                z= p[p[z]]
else
                if z=right[p[z]]
                    z= p[z]
LEFT-ROTATE(T, z)
                color[p[z]]= BLACK
                color[p[p[z]]]= RED
RIGHT-ROTATE(T, p[p[z]])
else
            (samewithleft/right exchanged)
    color[root[T]]= BLACK

enumColor { RED, BLACK };

structNode {
int key;
    Color color;
    Node *left, *right, *parent;

Node(int k) :key(k),color(RED),left(nullptr),right(nullptr),parent(nullptr) {}
};

1--- 2
     |     
3--- 4

Adj[1] = [2, 3]
Adj[2] = [1, 4]
Adj[3] = [1, 4]
Adj[4] = [2, 3]

    1 → 2
    ↓   ↓
    3 → 4

Adj[1] = [2, 3]
Adj[2] = [4]
Adj[3] = [4]
Adj[4] = []

BFS(G, s)
for each vertex u ∈ V[G] - {s}
        color[u] = WHITE
        d[u] = ∞
        π[u] = NIL

    color[s] = GRAY
    d[s] =0
    π[s] =NIL
Q= ∅
    ENQUEUE(Q, s)

while Q ≠ ∅
        u = DEQUEUE(Q)
for each v ∈ Adj[u]
if color[v] = WHITE
                color[v] = GRAY
                d[v] = d[u] +1
                π[v] = u
ENQUEUE(Q, v)
        color[u] = BLACK

1 ≤ d[v] < f[v] ≤ 2|V|

DFS(G)
foreach vertex u ∈ V[G]
        color[u] = WHITE
        π[u] = NIL
time =0
foreach vertex u ∈ V[G]
if color[u] = WHITE
            DFS-VISIT(u)

DFS-VISIT(u)
    color[u] = GRAY
time =time +1
    d[u] =time
foreach v ∈ Adj[u]
if color[v] = WHITE
            π[v] = u
            DFS-VISIT(v)
    color[u] = BLACK
time =time +1
    f[u] =time

d[u] < f[u] < d[v] < f[v]
또는
d[v] < f[v] < d[u] < f[u]

d[u] < d[v] < f[v] < f[u]

d[v] < d[u] < f[u] < f[v]

1. DFS 수행 → 완료 시간 f[v] 계산
2. f[v] 내림차순으로 정점 출력

KAHN_TOPOLOGICAL_SORT(G):
    L = []
    S = { v | indegree[v] =0 }

while Snot empty
        n = removefrom S
        append nto L
foreach m neighborof n
            remove (n, m)
            indegree[m]--
if indegree[m] ==0
add mto S

if edges remain
        error
else
return L

#include<iostream>
#include<vector>
#include<queue>
usingnamespace std;

vector<int>bfs(int start, vector<vector<int>>& adj,int n) {
vector<int>dist(n + 1,-1);
    queue<int> q;

    dist[start] =0;
    q.push(start);

while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (dist[v] ==-1) {
                dist[v] = dist[u] +1;
                q.push(v);
            }
        }
    }
return dist;
}

int timeStamp =0;

voiddfsVisit(int u, vector<vector<int>>& adj,
              vector<int>& color, vector<int>& d, vector<int>& f) {
    color[u] =1;
    d[u] = ++timeStamp;

for (int v : adj[u])
if (color[v] ==0)
dfsVisit(v, adj, color, d, f);

    color[u] =2;
    f[u] = ++timeStamp;
}

voidtopoSort(int u, vector<vector<int>>& adj,
              vector<bool>& visited, stack<int>& st) {
    visited[u] =true;
for (int v : adj[u])
if (!visited[v])
topoSort(v, adj, visited, st);
    st.push(u);
}

vector<int>kahnTopologicalSort(vector<vector<int>>& adj,int n) {
vector<int>indegree(n + 1,0);
for (int u =1; u <= n; u++)
for (int v : adj[u])
            indegree[v]++;

    queue<int> q;
for (int u =1; u <= n; u++)
if (indegree[u] ==0)
            q.push(u);

    vector<int> result;
while (!q.empty()) {
int u = q.front(); q.pop();
        result.push_back(u);
for (int v : adj[u])
if (--indegree[v] ==0)
                q.push(v);
    }

if (result.size() != n)return {};
return result;
}

vector<vector<int>>findSCC(vector<vector<int>>& adj,int n) {
vector<bool>visited(n + 1,false);
    stack<int> st;

    function<void(int)> dfs1 = [&](int u) {
        visited[u] =true;
for (int v : adj[u])
if (!visited[v])dfs1(v);
        st.push(u);
    };

for (int u =1; u <= n; u++)
if (!visited[u])dfs1(u);

    vector<vector<int>>radj(n +1);
for (int u =1; u <= n; u++)
for (int v : adj[u])
            radj[v].push_back(u);

fill(visited.begin(), visited.end(),false);
    vector<vector<int>> sccs;

    function<void(int, vector<int>&)> dfs2 = [&](int u, vector<int>& comp) {
        visited[u] =true;
        comp.push_back(u);
for (int v : radj[u])
if (!visited[v])dfs2(v, comp);
    };

while (!st.empty()) {
int u = st.top(); st.pop();
if (!visited[u]) {
            vector<int> comp;
dfs2(u, comp);
            sccs.push_back(comp);
        }
    }

return sccs;
}