[PS] 자료구조와 알고리즘 개념 정리 (Algorithm) Part 2

자료구조와 알고리즘에 대해 더 알고 싶다면 [PS] 자료구조와 알고리즘 개념 정리 (Data Structure) Part 1 포스트를 참조하면 된다.
PS 문제풀이 팁 및 문제 리스트에 대해 더 알고 싶다면 [PS] 알고리즘 문제 풀이 - 유용한 팁 및 문제 리스트 정리 포스트를 참조하면 된다.

Algorithm

Math

Recursion

재귀(Recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 방식이다. 재귀로 문제를 푼다는 것은 귀납적인 방식으로 문제를 해결하겠다는 것과 동일하다. 올바른 재귀 함수는 반드시 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 하는데 이를 보통 base condition이라고 한다. 또한 모든 입력은 base condition으로 수렴해야 한다.

 

재귀는 반복문으로 구현했을 때와 비교하여 코드는 간결하지만 메모리와 시간 측면에서는 일반적으로 손해를 본다. 재귀는 분할 정복 알고리즘, 트리 탐색 등에 널리 사용된다.

Sort

Bubble Sort

인접한 두 원소를 비교하여 정렬하는 방식으로, 시간 복잡도가 높아 실제로는 잘 사용되지 않는다.

Insertion Sort

삽입 정렬(Insertion Sort)는 각 원소를 이미 정렬된 배열의 적절한 위치에 삽입하는 방식으로 구현된다. 작은 데이터 집합에 효율적이다.

Quick Sort

퀵 정렬(Quick Sort)은 분할 정복 기법을 사용하여 빠른 평균 시간 복잡도를 가지나, 최악의 경우 시간 복잡도가 높아질 수 있다다.

Merge Sort

병합 정렬(Merge Sort)는 분할 정복 방식을 통해 구현되며, 안정적인 정렬 방식으로 다양한 상황에서 효율적이다.

• 시간복잡도 : $O(n \log n)$, $n$은 데이터 갯수
• 공간복잡도 : $O(n)$

C++ Skeleton Code (w/ STL)

#include <cstdio>
#include <algorithm>
using namespace std; 
constexpr int LM = 10;

int A[LM] = { 5,2,7,1,3,8,4,6,10,9 };

int main() {
    for(int i=0; i<LM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9 
    puts("");
    
    stable_sort(A, A+LM);
    
    for(int i=0; i<LM; i++) printf("%d ", A[i]); // 1 2 3 4 5 6 7 8 9 10 
    puts("");
    
    return 0;   
}

 

C++ Skeleton Code (Pure)

#include <cstdio>
constexpr int LM = 10;

int A[LM] = { 5,2,7,1,3,8,4,6,10,9 };
int trr[LM];

void MergeSort(int *arr, int s, int e) {
	if(s>=e) return;
	int m=(s+e)/2, i=s, j=m+1, k=s;
	
	MergeSort(arr,s,m), MergeSort(arr,m+1,e);
	
	while(i<=m && j<=e) {
	    if(arr[j] < arr[i]) trr[k++] = arr[j++];
	    else trr[k++] = arr[i++];
	}
	
	while(i<=m) trr[k++] = arr[i++];
	while(j<=e) trr[k++] = arr[j++];

    for(i=s; i<=e; i++) arr[i] = trr[i];
}

int main() {
    for(int i=0; i<LM; i++) printf("%d ", A[i]); // 5 2 7 1 3 8 4 6 10 9 
    puts("");
    
    MergeSort(A, 0, LM-1);
    
    for(int i=0; i<LM; i++) printf("%d ", A[i]); // 1 2 3 4 5 6 7 8 9 10 
    puts("");
    
    return 0;   
}

Counting Sort

계수 정렬(Counting Sort)는 각 항목의 발생 횟수를 계산하여 정렬하는 방식으로, 작은 정수를 정렬할 때 유용하다. 비교 정렬 알고리즘의 하한은 $O(n \log n)$으로 알려져 있으나 입력된 자료의 원소가 제한적인 성질(원소의 최대값 k가 $-O(n) \sim O(n)$ 범위 내 존재해야 함)을 만족하는 경우 계수 정렬은 $O(n)$ 정렬이 가능하다. 계수 정렬은 개수를 셀 배열과 정렬된 결과가 저장될 배열이 추가로 필요한 단점이 존재한다.

C++ Skeleton Code (Pure)

#include <cstdio>
constexpr int N = 10;

int A[N] = { 1,4,3,2,2,4,3,5,3,1 };
int sortedA[N];
int cnt[N];
int K = 6; // 정렬할 값의 상한

void CountingSort(int A[], int n){
    int i;
    for(i=0; i<K; i++) cnt[i]=0;            // 카운팅 배열 초기화
    for(i=0; i<n; i++) cnt[A[i]]++;         // 숫자들 카운팅
    for(i=1; i<K; i++) cnt[i] += cnt[i-1];  // 누적합 구하기
    for(i=n-1; i>=0; i--) 
        sortedA[--cnt[A[i]]] = A[i];
}


int main() {
    
    for(int i=0; i<N; i++) printf("%d ", A[i]);  // 1 4 3 2 2 4 3 5 3 1 
    puts("");
    
    CountingSort(A, N);
    
    for(int i=0; i<N; i++) printf("%d ", sortedA[i]); // 1 1 2 2 3 3 3 4 4 5 
    puts("");
    
    return 0;   
}

 

Radix Sort

기수 정렬(Radix Sort)는 자릿수별로 데이터를 분류하여 정렬하는 방식으로, 숫자나 문자열 정렬에 효과적이다. 기수 정렬 역시 계수 정렬과 유사하게 입력된 자료의 원소가 제한적인 성질을 만족하는 경우 더 빠른 정렬이 가능하다. 기수 정렬은 원소의 자리수가 $d$ 자리 이하인 경우 $O(d N)$의 시간복잡도를 가진다. 또한 음수를 포함한 정수를 정렬할 수 있다.

 

낮은 자리부터 정렬하고 정렬된 순서를 유지하면서 보다 높은 자리를 정렬하는 과정에서 계수 정렬(counting sort)가 사용된다. 자리수 별로 정렬할 때 몫과 나머지 연산을 사용하는데 이 때 10진수 기법을 사용하면 효율성이 떨어지므로 2의 제곱수 진법을 사용한다. 일반적으로 $256(=2^8)$ 진법을 사용하며 자리수 $d=4$가 된다.

 

C++ Skeleton Code (Pure)

#include <cstdio>
constexpr int N = 10;
constexpr int EXP = 8;
constexpr int MOD = (1<<EXP);       // 256진법
constexpr int MASK = MOD-1;

int A[N] = { 1,4,3,2,2,4,3,5,3,1 };
int B[N];
int cnt[MOD];

void RadixSort() {
    int i, j;
    int *ap=A, *bp=B, *tp;                    
    
    for(i=0; i<32; i+=EXP) {                        // 32비트에 대하여 8비트씩 연산
        for(j=0; j<MOD; j++) cnt[j]=0;            
        for(j=0; j<N; j++) cnt[(ap[j]>>i)&MASK]++; // ap[j]를 2^i로 나눈 몫을 256으로 나눈
        for(j=1; j<MOD; j++) cnt[j] += cnt[j-1];   // 나머지이므로 (0~255) 값이 나옴
        for(j=N-1; j>=0; j--) 
            bp[--cnt[(ap[j]>>i)&MASK]] = ap[j];
            
        tp=ap, ap=bp, bp=tp;  // 배열 swap
    }
}


int main() {
    for(int i=0; i<N; i++) printf("%d ", A[i]);  // 1 4 3 2 2 4 3 5 3 1 
    puts("");
    
    RadixSort();
    
    for(int i=0; i<N; i++) printf("%d ", A[i]); // 1 1 2 2 3 3 3 4 4 5 
    puts("");
    
    return 0;   
}

 

Search

Binary Search

이진 탐색(Binary Search)는 정렬된 리스트에서 중간값을 기준으로 탐색 범위를 반으로 줄여가며 원하는 값을 찾는 방법이다.

 

DFS

깊이 우선 탐색(Depth First Search, DFS)은 그래프의 깊은 부분을 우선적으로 탐색하는 방식이다.

• 시간복잡도: $O(V+E)$, $V$는 정점의 개수, $E$는 간선의 개수
• 공간복잡도: $O(V)$

 

C++ Skeleton Code (Pure)

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
constexpr int LM = 1005;

vector<vector<int>> A;
int visited[LM];

void DFS(int s) {
    if(visited[s]) return;  // base condition
    
    visited[s] = 1;
    printf("%d ", s);
    
    for(int i = 0; i < A[s].size(); i++) { 
        int next = A[s][i];
        if(!visited[next]) DFS(next);
    }
}

int main() {
    A = {          // 그래프 표현 (인접 리스트)
        {1, 2},    // 정점 0에 인접한 정점: 1, 2
        {0, 3, 4}, // 정점 1에 인접한 정점: 0, 3, 4
        {0, 4},    // 정점 2에 인접한 정점: 0, 4
        {1, 5},    // 정점 3에 인접한 정점: 1, 5
        {1, 2},    // 정점 4에 인접한 정점: 1, 2
        {3}        // 정점 5에 인접한 정점: 3
    };
    
    memset(visited, 0, sizeof(visited));
    
    DFS(0);      // 0 1 3 5 4 2  

    return 0;
}

C++ Skeleton Code (w/ STL)

#include <cstdio>
#include <cstring>
#include <vector>
#include <stack>
using namespace std;

constexpr int LM = 1005;

vector<vector<int>> A;
int visited[LM];

void DFS(int start) {
    stack<int> st;
    st.push(start);
    visited[start] = 1;

    while (!st.empty()) {
        int current = st.top();
        st.pop();

        printf("%d ", current);

        // 현재 노드에 인접한 노드를 스택에 추가
        // 인접한 노드를 거꾸로 탐색하여 스택에 넣어줌으로써, 재귀 버전의 탐색 순서를 유지
        for (int i = A[current].size() - 1; i >= 0; i--) {
            int next = A[current][i];
            if (visited[next]) continue;
            visited[next] = 1;
            st.push(next);    
        }
    }
}

int main() {
    A = {          // 그래프 표현 (인접 리스트)
        {1, 2},    // 정점 0에 인접한 정점: 1, 2
        {0, 3, 4}, // 정점 1에 인접한 정점: 0, 3, 4
        {0, 4},    // 정점 2에 인접한 정점: 0, 4
        {1, 5},    // 정점 3에 인접한 정점: 1, 5
        {1, 2},    // 정점 4에 인접한 정점: 1, 2
        {3}        // 정점 5에 인접한 정점: 3
    };
    
    memset(visited, 0, sizeof(visited));
    
    DFS(0);  // 시작 정점을 스택에 넣고 DFS 시작

    return 0;
}

 

BFS

너비 우선 탐색(Breadth First Search, BFS)은 가까운 노드를 먼저 탐색하며, 레벨 별로 탐색하는 방식이다.

• 시간복잡도: $O(V+E)$, $V$는 정점의 개수, $E$는 간선의 개수
• 공간복잡도: $O(V)$

C++ Skeleton Code (w/ STL)

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
constexpr int LM = 1005;

vector<vector<int>> A;

int que[LM*LM];
int visited[LM];
int fr, re;

void BFS(int s) {
    fr = re = 0;

    que[re++] = s;
    visited[s] = 1; // 시작 정점을 큐에 넣고 방문 처리

    while (fr < re) {
        int cur = que[fr++];
        
        printf("%d ", cur);

        for (int i = 0; i < A[cur].size(); i++) { // 현재 정점에 인접한 모든 정점을 탐색
            int next = A[cur][i];
            if (visited[next])  continue;  // 이미 방문한 정점은 스킵 
            
            que[re++] = next;                  // 아직 방문하지 않은 정점이라면 큐에 넣고
            visited[next] = 1;             // 방문 처리
        }
    }
    puts("");
}

int main() {
    A = {          // 그래프 표현 (인접 리스트)
        {1, 2},    // 정점 0에 인접한 정점: 1, 2
        {0, 3, 4}, // 정점 1에 인접한 정점: 0, 3, 4
        {0, 4},    // 정점 2에 인접한 정점: 0, 4
        {1, 5},    // 정점 3에 인접한 정점: 1, 5
        {1, 2},    // 정점 4에 인접한 정점: 1, 2
        {3}        // 정점 5에 인접한 정점: 3
    };
    
    memset(visited,0, sizeof(visited));
    
    BFS(0);     // 0 1 2 3 4 5 

    return 0;
}

C++ Skeleton Code (Pure)

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
constexpr int LM = 1005;

vector<vector<int>> A;

int que[LM*LM];
int visited[LM];
int fr, re;

void BFS(int s) {
    fr = re = 0;

    que[re++] = s;
    visited[s] = 1; // 시작 정점을 큐에 넣고 방문 처리

    while (fr < re) {
        int cur = que[fr++];
        
        printf("%d ", cur);

        for (int i = 0; i < A[cur].size(); i++) { // 현재 정점에 인접한 모든 정점을 탐색
            int next = A[cur][i];
            if (visited[next])  continue;  // 이미 방문한 정점은 스킵 
            
            que[re++] = next;                  // 아직 방문하지 않은 정점이라면 큐에 넣고
            visited[next] = 1;             // 방문 처리
        }
    }
    puts("");
}

int main() {
    A = {          // 그래프 표현 (인접 리스트)
        {1, 2},    // 정점 0에 인접한 정점: 1, 2
        {0, 3, 4}, // 정점 1에 인접한 정점: 0, 3, 4
        {0, 4},    // 정점 2에 인접한 정점: 0, 4
        {1, 5},    // 정점 3에 인접한 정점: 1, 5
        {1, 2},    // 정점 4에 인접한 정점: 1, 2
        {3}        // 정점 5에 인접한 정점: 3
    };
    
    memset(visited,0, sizeof(visited));
    
    BFS(0);     // 0 1 2 3 4 5 

    return 0;
}

 

 

Dynamic Programming

동적계획법(Dynamic Programming)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 이 결과를 저장하여 재사용함으로써 전체 문제의 효율적인 해결을 가능하게 한다. 최적 부분 구조와 중복되는 하위 문제를 가진 경우에 유용하다.

 

Permutation 

순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다.

C++ Skeleton Code (w/ STL)

#include <algorithm>
#include <cstdio>
using namespace std;
constexpr int LM=10005;
int num[LM] = {0};
int main(int argc, char **argv){
  num[0]=1;
  num[1]=2;
  num[2]=3;
  do{
    for(int i=0;i<3;i++)
      printf("%d ", num[i]);
    printf("\n");
  }while(next_permutation(num, num+3));
  return 0;
}

 

C++ Skeleton Code (Pure)

#include <algorithm>
#include <cstdio>
using namespace std;

int num[3]={0};
int N=3;

int main(int argc, char **argv){
  num[0]=1, num[1]=2, num[2]=3;

  while(1) {
    for(int i=0;i<N;i++)
      printf("%d ", num[i]);
    printf("\n");

    bool last_perm=true;       // 마지막 순열인지 체크

    for(int i=N-1;i>0;i--){    // 입력된 순열의 마지막 원소부터 검사
      if(num[i-1] < num[i]){  // 왼쪽 원소(기준) < 오른쪽 원소
        int idx=i;          // 교환할 원소의 인덱스
        for(int j=N-1; j>=i; j--)
          if(num[i-1] < num[j] && num[j] < num[idx])  // 기준 원소보다 크면서 제일 작은 원소
            idx=j;

        int tmp = num[idx];   // 교환
        num[idx] = num[i-1];
        num[i-1] = tmp;

        sort(num+i, num+N);   // 기준 원소 우측 오름차순 정렬

        last_perm=false;
        break;
      }
    } 
    if(last_perm) break;
  }
}

Combination

조합은 집합에서 일부 원소를 취해 부분 집합을 만드는 연산이다.

 

 

Greedy

탐욕(Greedy) 알고리즘은 매 선택에서 지역적으로 최적인 선택을 함으로써 최종적인 해답의 최적성을 보장하는 알고리즘이다. 문제에 따라 최적해를 보장하지 않을 수도 있다.

 

Dijkstra

다익스트라(Dijkstra) 알고리즘은 가중치가 있는 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘이다. 음수 가중치를 가진 간선이 없을 때 사용할 수 있다. 알고리즘은 출발점에서 각 정점까지의 최단 거리를 저장하면서, 가장 가까운 정점을 선택하고, 이 정점을 통해 다른 정점으로 가는 거리를 업데이트하는 과정을 반복한다.

 

Floyd Warshall

플로이드-워셜(Floyd Warshall) 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 동적 프로그래밍을 기반으로 하며, 그래프의 모든 정점을 거쳐 가는 경로를 고려하여 최단 거리를 계산한다. 이는 각 정점을 거쳐 가는 모든 경로의 최단 거리를 행렬로 저장하고 업데이트하는 방식으로 작동한다.

 

Plane Sweeping

플레인 스위핑(Plane Sweeping) 알고리즘은 기하학적 문제, 특히 여러 개의 객체(예: 직사각형, 선분 등)가 주어졌을 때 이들 사이의 관계(예: 교차, 면적 계산 등)를 효율적으로 찾는 데 사용된다. 스위핑 라인(Sweep Line)을 가상으로 그려가며, 이 라인이 객체들을 스캔하면서 필요한 계산을 수행한다.

 

Minimum Spanning Tree

최소 비용 신장트리(Minimum Spanning Tree, MST)는 그래프의 모든 노드를 최소의 연결 비용으로 연결하는 부분 그래프(트리)이다. 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘은 MST를 찾는 데 널리 사용되는 알고리즘이다. 이들은 각각 탐욕적 방법을 사용하여 전체 그래프에서 최소 비용의 에지들을 선택하여 MST를 구성한다.

 

Topological Sorting

위상 정렬(Topological Sorting)은 유향 비순환 그래프(DAG, Directed Acyclic Graph)의 모든 노드를 방향성에 위배되지 않도록 순서대로 나열하는 정렬 방법이다. 이는 주로 의존성이 있는 여러 작업을 수행해야 할 때 그 순서를 결정하는 데 사용된다.

 

Maximum Flow

최대 유량(Maximum Flow) 문제는 네트워크 플로우 이론에서 주어진 네트워크의 두 노드 사이(일반적으로 소스와 싱크라고 함)를 통해 흐를 수 있는 최대의 유량을 찾는 문제이다. 포드-풀커슨(Ford-Fulkerson) 알고리즘과 에드몬드-카프(Edmonds-Karp) 알고리즘 등이 이 문제를 해결하는 데 사용된다.

 

Bipartite Match

이분 매칭(Bipartite March) 문제는 이분 그래프에서 서로 다른 두 부분 집합의 노드를 매칭하는 최대 집합을 찾는 문제이다. 이는 예를 들어, 일자리 할당, 자원 분배 등 다양한 최적화 문제에서 중요한 역할을 한다. 홉크로프트-카프(Hopcroft-Karp) 알고리즘은 이분 매칭 문제를 효율적으로 해결하는 알고리즘 중 하나이다.

 

 

References

[1] (Blog) 알고리즘 문제풀이(PS) 시작하기 - plzrun

[2] (Blog) 내가 문제풀이를 연습하는 방법 - koosaga

[3] (Blog) 코드포스 블루, 퍼플 달성 후기 및 일지 & 공부법 - Rebro

[4] (Blog) PS를 공부하는 방법 (How to study Problem Solving?) - subinium

[5] (Site) Baejoon Online Judge

[6] (Site) JungOl

[7] (Site) SW Expert Academy

[8] (Blog) BaaaaaaaarkingDog의 강좌/실전 알고리즘

[9] (Youtube) BaaaaaaaarkingDog의 강좌/실전 알고리즘