본문 바로가기
Coding

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

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

 

NOMENCLATURE

  • $V$ : 노드(Node, Vertex)의 개수 
  • $E$ : 간선(Edge)의 개수
  • $n$ : 원소의 개수 (또는 $N$)
  • $\log n$ : 밑이 2인 $\log_2 n$을 간략하게 표기
  • 노드 = 정점
  • 간선 = 엣지

 

Algorithm

Math

Prime number

소수(prime number)는 1과 자기 자신으로만 나누어지는 수를 말한다. 즉, 임의의 수를 약분했을 때 약수가 2개이면 해당 수를 소수라고 한다.

  • 현재 숫자 n이 1 이외에 다른 수로 나눠지는지 확인함으로써 소수 판별
    • 시간복잡도: $O(\sqrt{n})$
더보기 
bool isPrime(int n) {
  if(n==1) return 0;
  for(int i=2; i*i<=n; i++){    // search until sqrt(n)
    if(n % i == 0) return 0;
  }
  return 1;
}
  • 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하여 소수가 아닌 값들을 마킹함으로써 소수 판별
    • 시간복잡도: $O(n \log (\log n))$
더보기 
#include<bits/stdc++.h>

constexpr int N = 1005;
bool is_prime[N];

// Pure
void sieve() {
  memset(is_prime, 1, sizeof(is_prime));
  is_prime[1] = false;
  for(int i=2; i*i<=N; i++){
    if(is_prime[i] == false) continue;
    for(int j=i*i; j<=N; j+=i) {
      is_prime[j] = false;
    }
  }
}

int main() {
  sieve();

  for(int i=2; i<=N; i++){
    if(is_prime[i]) {    // check if 'i' is prime number
      printf("%d ", i);
    }
  }puts("");
}
더보기 
#include<bits/stdc++.h>
using namespace std;

int N = 1005;
vector<int> primes;

// STL
void sieve() {
  vector<bool> state(N+1, true);
  state[1] = false;
  for(int i=2; i*i<=N; i++){
    if(!state[i]) continue;
    for(int j=i*i; j<=N; j+=i)
      state[j] = false;
  }
  for(int i=2; i<=N; i++) {
    if(state[i]) primes.push_back(i);
  }
}

int main() {
  sieve();

  for(int i=2; i<=N; i++){
    // check if 'i' is prime number
    if(find(primes.begin(), primes.end(), i) != primes.end()) {  
      printf("%d ", i);
    }
  } puts("");
}

 

Prime factorization

소인수분해(prime factorization)은 정수를 소수의 곱으로 나타내는 것을 의미한다. 모든 자연수는 소인수분해하는 방법이 딱 한가지만 존재하므로 유일한 소인수분해 값을 얻을 수 있다.

  • C++ Skeleton Code (Pure)
    • 시간복잡도: $O(\sqrt{n})$
더보기 
#include <bits/stdc++.h>
using namespace std;

// O(sqrt(n))
void primeFactorization(int n) {
  for(int i=2; i*i<=n; i++){
    while(n%i == 0) {
      printf("%d ", i);
      n /= i;
    }
  }
  if(n != 1) printf("%d ", n);
  puts("");
}

int main(int argc, char **argv){
  int N;
  scanf("%d",&N);  // 1100

  primeFactorization(N);  // 2 2 5 5 11
}
  • 에라토스테네스의 체를 활용한 빠른 소인수분해
    • 시간복잡도: $O(\log n)$
더보기 
#include <bits/stdc++.h>
using namespace std;

const int LM = 1000005;

int minFactor[LM];  // minFactor[i] : i의 가장 작은 소인수(i가 소수인 경우는 자기 자신)

// 시간복잡도: O(nloglogn)
void eratosthenes2(int n) {
  // 초기화
  minFactor[0] = minFactor[1] = -1;
  for ( int i = 2; i <= n; i++ ) {
    minFactor[i] = i;
  }
  
  // 에라토스테네스의 체
  for ( int i = 2; i*i <= n; i++ ) 
    if ( minFactor[i] == i ) 
      for ( int j = i * i; j <= n; j += i ) 
        if ( minFactor[j] == j )        // 아직 약수를 본 적 없는 숫자인 경우 i를 써둔다
          minFactor[j] = i;
}

// 시간복잡도: O(logn)
vector<int> factor( int n ) {
  vector<int> ret;
  // n이 1이 될 때까지 가장 작은 소인수로 나누기를 반복한다
  while ( n > 1 ) {
    ret.push_back( minFactor[n] );
    n /= minFactor[n];
  }
  return ret;
}

int main( int argc, char **argv ) {
  int N;
  scanf("%d", &N);   // 1100

  eratosthenes2(N);
  vector<int> ret = factor(N);

  for(auto& e : ret) {
    printf("%d ", e);   // 2 2 5 5 11
  }
  puts("");
}

 

Divisor

약수(divisor)는 어떤 수를 나누어떨어지게 하는 수를 말한다. 예를 들어 $24$의 약수는 $[1, 2, 3, 4, 6, 8, 12, 24]$이다.

  • C++ Skeleton Code (w/ STL)
    • 시간복잡도 $O(\sqrt{n})$
더보기 
#include <bits/stdc++.h>
using namespace std;

// O(sqrt(n))
vector<int> divisor(int n){
  vector<int> div;
  for(int i=1; i*i <= n; i++){
    if(n % i == 0) div.push_back(i);
  }
  for(int j=(int)div.size()-1; j>=0; j--) {
    if(div[j]*div[j] == n) continue;
    div.push_back(n/div[j]);
  }
  return div;
}

int main(int argc, char **argv){
  int N;
  scanf("%d",&N); // 24

  vector<int> divs = divisor(N);

  for(auto x : divs) printf("%d ", x);    // 1 2 3 4 6 8 12 24
  puts("");
}

 

GCD

최대공약수(greatest common divisor)는 두 자연수의 공통된 약수 중 가장 큰 약수를 말한다. 유클리드 호제법을 사용하면 GCD를 빠르게 구할 수 있다.

  • 유클리드 호제법: 두 수 $a$, $b$에 대하여 $a$를 $b$로 나눈 나머지를 $r$이라고 하면 GCD($a,b$)=GCD($b,r$)이 성립한다
  • C++ Skeleton Code (Pure)
    • 시간복잡도: $O(\log(\min(a,b))$
더보기 
#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
  if(a==0) return b;
  return gcd(b%a, a);
}

int main(int argc, char **argv){
  int A,B;
  scanf("%d %d",&A, &B);  // 32, 6

  printf("%d\n", gcd(A, B));  // GCD(32,6) = 2
}

 

LCM

최소공배수(least common multiple)는 두 자연수의 공통된 배수 중 가장 작은 배수를 말한다. 

  • LCM($a,b$) = $(a\times b) / $ GCD($a,b$)가 성립한다 (원래 식은 $a\times b$ = GCD($a,b$) $\cdot$ LCM($a,b$))
  • C++ Skeleton Code (Pure)
    • 시간복잡도: $O(\log(\min(a,b))$
더보기 
#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
  if(a==0) return b;
  return gcd(b%a, a);
}

int lcm(int a, int b){
  return a / gcd(a,b)*b;
}

int main(int argc, char **argv){
  int A,B;
  scanf("%d %d",&A, &B);  // 32, 6

  printf("%d\n", lcm(A, B));  // LCM(32,6) = 96
}

 

Permutation 

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

  • 시간복잡도: $O(n! \times n)$ 
  • 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;
  }
}
  • 순열 $_nP_r$ 경우의 수를 구하는 예제 (C++)
더보기 
#include <bits/stdc++.h>

// nPr = n! / (n-r)!
// 시간복잡도 O(r)
long long permutation(int n, int r) {
  if (r > n) return 0;
  unsigned long long res = 1;
  for (int i = 0; i < r; ++i) {
    res *= (n - i);
  }
  return res;
}

int main() {
  int n = 10, r = 5;
  printf("%lld\n", permutation(n,r));  // 30240
}

 

Combination

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

  • 시간복잡도: $O( \ _nC_k \times n \ ) = O( (n! / (k!(n-k)!) ) \times n )$ 
  • C++ Skeleton Code (w/ STL)
더보기 
#include <bits/stdc++.h>
using namespace std;

int num[5] = {1,2,3,4,5};

int main(int argc, char **argv) {
  int n = 5;
  int k = 3;

  // Initialize mask with k 1's followed by n-k 0's
  int mask[5];
  memset(mask, 0, sizeof(mask));
  for(int i=0; i<k; i++){
    mask[i] = 1;
  }

  do {
    for (int i = 0; i < n; ++i) {
      if (mask[i])
        printf("%d ", num[i]);
    }
    printf("\n");
  } while (prev_permutation(mask, mask + n));

  // 1 2 3
  // 1 2 4
  // 1 2 5
  // 1 3 4
  // 1 3 5
  // 1 4 5
  // 2 3 4
  // 2 3 5
  // 2 4 5
  // 3 4 5
}
  • C++ Skeleton Code (Pure) #1
더보기 
#include <cstdio>
using namespace std;

int arr[5] = {1, 2, 3, 4, 5};
int n = 5, k = 3;

int main(int argc, char **argv) {
  int indices[3] = {0,1,2}; // Initialize indices for the first combination

  do {
    for (int i = 0; i < k; ++i)
      printf("%d ", arr[indices[i]]);
    printf("\n");

    int i = k - 1;
    while (i >= 0 && indices[i] == n - k + i)
      --i;

    if (i < 0) break; // All combinations generated

    ++indices[i];
    for (int j = i + 1; j < k; ++j)
      indices[j] = indices[j - 1] + 1;

  } while (1);
}
  • C++ Skeleton Code (Pure) #2
더보기 
#include <cstdio>
using namespace std;

int arr[5] = {1, 2, 3, 4, 5};
int sel[5];
int n = 5, k = 3;

void comb(int idx, int start) {
  if(idx == k) {
    for(int i = 0; i < k; i++) {
      printf("%d ", sel[i]);
    }
    puts("");

    return;
  }

  for(int i = start; i < n; i++) {
    sel[idx] = arr[i];
    comb(idx + 1, i + 1);
  }
}

int main(){
  comb(0, 0);
  return 0;
}
  • 조합 $_nC_r$ 경우의 수를 구하는 예제 (C++)
더보기 
#include <bits/stdc++.h>

using ll = long long;

const int LM=1005;
const int MOD=10007;

ll comb[LM][LM];

// O(nr)
void computeCombination() {
  // compute Comb 1 ~ LM in advance
  for(int i=1; i<LM; i++){
    comb[i][0] = comb[i][i] = 1;
    for(int j=1; j<i; j++){
      comb[i][j] = comb[i-1][j] + comb[i-1][j-1];    // DP, nCr = n-1Cr-1 + n-1Cr
    }
  }
}

int main(int argc, char **argv){
  int n=10,r=5;
  computeCombination();
  printf("%lld\n", comb[n][r]);  // 252
}

 

Recursion

재귀(recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 방식이다. 재귀로 문제를 푼다는 것은 귀납적인 방식으로 문제를 해결하겠다는 것과 동일하다. 올바른 재귀 함수는 반드시 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 하는데 이를 보통 base condition이라고 한다. 또한 모든 입력은 base condition으로 수렴해야 한다. 재귀는 반복문으로 구현했을 때와 비교하여 코드는 간결하지만 메모리와 시간 측면에서는 일반적으로 손해를 본다. 재귀는 분할 정복 알고리즘, 트리 탐색 등에 널리 사용된다.

  • 피보나치 수열을 재귀로 구하는 예제 (C++)
더보기 
#include <cstdio>

// recursive: O(1.618^n)
int fibonacci(int n) {
  if (n == 0 || n == 1) return 1;  // base case
  return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
  int n = 20; 
  for (int i = 0; i <= n; i++) {
    printf("%d ", fibonacci(i));  // 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946
  }
  puts("");
}

 

  • 하노이 탑을 재귀로 구하는 예제 (C++)
더보기 
#include <bits/stdc++.h>
using namespace std;

void hanoi(int from, int to, int n){
  if(n==1) { printf("%d %d\n",from,to); return; }

  int by = 6-from-to;

  hanoi(from, by, n-1);
  printf("%d %d\n", from,to);
  hanoi(by, to, n-1);
}

void hanoi2(int from, int by, int to, int n){
  if(n==1) { printf("%d %d\n", from, to); return; }

  hanoi2(from, to, by, n-1);                    // n-1개의 원반을 보조 기둥(by)로 이동
  printf("%d %d\n", from, to);                  // 가장 큰 원반을 목표 기둥(to)로 이동
  hanoi2(by, from, to, n-1);                    // n-1개의 원반을 목표 기둥(to)로 이동
}

int main(int argc, char **argv){
   int K; scanf("%d",&K);
   printf("%d\n", (1<<K)-1);

   hanoi(1, 3, K);
   // hanoi2(1, 2, 3, K);
}

 

Sort

Bubble sort

버블 정렬(bubble sort)는 인접한 두 원소를 비교하여 정렬하는 방식이다. 시간 복잡도가 높아 실제 PS에서는 잘 사용되지 않는다.

  • 시간복잡도: 평균/최악 $O(n^2)$, 최선(거의 정렬된 경우) $O(n)$
  • 공간복잡도: $O(1)$
  • C++ Skeleton Code (Pure)
더보기 
#include <cstdio>
constexpr int LM = 10;

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

void BubbleSort(int *arr, int s, int e) {
    for(int i = s; i < e; i++) {
        for(int j = s; j < e - (i - s); j++) {
            if(arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

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

    BubbleSort(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;
}

 

Insertion sort

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

  • 시간복잡도: 평균/최악 $O(n^2)$, 최선(거의 정렬된 경우) $O(n)$
  • 공간복잡도: $O(1)$
  • C++ Skeleton Code (Pure)
더보기 
#include <cstdio>
constexpr int LM = 10;

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


void InsertionSort(int *arr, int s, int e) {
    for(int i = s + 1; i <= e; i++) {           
        int key = arr[i];
        int j = i - 1;
        while(j >= s && arr[j] > key) {       
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;                     
    }
}

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

    InsertionSort(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;
}

 

Heap sort

힙(heap) 자료 구조를 사용하여 정렬하는 방식으로 최대 힙(max heap)을 구성한 후 힙의 루트부터 모든 원소를 꺼내서 재구성하면 오름차순으로 정렬된다.

  • 시간복잡도: 최악의 경우에도 $O(n \log n)$을 보장하며 추가 메모리 사용이 적은 편 (힙 구성 $O(n)$, $n$번에 걸쳐서 힙 재정렬 $O(\log n)$ 씩)
  • 공간복잡도: $O(1)$ (배열 내에서 힙을 구성하므로 추가 공간이 거의 필요 없음)
  • C++ Skeleton Code (Pure)
더보기 
#include <cstdio>

constexpr int NUM = 10;
constexpr int LM = 105;

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

int heap[LM];
int hn = 0;

void swap(int &a, int &b) { int t = a; a = b; b = t; }

void push(int nd) {
  heap[++hn] = nd;

  for (int c = hn; c > 1; c /= 2) {
    if (heap[c] > heap[c / 2]) {
      swap(heap[c], heap[c / 2]);
    }
    else {
      break;
    }
  }
}

void pop() {
  swap(heap[1], heap[hn--]);

  for (int c = 2; c <= hn; c *= 2) {
    if (c < hn && heap[c + 1] > heap[c]) {
      c++;
    }
    if (heap[c] > heap[c / 2]) {
      swap(heap[c], heap[c / 2]);
    }
    else {
      break;
    }
  }
}

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

  printf("\n");

  for(int i = 0; i < NUM; i++) { push(A[i]); }
  while (hn > 1) {   pop();   }

  for(int i = 1; i <= NUM; i++) printf("%d ", heap[i]); // 1 2 3 4 5 6 7 8 9 10
  printf("\n");
}

 

Quick sort

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

  • 시간복잡도: 평균 $O(n \log n)$, 최악 $O(n^2)$
  • 공간복잡도: 평균 $O(\log 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("");
    
    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) 
더보기 
// 실제 PS에서 STL 없이 정렬을 구현해야 한다면 퀵소트보다는 머지소트를 구현하는 것이 좋다
// 손구현은 피봇이나 여러 최적화 기법이 들어가있지 않기 때문에 최악의 경우 O(N^2)이 나올 수 있다
// 손구현은 참고용으로만 보는 것이 좋다
#include <bits/stdc++.h>
using namespace std;

const int LM = 100005;

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

void quickSort(int st, int en) { 
  if(en <= st+1) return;         // base case : 수열의 길이가 1 이하이면 함수 종료
  int pivot = A[st];             // 제일 앞의 것을 pivot으로 잡는다
  int l = st+1;                  
  int r = en-1;                  
  while(1){
    while(l <= r && A[l] <= pivot) l++;
    while(l <= r && A[r] >= pivot) r--;
    if(l > r) break; 
    swap(A[l], A[r]);
  }
  swap(A[st], A[r]);
  quickSort(st, r);
  quickSort(r+1, en);
}

int main() {
  quickSort(0, N);

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

 

Merge sort

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

  • 시간복잡도 : 평균/최악 동일하게 $O(n \log 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)$ 정렬이 가능하다. 계수 정렬은 개수를 셀 배열과 정렬된 결과가 저장될 배열이 추가로 필요한 단점이 존재한다.

  • 시간복잡도: $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$가 된다.

  • 시간복잡도 : $d$ 자리수 이하인 경우 $O(dn)$
  • 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)는 정렬된 리스트에서 중간값을 기준으로 탐색 범위를 반으로 줄여가며 원하는 값을 찾는 방법이다. 이진 탐색을 수행하기 전 데이터는 오름차순으로 정렬되어 있어야 한다.

  • 시간복잡도: $O(\log n)$
  • C++ Skeleton Code (w/ STL)
더보기 
#include <cstdio>
#include <algorithm>

constexpr int LM = 1005;

int A[LM];
int N;

int main() {
  N = 10;
  A[0] = 5; A[1] = 2; A[2] = 7; A[3] = 1; A[4] = 3; 
  A[5] = 9; A[6] = 4; A[7] = 6; A[8] = 10; A[9] = 9; // 5 2 7 1 3 9 4 6 10 9

  std::sort(A, A + N);                               // 1 2 3 4 5 6 7 8 9 10

  int ret = std::binary_search(A, A+N, 7);

  if(ret == 1) printf("found\n");
  else printf("not found\n");
}
  • C++ Skeleton Code (Pure)
더보기 
#include <cstdio>
#include <algorithm>

constexpr int LM = 1005;

int A[LM];
int N;

int binarySearch(int target) {
  int l = 0;
  int r = N-1;

  while (l <= r) {
    int m = (l+r) / 2;

    if (A[m] == target) return 1;  // 찾은 경우

    if (A[m] < target) l = m + 1;
    else r = m - 1;
  }

  return 0; // 찾지 못한 경우
}

int main() {
  N = 10;
  A[0] = 5; A[1] = 2; A[2] = 7; A[3] = 1; A[4] = 3; 
  A[5] = 9; A[6] = 4; A[7] = 6; A[8] = 10; A[9] = 9; // 5 2 7 1 3 9 4 6 10 9

  std::sort(A, A + N);                               // 1 2 3 4 5 6 7 8 9 10

  int ret = binarySearch(7);

  if(ret == 1) printf("found\n");
  else printf("not found\n");
}

 

Parametric search

매개변수 탐색(parametric search)는 조건을 만족하는 최소/최대값을 구하는 최적화 문제를 결정 문제로 변환하여 이분 탐색을 수행하는 방법을 말한다.

  • BOJ 1654 랜선 자르기
  • (최적화 문제) N개를 만들 수 있는 랜선의 최대 길이 X는? (Maximize X, subject to N)
  • (결정 문제) 랜선의 길이가 X일 때 랜선이 N개 이상인가? (Yes or No)
더보기 
// 랜선 자르기 boj.kr/1654
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int LM = 10005;

int N,K;
int A[LM];

// Parametric search
bool solve(ll x){
	ll cur = 0;
	for(int i=0;i<K;i++) 
		cur += A[i]/x;
	return cur >= N;
}

int main(int argc, char **argv){
	scanf("%d %d",&K,&N);
	for(int i=0;i<K;i++) 
		scanf("%d", &A[i]);

	ll st = 1;
	ll en = 0x7fffffff;  // 2^31 - 1

	while(st < en) {
		ll m = (st+en+1)/2;
		if(solve(m)) st = m;
		else en = m-1;
	}

	printf("%lld\n", st);
}

 

DFS (Depth-First Search)

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

  • 시간복잡도: $O(V+E)$
  • 공간복잡도: $O(V)$
  • 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;
}
  • 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;
}

 

 

BFS (Breadth-First Search)

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

  • 시간복잡도: $O(V+E)$
  • 공간복잡도: $O(V)$
  • C++ Skeleton Code (w/ STL)
더보기 
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
constexpr int LM = 1005;

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

void BFS(int s) {
  q.push(s);
  visited[s] = 1; // 시작 정점을 큐에 넣고 방문 처리

  while (!q.empty()) {
    int cur = q.front(); 
    q.pop();

    printf("%d ", cur);

    for (int i = 0; i < A[cur].size(); i++) { // 현재 정점에 인접한 모든 정점을 탐색
      int next = A[cur][i];
      if (visited[next])  continue;  // 이미 방문한 정점은 스킵

      q.push(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;
}

 

Two pointers

투 포인터(two pointers) 알고리즘은 배열에서 원래 이중 for문으로 $O(n^2)$에 처리되는 작업을 2개의 포인터의 움직임으로 $O(n)$에 해결하는 알고리즘을 말한다.

  • 시간복잡도: $O(n)$
  • C++ Skeleton Code (Pure)
더보기 
// 수 고르기 boj.kr/2230 
#include <bits/stdc++.h>
using namespace std;

constexpr int LM = 100'005;
constexpr int INF = 0x7fffffff;

int N,M;
int A[LM];

int main(int argc, char **argv){
	scanf("%d%d",&N, &M);

	for(int i=0; i<N; i++){
		scanf("%d", &A[i]);
	}

	sort(A, A+N);

	int ans = INF;
	
	// Two pointers
	int en = 0;
	for(int st=0; st<N; st++){
		while(en < N && A[en] - A[st] < M) en++;
		if(en == N) break;  // en이 범위를 벗어날 시 종료
		ans = min(ans, A[en] - A[st]);
	}

	printf("%d\n", ans);
}

 

Divide and conquer

분할정복(divide and conquer)은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고 각 부분 문제의 답으로 전체 문제의 답을 계산하는 알고리즘을 말한다. 분할 정복이 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. 분할정복은 많은 경우 같은 작업을 더 빠르게 처리할 수 있다. 

  • 1+2+...+n까지의 합을 정복분할로 푸는 예제 (C++) 
더보기 
#include <bits/stdc++.h>
using ll = long long;

// 시간복잡도 O(log n)
ll fastSum(int n){
  if(n==1) return 1;

  if(n%2 == 1) return fastSum(n-1) + n;
  else  return 2*fastSum(n/2) + (n/2)*(n/2);
}

int main(int argc, char **argv){
  printf("%lld\n", fastSum(9651));   // 46575726
}
  • 정방행렬의 거듭제곱을 정복분할로 푸는 예제 (C++) 
더보기 
#include <bits/stdc++.h>
using namespace std;

class SquareMatrix {
  public:
    vector<vector<long long>> mat;
    int n;
    SquareMatrix(int n) : n(n), mat(n, vector<long long>(n, 0)) {}
    SquareMatrix(const vector<vector<long long>>& arr)
      : n((int)arr.size()), mat(arr) {}

    int size() const { return n; } // 행렬 크기 반환

    SquareMatrix operator*(const SquareMatrix &r) const {
      SquareMatrix ret(n);
      for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
          long long sum = 0;
          for(int k=0; k<n; k++){
            sum += mat[i][k] * r.mat[k][j];
          }
          ret.mat[i][j] = sum;
        }
      }
      return ret;
    }
};

SquareMatrix identity(int n){
  SquareMatrix I(n);
  for(int i=0; i<n; i++){
    I.mat[i][i] = 1;
  }
  return I;
}

// 분할정복으로 행렬 거듭제곱
// 시간복잡도: O(n^3 log m),  n: 행렬 크기, m: 거듭제곱 횟수
// 분할정복 안 쓴 경우 O(n^3 m)
SquareMatrix pow(const SquareMatrix& A, int m) {
  if(m == 0) return identity(A.size());
  if(m % 2 > 0) return pow(A, m - 1) * A;
  SquareMatrix half = pow(A, m / 2);
  return half * half;
}

int main(){
  SquareMatrix M({{1,2},{3,4}}); // 2x2 행렬 예시
  int exponent = 5;

  SquareMatrix result = pow(M, exponent);

  for(int i=0; i<result.size(); i++){
    for(int j=0; j<result.size(); j++){
      cout << result.mat[i][j] << " ";
    }
    cout << "\n";
  }
}
  • 두 큰 정수의 곱셈을 정복분할로 푸는 예제 (C++) (a.k.a 카라츠바 알고리즘) 
더보기 
#include <bits/stdc++.h>
using namespace std;

// 카라츠바 시간복잡도: O(n^log3) ~= O(n^1.585)
// 단순히 두 큰 수를 곱하는 O(n^2)보다 훨씬 적은 곱셈을 필요로 한다

// num[]의 자리수 올림을 처리한다
void normalize(vector<int>& num){
    num.push_back(0);

    // 자리수 올림 처리
    for(int i=0; i<num.size()-1; i++){
        if(num[i] < 0) {
            int borrow = (abs(num[i]) + 9) / 10;
            num[i+1] -= borrow;
            num[i] += borrow * 10;
        }
        else {
            num[i+1] += num[i] / 10;
            num[i] %= 10;
        }
    }

    while(num.size() > 1 && num.back() == 0)
        num.pop_back();
}

// 두 긴 자연수의 곱을 반환한다
// 각 배열에는 각 수의 자리수가 1의 자리에서부터 시작해 저장되어있다
vector<int> multiply(const vector<int>& a, const vector<int>& b) {
    vector<int> c(a.size() + b.size() + 1, 0);
    for(int i=0; i<a.size(); i++){
        for(int j=0; j<b.size(); j++){
            c[i+j] += a[i] * b[j];
        }
    }
    normalize(c);
    return c;
}

// a += b * (10^k)
void addTo(vector<int>& a, const vector<int>& b, int k) {
    // Ensure a has enough size to accommodate b shifted by k
    int sizeNeeded = max((int)a.size(), (int)(b.size() + k));
    if(a.size() < sizeNeeded) {
        a.resize(sizeNeeded, 0);
    }
    // Digit-wise addition
    for(int i=0; i<b.size(); i++){
        a[i + k] += b[i];
    }
    normalize(a);
}

// a -= b
void subFrom(vector<int>& a, const vector<int>& b) {
    // Subtract b from a
    for(int i=0; i<b.size(); i++){
        a[i] -= b[i];
    }
    normalize(a);
}

vector<int> karatsuba(const vector<int>& a, const vector<int>& b) {
    int an = a.size(), bn = b.size();
    // a가 b보다 작으면 swap
    if(an < bn) return karatsuba(b,a);

    if(an == 0 || bn == 0) 
        return vector<int>();

    // 작은 크기에서는 일반 곱으로 계산
    if(an <= 50) 
        return multiply(a,b);

    int half = an / 2;

    // a, b를 절반으로 분할
    vector<int> a0(a.begin(), a.begin() + half);
    vector<int> a1(a.begin() + half, a.end());
    vector<int> b0(b.begin(), b.begin() + min<int>(b.size(), half));
    vector<int> b1(b.begin() + min<int>(b.size(), half), b.end());

    // 재귀적으로 계산
    vector<int> z2 = karatsuba(a1, b1);
    vector<int> z0 = karatsuba(a0, b0);

    // (a0 + a1)*(b0 + b1)를 계산
    addTo(a0, a1, 0);  // a0 = a0 + a1
    addTo(b0, b1, 0);  // b0 = b0 + b1
    vector<int> z1 = karatsuba(a0, b0);
    
    // z1 = z1 - z0 - z2
    subFrom(z1, z0);
    subFrom(z1, z2);

    // 결과를 ret에 합치기
    vector<int> ret;
    // 시작은 0으로 아무것도 없는 상태
    addTo(ret, z0, 0);
    addTo(ret, z1, half);
    addTo(ret, z2, half + half);

    return ret;
}

int main(){
    string s1, s2;
		s1 = "1234";
		s2 = "5678";

    vector<int> a, b;
    for(int i = s1.size()-1; i >= 0; i--){
        a.push_back(s1[i] - '0');
    }
    for(int i = s2.size()-1; i >= 0; i--){
        b.push_back(s2[i] - '0');
    }

    // Karatsuba로 곱셈
    vector<int> result = karatsuba(a, b);

    // Leading zero 제거 (최소 한 자리는 남겨둠)
    while(result.size() > 1 && result.back() == 0) {
        result.pop_back();
    }

    // 정상적인(가장 큰 자리부터) 순서로 출력
    for(int i = result.size()-1; i >= 0; i--){
        printf("%d", result[i]);
    }
    puts("");
}

 

Dynamic programming

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

  • 최대 증가 부분 수열(LIS)을 DP로 푸는 예제 (C++)
더보기 
#include <bits/stdc++.h>
using namespace std;

// 시간복잡도: O(n^2)
int N;
int dp[100];
vector<int> A;

int lis(int start) {
	int &ret = dp[start];
	if(ret != -1) return ret;

	// 항상 A[start]는 있기 때문에 길이는 최하 1
	ret = 1;
	for(int next = start+1; next<N; next++){
		if(A[start] < A[next])
			ret = max(ret, lis(next)+1);
	}

	return ret;
}

int main(int argc, char **argv){
	N = 8;

	memset(dp, -1, sizeof(dp));
	
	A.push_back(5);
	A.push_back(6);
	A.push_back(7);
	A.push_back(8);
	A.push_back(1);
	A.push_back(2);
	A.push_back(3);
	A.push_back(4);  // 5 6 7 8 1 2 3 4

	int ans=0;
	for(int i=0; i<N; i++)
		ans = max(ans, lis(i));

	printf("%d\n", ans);  // 4

}
  • 피보나치 수열을 DP로 구하는 예제 (C++)
더보기 
#include <cstdio>

// recursive : O(1.618^n)
// dp : O(n)
int fibonacci(int n){
  int f[50];
  f[0] = f[1] = 1;
  for(int i=2; i<=n; i++)
    f[i] = f[i-1] + f[i-2];
  return f[n];
}

int main() {
  printf("%d\n", fibonacci(20));  // 10946
}

 

Greedy

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

 

Dijkstra

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

  • C++ Skeleton Code (Pure)
    • 시간복잡도: $O(V^2 + E)$ : $V$가 20,000개가 넘으면 PS 알고리즘에서 보통 TLE 발생
더보기 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

#define X first
#define Y second

constexpr int LM = 20005;
constexpr int INF = 0x3f3f3f3f;

vector<pii> adj[LM];

bool fix[LM];
int d[LM];
int V, E, K;

void dijkstraNaive(int s) {
  fill(d, d + V + 1, INF);  // 최단거리 테이블 초기화
  d[s] = 0;

  while (1) {
    int idx = -1;
    for (int i = 1; i <= V; i++) {
      if (fix[i]) continue;
      if (idx == -1) idx = i;
      else if (d[i] < d[idx]) idx = i;
    }
    if (idx == -1 || d[idx] == INF) break;   // 더 이상 선택할 정점이 없으면

    fix[idx] = 1;  // 정점 idx 고정

    for(auto next : adj[idx]) 
      d[next.Y] = min(d[next.Y], d[idx] + next.X);
  }
}

int main() {
  V = 5;   // 노드
  E = 6;   // 엣지
  K = 1;   // 시작 정점 번호

  // u, v, w
  vector<tuple<int, int, int>> edges = {
    {5, 1, 1},
    {1, 2, 2},
    {1, 3, 3},
    {2, 3, 4},
    {2, 4, 5},
    {3, 4, 6}
  };

  for (auto [u, v, w] : edges) {
    adj[u].push_back({ w, v });
  }

  dijkstraNaive(K);

  for (int i = 1; i <= V; i++) {
    if (d[i] == INF) printf("INF\n");
    else printf("%d\n", d[i]);
  }
  // 0
  // 2
  // 3
  // 7
  // INF
}
  • C++ Skeleton Code (w/ STL)
    • 시간복잡도: $O(E \log V)$ : 일반적으로 PS에서 자주 사용되는 방식
더보기 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

#define X first
#define Y second

constexpr int LM = 20005;
constexpr int INF = 0x3f3f3f3f;

vector<pii> adj[LM];
priority_queue<pii, vector<pii>, greater<pii>> pq;

bool fix[LM];
int d[LM];
int V, E, K;

void dijkstra(int s) {
  fill(d, d + V + 1, INF);
  d[s] = 0;

  pq.push({ d[s], s });

  while (!pq.empty()) {
    auto cur = pq.top(); pq.pop();

    if (d[cur.Y] != cur.X) continue;

    for (auto next : adj[cur.Y]) {
      if (d[next.Y] <= d[cur.Y] + next.X) continue;
      d[next.Y] = d[cur.Y] + next.X;
      pq.push({ d[next.Y], next.Y });
    }
  }
}

int main() {
  V = 5;   // 노드
  E = 6;   // 엣지
  K = 1;   // 시작 정점 번호

  // u, v, w
  vector<tuple<int, int, int>> edges = {
    {5, 1, 1},
    {1, 2, 2},
    {1, 3, 3},
    {2, 3, 4},
    {2, 4, 5},
    {3, 4, 6}
  };

  for (auto [u, v, w] : edges) {
    adj[u].push_back({ w, v });
  }

  dijkstra(K);

  for (int i = 1; i <= V; i++) {
    if (d[i] == INF) printf("INF\n");
    else printf("%d\n", d[i]);
  }
  // 0
  // 2
  // 3
  // 7
  // INF
}
  • C++ Skeleton Code (w/ STL) (+ 경로 복원)
    • 시간복잡도: $O(E \log V)$ : 위와 동일
더보기 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

#define X first
#define Y second

const int LM = 1005;
const int INF = 1e9 + 10;

vector<pii> adj[LM];

int v, e, st, en;
int d[LM];
int pre[LM];

int main() {
  v = 5;    
  e = 8;

  // a,b,c (a,b : node) (c : cost)
  vector<tuple<int, int, int>> edges = {
    {1, 2, 2}, {1, 3, 3}, {1, 4, 1}, {1, 5, 10},
    {2, 4, 2}, {3, 4, 1}, {3, 5, 1}, {4, 5, 3}
  };

  st = 1;   // start
  en = 5;   // end

  fill(d, d + v + 1, INF);

  for (auto [u, v, w] : edges) {
    adj[u].push_back({w, v});
  }

  // Dijkstra
  priority_queue<pii, vector<pii>, greater<pii>> pq;
  d[st] = 0;
  pq.push({d[st], st});

  while (!pq.empty()) {
    auto cur = pq.top(); pq.pop();

    if (d[cur.Y] != cur.X) continue;
    for (auto next : adj[cur.Y]) {
      if (d[next.Y] <= d[cur.Y] + next.X) continue;

      d[next.Y] = d[cur.Y] + next.X;
      pq.push( { d[next.Y], next.Y } );
      pre[next.Y] = cur.Y;           // 경로 복원 
    }
  }

  // 도착 도시까지 최소 비용
  printf("%d\n", d[en]);

  // 경로 복원
  vector<int> path;
  int cur = en;

  while (cur != st) {
    path.push_back(cur);
    cur = pre[cur];
  }

  path.push_back(cur);
  reverse(path.begin(), path.end());
  printf("%d\n", path.size());           // 도시 개수
  for (auto x : path) printf("%d ", x);  // 최소 비용을 갖는 경로 
}

 

Floyd-Warshall

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

  • 시간복잡도: $O(V^3)$ 
  • C++ Skeleton Code (Pure) 
더보기 
#include <bits/stdc++.h>
using namespace std;

const int LM = 105;
const int INF = 0x3f3f3f3f;

int d[LM][LM];
int n, m;

int main() {
  n = 5;    // node
  m = 14;   // edge
	
	// a,b,c (a,b : node) (c : cost)
  vector<tuple<int, int, int>> edges = {
      {1, 2, 2}, {1, 3, 3}, {1, 4, 1}, {1, 5, 10},
      {2, 4, 2}, {3, 4, 1}, {3, 5, 1}, {4, 5, 3},
      {3, 5, 10}, {3, 1, 8}, {1, 4, 2}, {5, 1, 7},
      {3, 4, 2}, {5, 2, 4}
  };

  for (int i = 1; i <= n; i++) {
    fill(d[i], d[i] + n + 1, INF);
  }

  for (auto [a, b, c] : edges) {
    d[a][b] = min(d[a][b], c);
  }

  for (int i = 1; i <= n; i++)
    d[i][i] = 0;

  // Floyd-Warshall
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }

  // 최단 거리 테이블
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (d[i][j] == INF) printf("0 ");
      else printf("%d ", d[i][j]);
    }
    puts("");
  }
}
  • C++ Skeleton Code (Pure) (using dp) (+경로 복원)
더보기 
#include <bits/stdc++.h>
using namespace std;

const int LM = 105;
const int INF = 0x3f3f3f3f;

int d[LM][LM];
int nxt[LM][LM];
int n, m;

int main() {
  n = 5;   // node
  m = 14;  // edge

	// a,b,c (a,b : node) (c : cost)
  vector<tuple<int, int, int>> edges = {
      {1, 2, 2}, {1, 3, 3}, {1, 4, 1}, {1, 5, 10},
      {2, 4, 2}, {3, 4, 1}, {3, 5, 1}, {4, 5, 3},
      {3, 5, 10}, {3, 1, 8}, {1, 4, 2}, {5, 1, 7},
      {3, 4, 2}, {5, 2, 4}
  };

  for (int i = 1; i <= n; i++) {
    fill(d[i], d[i] + n + 1, INF);
  }

  for (auto [a, b, c] : edges) {
    d[a][b] = min(d[a][b], c);
    nxt[a][b] = b;
  }

  for (int i = 1; i <= n; i++)
    d[i][i] = 0;

  // Floyd-Warshall
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (d[i][k] + d[k][j] < d[i][j]) {
          d[i][j] = d[i][k] + d[k][j];
          nxt[i][j] = nxt[i][k];
        }
      }
    }
  }

	// 최단 거리 테이블
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (d[i][j] == INF) printf("0 ");
      else printf("%d ", d[i][j]);
    }
    puts("");
  }

	// 경로 복원
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (d[i][j] == 0 || d[i][j] == INF) {
        printf("0\n");
        continue;
      }

      vector<int> path;
      int st = i;
      while (st != j) {
        path.push_back(st);
        st = nxt[st][j];
      }
      path.push_back(j);
      printf("%d ", (int)path.size());
      for (auto x : path) printf("%d ", x);
      puts("");
    }
  }
}

 

Minimum spanning tree

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

  • 크루스칼 알고리즘 (C++) (using Union-find)
    • 시간복잡도: $O(E \log E)$
더보기 
#include <bits/stdc++.h>
using namespace std;
using tiii = tuple<int,int,int>;

vector<int> p(10005,-1);

int find(int x){
  if(p[x] < 0) return x;
  return p[x] = find(p[x]);
}

bool isDiffGroup(int a, int b){
  a = find(a); b = find(b);
  if(a == b) return 0;

  if(p[a] == p[b]) p[a]--;
  if(p[a] < p[b]) p[b] = a;
  else p[a] = b;

  return 1;
}

int main(void) {
  int v = 3, e = 3;

  // a,b,c (a,b : node) (c : cost)
  tiii edge[] = {
    {1, 2, 1},
    {2, 3, 2},
    {1, 3, 3}
  };

  sort(edge, edge + e);

  int cnt = 0;
  int ans = 0;

  // Kruskal algorithm (using isDiffGroup-find)
  for(int i = 0; i < e; i++){
    int a, b, cost;
    tie(cost, a, b) = edge[i];

    if(!isDiffGroup(a, b)) continue;

    ans += cost;  // MST 가중치의 합
    cnt++;
    if(cnt == v-1) break;
  }

  printf("%d\n", ans);  // 3
}
  • 프림 알고리즘 (C++) (using pq)
    • 시간복잡도: $O(E \log V)$
더보기 
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

constexpr int LM = 10005;

vector<pii> adj[LM];  // adj[i] = { cost , vertex_id }

bool chk[LM]; // chk[i] : i번째 정점이 MST에 속해있는가?
int cnt = 0;  // 현재 선택된 간선의 수

int main() {
	int v = 3, e = 3;

	// a,b,c (a,b : node) (c : cost)
	vector<tuple<int, int, int>> edges = {
		{1, 2, 1},
		{2, 3, 2},
		{1, 3, 3}
	};

	for (auto [a, b, cost] : edges) {
		adj[a].push_back({ cost, b });
		adj[b].push_back({ cost, a });
	}

	// Prim algorithm
	priority_queue<tiii, vector<tiii>, greater<tiii>> pq;   // pq[i] = { cost, vertex_id1, vertex_id2 }

	chk[1] = 1;

	for (auto nxt : adj[1]) {
		pq.push({ nxt.X, 1, nxt.Y });
	}

	int ans = 0;

	while (cnt < v - 1) {
		int cost, a, b;
		tie(cost, a, b) = pq.top(); pq.pop();

		if (chk[b]) continue;

		ans += cost;  // MST의 가중치 합
		chk[b] = 1;
		cnt++;

		for (auto nxt : adj[b]) {
			if (!chk[nxt.Y])
				pq.push({ nxt.X, b, nxt.Y });
		}
	}


	printf("%d\n", ans); // 3
}

 

Topological sort

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

  • C++ Skeleton Code (Pure)
더보기 
#include <bits/stdc++.h>
using namespace std;

const int LM = 32005;

vector<int> adj[LM];
int deg[LM];
int N;

int main() {
	// Nodes
  N = 4; 

  // Edges
  adj[4].push_back(2);
  deg[2]++;
  adj[3].push_back(1);
  deg[1]++;

  // Topological sort
  queue<int> q;
  vector<int> result;

  for (int i = 1; i <= N; i++)
    if (deg[i] == 0) q.push(i);

  while (!q.empty()) {
    int cur = q.front(); q.pop();
    result.push_back(cur);

    for (int nxt : adj[cur]) {
      deg[nxt]--;
      if (deg[nxt] == 0) q.push(nxt);
    }
  }

  for (auto x : result) printf("%d ", x);   // 3 4 1 2
}

 

KMP

KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색을 효율적으로 수행하는 알고리즘으로, 패턴 내에서 접두사와 접미사의 일치 정보를 활용하여 불필요한 비교를 줄인다. 전처리 연산을 통해 패턴의 "접두사 배열(longest prefix suffix, LPS 배열 또는 실패 함수)"을 생성하고, "탐색(search)" 연산을 수행할 때 이를 활용하여 중복된 비교 없이 빠르게 문자열 내에서 패턴을 찾는다. 일반적인 브루트포스 검색보다 빠르며, 대량의 텍스트 검색에서 효과적이다. KMP는 문자열 검색, DNA 서열 분석, 편집 거리 계산 등의 문제에서 활용된다.

  • $|N|$: 전체 문자열 $N$의 길이
  • $|M|$: 검색할 패턴 $M$의 길이
  • 시간복잡도: $O(|N|+|M|)$ (브루트포스 기반 문자열 매칭 : $O(|N| \times |M|)$)
  • C++ Skeleton Code (Pure)
더보기 
// 부분 문자열 boj.kr/16916
#include <bits/stdc++.h>
using namespace std;

// longest prefix suffix, LPS 배열(실패 함수) 구하기
vector<int> failure( string& s ) {
  vector<int> f( s.size() );
  int j = 0;

  for ( int i = 1; i < s.size(); i++ ) {
    while ( j > 0 && s[i] != s[j] ) j = f[j - 1];
    if ( s[i] == s[j] ) f[i] = ++j;
  }
  return f;
}

int main( int argc, char** argv ) {
  string s, p;
  cin >> s >> p;

	// KMP
  vector<int> f = failure( p );
  int j = 0;
  for ( int i = 0; i < s.size(); i++ ) {
    while ( j > 0 && s[i] != p[j] ) j = f[j - 1];
    if ( s[i] == p[j] ) j++;
    if ( j == p.size() ) {
      printf( "1\n" );
      return 0;
    }
  }
  printf( "0\n" );
}

 

Sqrt decomposition

제곱근 분할(sqrt decomposition)은 데이터를 $\sqrt{n}$ 크기의 블록으로 나누어, 구간 합이나 구간 최솟값·최댓값 등의 쿼리를 빠르게 처리하기 위한 알고리즘 기법이다. 각 블록에 대한 요약 정보를 미리 계산해 두고, 쿼리가 들어오면 필요한 블록만 참조하여 결과를 합산하거나 갱신한다. 이를 통해, 개별 원소를 전부 확인하지 않고도 효율적으로 쿼리에 응답할 수 있다. 일반적으로 쿼리와 업데이트가 모두 $O(\sqrt{n})$에 처리되어, 단순한 방법에 비해 성능을 크게 향상시킬 수 있다.

  • C++ Skeleton Code (Pure)
더보기 
// JUNGOL 1726 구간의 최대값1
// jungol.co.kr/problem/1726
// sqrt decomposition : [s, e) , update() 함수 구현
#include <cstdio>

const int LM = 50005;
const int MOD = 256;   // sqrt(50000) = 223.606
int N, Q;
int A[LM];             // 입력 데이터
int B[MOD + 1];        // 각 블록별 최대값

inline int min(int a, int b) { return a < b ? a : b; }
inline int max(int a, int b) { return a > b ? a : b; }

void update(int idx, int newVal) {
	int bn = idx / MOD;                       // idx가 속한 블록 번호
	int sn = bn * MOD, en = min(sn + MOD, N); // idx가 속한 블록의 시작과 끝 인덱스
	A[idx] = B[bn] = newVal;
	for (int i = sn; i < en; ++i)             // 블록 내 최대값 갱신
		B[bn] = max(B[bn], A[i]);
}

int query(int s, int e) {   // 구간 [s, e)에서 최대값 찾기
	int maxValue = A[s];
	// 1. 왼쪽 끝부분에서 블록 경계를 맞추기 위해 개별 비교
	while (s < e && s % MOD)
		maxValue = max(maxValue, A[s++]);

	// 2. 오른쪽 끝부분에서 블록 경계를 맞추기 위해 개별 비교
	while (s < e && e % MOD)
		maxValue = max(maxValue, A[--e]);

	// 3. 블록 단위로 최대값 비교
	for (s /= MOD, e /= MOD; s < e; s++)
		maxValue = max(maxValue, B[s]);

	return maxValue;
}

int main() {
	int s, e;
	scanf("%d %d", &N, &Q);
	for (int i = 0; i < N; ++i) {
		scanf("%d", A + i);
		update(i, A[i]);
	}

	for (int i = 0; i < Q; ++i) {
		scanf("%d %d", &s, &e);
		printf("%d\n", query(s - 1, e));
	}
}

 

Segment tree

세그먼트 트리(segment tree)는 배열 같은 선형 자료구조에 대해 구간 합이나 구간 최댓값·최솟값 등의 쿼리를 빠르게 처리하기 위해 트리 형태로 분할·구성하는 자료구조이다. 배열을 여러 구간으로 나누어 각 구간의 대표 정보를 저장하며, 쿼리가 들어오면 관련된 구간들만 빠르게 확인하여 결과를 합산하거나 갱신한다. 이를 통해 원소를 일일이 확인하지 않고도 구간 정보를 효율적으로 처리할 수 있으며, 쿼리와 업데이트 모두 일반적으로 $O(\log n)$에 처리할 수 있다.

  • C++ Skeleton Code (Pure)
더보기 
// JUNGOL 1726 구간의 최대값1
// jungol.co.kr/problem/1726
// 세그먼트 트리 : 업데이트 및 쿼리
#include <cstdio>

const int LM = 50005;
const int TLM = 1 << 17; // 131072

int N, Q;
int tree[TLM];

int max(int a, int b) { return a > b ? a : b; }

// 세그먼트 트리 업데이트 함수
void update(int node, int s, int e, int tg, int val) {
	if (s >= e) { // 리프 노드에 도달했을 때 값 업데이트
		tree[node] = val;
		return;
	}
	int m = (s + e) / 2, lch = node * 2, rch = lch + 1;
	if (tg <= m) update(lch, s, m, tg, val);  // 왼쪽 자식 노드 업데이트
	else update(rch, m + 1, e, tg, val);      // 오른쪽 자식 노드 업데이트
	tree[node] = max(tree[lch], tree[rch]);   // 부모 노드는 자식 노드 중 최댓값을 저장
}

// 구간 내 최댓값을 찾는 쿼리 함수
int query(int node, int s, int e, int qs, int qe) {
	if (e < qs || qe < s) return -1;           // 쿼리 범위 밖이면 무효값 반환
	if (qs <= s && e <= qe) return tree[node]; // 현재 구간이 완전히 쿼리 범위에 포함되면 반환
	int m = (s + e) / 2, lch = node * 2, rch = lch + 1;
	int leftMax = query(lch, s, m, qs, qe);    // 왼쪽 서브트리 탐색
	int rightMax = query(rch, m + 1, e, qs, qe); // 오른쪽 서브트리 탐색
	return max(leftMax, rightMax);             // 두 값 중 최댓값 반환
}

int main() {
	scanf("%d %d", &N, &Q);
	int i, s, e, val;

	// 초기 데이터 입력 및 트리 업데이트
	for (i = 1; i <= N; ++i) {
		scanf("%d", &val);
		update(1, 1, N, i, val);
	}

	// 쿼리 처리
	for (i = 0; i < Q; ++i) {
		scanf("%d %d", &s, &e);
		printf("%d\n", query(1, 1, N, s, e));
	}
}

 

Plane sweeping

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

 

Maximum flow

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

 

Bipartite match

이분 매칭(bipartite match) 문제는 이분 그래프에서 서로 다른 두 부분 집합의 노드를 매칭하는 최대 집합을 찾는 문제이다. 이는 예를 들어, 일자리 할당, 자원 분배 등 다양한 최적화 문제에서 중요한 역할을 한다. 홉크로프트-카프(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의 강좌/실전 알고리즘

[10] (Site) C++ 유용한 기능들

[11] (Book) 알고리즘 문제 해결 전략 - 구종만 저

 

저작자표시

'Coding' 카테고리의 다른 글

Modern C++ 개념 정리 (STL, Design Pattern, Concurrent, Template Programming)  (0) 2024.06.27
[PS] 알고리즘 문제 풀이 - 유용한 팁 및 문제 리스트 정리  (0) 2024.03.08
[PS] 자료구조와 알고리즘 개념 정리 (Data Structure) Part 1  (1) 2024.03.07
VPython 예제10 - 2자유도 반한정계 스프링-질량 애니메이션  (0) 2022.01.11
VPython 예제9 - 2자유도 스프링-질량계 애니메이션 (2)  (0) 2022.01.11

'Coding' Related Articles

티스토리툴바