정렬 알고리즘

  • Comparison based sorting
    • Bubble sort
    • Selection sort
    • Merge sort
    • Quick sort
    • Heap sort
  • Non-comparison based sorting
    • Counting sort
    • Radix sort
    • Bucket sort

비트마스크를 이용한 집합의 구현

  • 원소의 포함 여부 확인
if (toppings & (1 << p)) cout << "pepperoni is in" << endl;
// 연산의 결과 값이 0 또는 1<<p 라는 점에 유의
  • 원소의 삭제
toppings &= ~(1 << p);
// 1<<p만 꺼버린다
  • 원소의 토글
toppings ^= (1 << p);
// XOR
  • 집합의 연산
int added = (a | b);           // 합집합
int intersection = (a & b)     // 교집합
int difference = (a & ~b);     // 차집합
int symmdiff = (a ^ b);        // 대칭차집합
  • 집합의 크기 구하기
int count = __builtin_popcount(toppings);
  • 집합의 최소 원소 찾기
int idx = __builtin_ctz(toppings);   // p
int elem = (toppings & -toppings);   // 1 << p
  • 집합의 최소 원소 지우기
toppings &= (toppings - 1);
  • 집합의 부분집합 순회
for (int subset = pizza; subset; subset = ((subset - 1) & pizza))
// subset에서 1을 빼면 최하위 비트가 꺼지고 나머지는 그 밑에는 1
// 공집합은 방문하지 않는다

선형 자료구조

  • Vector

    재할당 전략, 표준 라이브러리의 동적 배열 구현

  • Linked List

    Splicing, 삭제했던 원소 돌려놓기

Queue, Stack, Deque

  • 구현
    • list
    • vector
    • stl

KMP

vector<int> get_partial_match(const string& N) {
  vector<int> ret(N.size(), 0);
  int begin = 0, matched = 0;
  while (begin + matched < N.size()) {
    if (N[begin + matched] == N[matched]) {
      matched += 1;
      pi[begin + matched - 1] = matched;
    } else {
      if (matched == 0) {
        begin += 1;
      } else {
        begin += matched - pi[matched - 1];
        matched = pi[matced - 1];
      }
    }
  }
  return pi;
}

vector<int> kmp_search(const string& H, const string& N) {
  // searching Needle from Haystack
  vector<int> ret;
  vector<int> pi = get_partial_match(N);

  int begin = 0, matched = 0;
  while (begin < H.size() - N.size()) {
    if (matched < N.size() && H[begin + matched] == N[matched]) {
      matched += 1;
      if (matched == N.size()) ret.push_back(begin);
    } else {
      if (matched == 0) {
        begin += 1;
      } else {
        begin += matched - pi[matched - 1];
        matched = pi[matched - 1];
      }
    }
  }
  return ret;
}

// original verison proposed in the paper
vector<int> kmp_search2(const string& H, const string& N) {
  int n = H.size();
  int m = N.size();

  int matched = 0;
  vector<int> ret;
  vector<int> pi = get_partial_match(N);

  for (int i = 0; i < H.size(); ++i) {
    while (matched > 0 && H[i] != N[matched]) {
      matched = pi[matched - 1];
    }
    if (H[i] == N[matched]) {
      matched += 1;
      if (matched == N.size()) {
        ret.push_back(i - m + 1);
        matched = pi[matched - 1];
      }
    }
  }
  return ret;
}

Suffix Array

모든 접미사를 사전순으로 정렬한 배열

Manber-Myers ($O(n \log^2 n)$)

Tree

  • 트리에서 가장 긴 경로 찾기
struct TreeNode {
  vector<TreeNode *> children;
};

int g_longest;
int height(TreeNode *root) {
  vector<int> heights;
  for (int i = 0; i < root->children.size(); ++i) {
    heights.push_back(height(root->children[i]));
  }
  if (heights.empty())
    return 0;
  sort(heights.begin(), heights.end());
  if (heights.size() >= 2) {
    g_longest = max(g_longest, 2 + heights[heights.size() - 2] +
                                   heights[heights.size() - 1]);
  }
  return heights.back() + 1;
}

int solve(TreeNode *root) {
  g_longest = 0;
  int h = height(root);
  return max(g_longest, h);
}

BST