평범한 컴퓨터공학도의 블로그 :)

개발자 Roadmap

1. https://roadmap.sh/roadmaps

(Frontend, Backend, Java, Python, Android, DevOps)

CS 공부를 위한 GitHub repository 

1. https://github.com/gyoogle/tech-interview-for-developer

2. https://github.com/hongcheol/CS-study

3. https://github.com/JaeYeopHan/Interview_Question_for_Beginner

Baekjoon Algorithm 풀이를 위한 Github repository

1. https://github.com/tony9402/baekjoon

CHAPTER 2 - 분할정복(Divide and Conquer)

- 문제의 입력를 두 개 이상의 작은 입력으로 나누고, 답을 얻기 위해 시도한다.
- 답을 얻지 못했다면, 또 각각의 입력 사례에 대해 분할을 한 뒤, 다시 시도한다.
- Divide and Conquer는 하향식(Top-Down) 방식의 접근법이다.

2.1 이분검색 (Binary Search)

- 이분 검색 알고리즘은 오름차순으로 정렬된 배열에서 실행가능하며, 수행 절차는 아래와 같다.

1. [Divide] 배열을 정 가운데 원소를 기준으로 반으로 분할한다. 찾고자 하는 수 x가 가운데 원소보다
   작으면 왼쪽 배열을 선택한다. x가 가운데 원소보다 크면 오른쪽 배열을 선택한다.
2. [Conquer] 선택한 반쪽 배열을 정복한다. 즉, 선택한 반쪽 배열에 x가 있는지 재귀적으로 이분검색한다.
3. [Obtain] 선택한 반쪽 배열에서 얻은 답이 최종 답이다.

index location (index low, index high)
{
  index mid;

  if(low > high)
   return 0;
  else {
   mid = (low + high) / 2;

   if(x == S[mid])
     return mid;
   else if(x < S[mid])
     return location(low, mid - 1);
   else
     return location(mid + 1, high);
  }
}

- 이분 검색의 최악 시간 복잡도(Worst-Case Time Complexity)는,

$$ W\left(n\right)\ =\ W\left(\frac{n}{2}\right)\ +\ 1\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ W\left(n\right)\ =\ \lg n\ +\ 1\ \ \in \ \Theta \left(\lg \ n\right) $$

2.2 Merge Sort

- 합병 정렬(Merge Sort)의 절차는 아래와 같다.

1. [Divide] 배열을 반으로 분할한다. (분할한 배열의 원소는 각각 n/2개 이다.)
2. [Conquer] 분할한 배열을 각각 따로 정렬한다.
3. [Obtain] 정렬한 두 배열을 합병하여 정렬한다.

void mergesort(int n, keytype S[])
{
  if(n > 1) {
    const int h = [n/2], m = n-h;
    keytype U[1..h], V[1..m];

    copy S[1] through S[h] to U[1] through U[h];
    copy S[h+1] through S[n] to V[1] through V[m];

    mergesort(h, U);
    mergesort(m, V);

    merge(h, m, U, V, S);
  }
}

void merge(int h, int m, const keytype U[], const keytype V[], keytype S[])
{
  index i, j, k;
  
  i = 1; j = 1; k = 1;
  while( i <= h && j <= m) {
    if(U[i] < V[j]) {
      S[k] = U[i];
      i++;
    }
    else {
      S[k] = V[j];
      j++;
    }
    k++;
  }

  if(i > h)
    copy V[j] through V[m] to S[k] through S[h+m];
  else
    copy U[i] through U[h] to S[k] through S[h+m];
}

​

- Merge의 Worst-case Time Complexity W(h,m)은 아래와 같다.
  (두 배열 U,V의 원소 개수는 h, m이다.)

$$ W\left(h,m\right)\ =\ h\ +\ m\ -\ 1 $$

- Mergesort의 Worst-case Time Complexity W(n)은 아래와 같다.

$$ W\left(n\right)\ =\ W\left(h\right)\ +\ W\left(m\right)\ +\ \left(h\ +m\ -1\right) $$

(1) W(h) : U를 정렬하는데 걸리는 시간
(2) W(m) : V를 정렬하는데 걸리는 시간
(3) (h+m-1) : 합병하는데 걸리는 시간

- 위의 식은 아래와 같이 표현될 수 있다.

$$ W\left(n\right)\ =\ 2W\left(\frac{n}{2}\right)\ +\ 1\ ,\ W\left(1\right)\ =\ 0 $$

$$ W\left(n\right)\ \ \in \ \Theta \left(n\ \lg \ n\right) $$

- MergeSort는 추가적으로 U와 V라는 배열을 만들어서 사용해야 하기 때문에, 추가적인 메모리가 필요하다.
(추가적으로 만들어지는 배열 원소의 총 개수는 대략 n(1+1/2+1/4+...) = 2n개 정도이다.)

​- 이에 n개의 원소를 가진 배열 하나만을 사용하여 메모리 공간을 효율적으로 사용하는 MergeSort가 존재한다.

void mergesort2 (index low, index high)
{
  index mid;

  if(low < high){
    mid = (low + high) / 2;
    mergesort2(low, mid);
    mergesort2(mid + 1, high);
    merge2(low, mid, high);
  }
}

void merge2(index low, index mid, index high)
{
  index i, j, k;
  keytype U[low .. high] // Merge에 필요한 local array
  i = low; j = mid + 1; k = low;

  while(i <= mid && j <= high) {
    if(S[i] < S[j]) {
       U[k] = S[i];
       i++;
    }
    else {
       U[k] = S[j];
       j++;
    }
       k++;
  }
  if(i > mid)
    move S[j] through S[high] to U[k] through U[high];
  else
    move S[i] through S[mid] to U[k] through U[high];
  move U[low] through U[high] to S[low] through S[high];
}

2.3 Quicksort(Partition Exchange Sort)

- Quicksort는 배열을 둘로 분할하고, 분할한 배열에 대해 각각 재귀 호출을 통해 정렬한다는 점이 Mergesort와 유사하다.

- 그러나, 빠른 정렬은 pivot을 설정하여 이 수보다 작은 원소는 왼쪽 배열로, 큰 원소는 오른쪽 배열로 가도록 하는 점에서 Mergesort와 다르다. 이에 pivot을 잘 설정하는 것이 중요하다.

void quicksort(index low, index high)
{
  index pivotpoint;
  
  if(high > low) {
    partition(low, high, pivotpoint);
    quicksort(low, pivotpoint - 1);
    quicksort(pivotpoint + 1, high);
  }
}

void partition(index low, index high, index& pivotpoint)
{
  index i, j;
  keytype pivotitem;

  pivotitem = S[low]; // pivotitem으로 첫번째 원소를 선택함.
  j = low;

  for(i = low + 1; i <= high; i++){
    if(S[i] < pivotitem){
      j++;
      exchange S[i] and S[j];
    }
  }
  pivotpoint = j;
  exchange S[low] and S[pivotpoint]; // pivotitem 값을 pivotpoint에 저장함.
}

- Partition은 첫째 원소를 제외한 모든 원소를 비교하므로, 시간복잡도는 아래와 같다.

$$ T\left(n\right)\ =\ n\ -1 $$

- 위의 Quicksort는 완전히 정렬된 배열을 정렬하는 경우가 Worst-case이다. (pivot이 항상 S[low])

$$ T\left(n\right)\ =\ T\left(0\right)\ +\ \ T\left(n-1\right)\ +\ n\ -1,\ n>0\ \ \ \ \ \ \ \ \ \ \ \ \ T\left(0\right)\ =\ 0 $$

T(0) : 왼쪽 배열을 정리하는데 걸리는 시간
T(n-1) : 오른쪽 배열을 정리하는데 걸리는 시간
n-1 : 분할(Partition) 하는데 걸리는 시간

$$ T\left(n\right)\ =\ \frac{n\left(n-1\right)}{2}\ \ \ \ \ \ \ \ \ \ \ W\left(n\right)\ =\ \frac{n\left(n-1\right)}{2}\in \Theta \left(n^2\right) $$

- 위의 Quicksort의 Average Time Complexity는,

$$ A\left(n\right)\ =\ \sum _{p=1}^n\frac{1}{n}\left[A\left(p-1\right)\ +\ A\left(n-p\right)\right]\ +\ n-1 $$

A(p-1) + A(n-p) : pivotpoint가 p일 때 부분 배열들을 정렬하는데 걸리는 평균시간
n-1 : 분할하는데 걸리는 시간

$$ A\left(n\right)\ \approx \left(n+1\right)2\ln n\ =\ \left(n+1\right)2\left(\ln 2\right)\left(\lg n\right) $$

$$ \approx \ 1.38\left(n+1\right)\lg n\ \in \ \Theta \left(n\lg n\right) $$

2.4 Strassen's Matrix Multiplication Algorithm

- 기본적인 행렬곱셈 알고리즘의 시간복잡도는,

$$ T\left(n\right)\ =\ n^3\ -\ n^2 $$

이므로, 실용적으로 사용하기 힘들다. 이에 Strassen은 곱셈을 기준으로 하든, 덧셈/뺄셈을 기준으로 하든지에
상관없이 시간복잡도가 3차보다 좋은 알고리즘을 발표하였다.

void strassen(int n, nxn_matrix A, nxn_matrix B, nxn_matrix& C)
{
  if(n <= threshold)
    compute C = A X B using the standard Algorithm.
  else {
     partition A into four matrices A11, A12, A21, A22;
     partition B into four matrices B11, B12, B21, B22;
     compute C = A X B using Strassen's method;
     // example recursive call;
     // strassen(n/2, A11 + A22, B11 + B22, M1);
  }
}

- Strassen에서의 곱셈의 수의 시간복잡도는 아래와 같다.

$$ T\left(n\right)\ =\ 7T\left(\frac{n}{2}\right)\ \ n>1\ 이며,\ n은\ 2의\ 거듭제곱 $$

$$ T\left(1\right)\ =\ 1 $$

$$ T\left(n\right)\ =\ n^{\lg 7}\approx n^{2.81}\in \Theta \left(n^{2.81}\right) $$

- Strassen에서의 덧셈/뺼셈의 수의 시간복잡도는 아래와 같다.

$$ T\left(n\right)\ =\ 7T\left(\frac{n}{2}\right)\ +\ 18\left(\frac{n}{2}\right)^2\ \ \ n>1\ 이며,\ n은\ 2의\ 거듭제곱 $$

$$ T\left(1\right)\ =\ 0 $$

$$ T\left(n\right)\ =\ 6n^{\lg 7}-6n^2\ \approx 6n^{2.81}\ -\ 6n^2\ \in \Theta \left(n^{2.81}\right) $$

2.5 분할정복법을 사용할 수 없는 경우

아래와 같은 두 경우에는 분할정복법을 피해야 한다.
1. 크기 n인 instance(사례)가 거의 n에 가까운 크기의 두 개 이상의 사례로 분할된다.
2. 크기 n인 instance(사례)가 n/c 크기의 거의 n개 사례로 분할된다.

​첫번째 사례의 경우는 exponential-time(지수시간) 알고리즘이 나오고,
두번째 사례의 경우는 n^(theta(lgn))의 알고리즘이 나오게 된다.

-Reference-
Neapolitan, Richard E., 『Foundation of algorithms FIFTH EDITION』

CHAPTER 1 - Algorithms : Efficiency, Analysis, and Order

1.1 알고리즘 (Algorithm)

- 리스트(list)란 어떤 원소를 특정 순서로 나열해 놓은 것이다.
(ex) S = [10, 7, 11, 5, 13 ,8]

- 순차검색 ( Time Complexitiy : O(n))
: 반복문을 통해 배열의 start index부터 end index까지 한번씩 검색하는 알고리즘.

void seqsearch(int n, const keytype S[]. keytype x, index& location)
{
  location = 1;
  while(location <= n && S[location] != x)
    location++;

  if(location > n)
    location = 0;
}

- 교환 정렬(Exchange Sort)
: 반복문을 통해 배열의 start index부터 end index까지 한번씩 검색하는 알고리즘.

void exchange(int n, keytype S[])
{
  index i, j;
  for (i = 1; i <= n-1; i++)
    for(j = i+1; j <= n; j++)
        if(S[j] < S[i])
          exchange S[i] and S[j];
}

1.2 효율적인 알고리즘 개발의 중요성

* 순차검색 대 이분검색

- 순차 검색(Sequential Search)보다 이분 검색(Binary Search)를 통해 효율적으로 Search 할 수 있다.

- 이분 검색(Binary Search) : 배열이 정렬되어 있다는 가정이 필요.
1. 찾고 싶은 수를 x라고 할 때, 배열의 정중앙에 위치한 원소 y와 비교한다.
2. 만약 x를 찾았다면, 검색을 종료한다.
3. 만약 x를 찾지 못했을 때 x가 y보다 크면 배열의 앞부분을, x가 y보다 작다면 배열의 뒷부분을 이분 검색한다.

void binsearch (int n, const keytype S[], keytype x, index& location)
{
  index low, high, mid;
  
  low = 1; high = n;
  location = 0;

  while(low <= high && location == 0) {
    mid = (low + high) / 2;

    if(x == S[mid])
     location = mid;
    else if(x < S[mid])
     high = mid - 1;
    else
     low = mid + 1;
  }
}

- 크기가 n인 배열에 대해 순차 검색에 의한 비교 횟수는 n 이고, 이분 검색에 의한 비교 횟수는 log(n) + 1 이다.

* 피보나치 수열

▶ 재귀함수를 사용하는 방법 (Divide and Conquer 기법)
- 피보나치 수열의 n번째 수는 재귀(Recursively)로 정의한다.

$$ f_{0} = 0 $$

$$ f_{1} = 1 $$

$$ f_{n} = f_{n-1} + f_{n-2} (if \; n \geq 2) $$

int fib (int n)
{
  if (n <= 1)
   return n;
  else
   return fib(n-1) + fib(n-2);
}

- T(n)을 n에 대한 Recursion Tree의 항의 개수라고 할 때,

$$ T(n) > 2 \times T(n-2)   
\\
\\
> 2 \times 2 \times T(n-4)
\\
\\
> 2 \times 2 \times 2 \times T(n-6)
\\
\\
> 2 \times 2 \times 2 \times ... \times T(0)  $$

- 따라서, 재귀함수를 사용하여 피보나치 함수를 구현하면 구하는 항의 갯수 T(n)은 아래 관계를 만족한다.

$$ T(n) > 2^{\frac{2}{n}} $$

▶ 배열과 반복문을 사용하는 방법 (Dynamic Programming 기법)

- 이에 재귀함수를 사용하는 대신, 배열과 반복문을 사용하여 좀 더 효율적이게 피보나치 수를 구하는 알고리즘을 작성할 수 있다.

int fib2 (int n)
{
  index i;
  int f[0..n];

  f[0] = 0;
  if ( n > 0) {
    f[1] = 1;
    for ( i = 2; i <= n; i++)
      f[i] = f[i-1] + f[i-2];
  }

  return f[n];
}

- 이 방법은 n번째 피보나치 항을 구하기 위해서 (n+1) 개의 항을 계산한다.

1.3 알고리즘의 분석 (Analysis of Algorithms)

* 시간복잡도 분석(Complexity Analysis)

- 일반적으로 알고리즘의 실행시간은 입력의 크기가 커지면 증가하고, 총 실행시간은 ​단위 연산이 몇 번 수행되는가에 비례한다.
- 알고리즘의 시간복잡도 분석(Time Complexity Analysis)는 입력크기를 기준으로 단위 연산을 몇번 수행하는지 구하는 것이다.
- 교환정렬(Exchange Sort)의 시간복잡도는,

$$ T(n) = (n-1) + (n-2) + (n-3) + ... + 1 = \frac{n(n-1)}{2} $$

- 크기가 n이어도, 단위 연산을 수행하는 횟수가 달라질 수 있다. (ex) 순차검색
- 이에 시간복잡도를 측정할 때, 알고리즘이 실행할 단위연산의 최대 횟수를 사용하여  최악 시간복잡도(Worst-case Time Complexity)를 구하여 사용할 수 있다.
- 순차 검색(Sequential Search)의 Worst-case time Complexity W(n) = n이다.

- 알고리즘이 평균적으로 얼마나 실행하는지를 알면, 더 효율적인 경우도 존재한다.
- 이 경우에는, 평균 시간복잡도(Average-case Time Complexity)를 구하여 알고리즘을 분석하는 경우가 더 합리적일 수 있다.
- 평균 시간복잡도를 구하기 위해서는 n개의 입력에 확률을 각각 부여해야 한다.
- 순차검색(Sequential Search)에서 찾고자 하는 수 x가 배열 S에 있는 경우는,
  (x가 k번째 위치에 있을 확률 : 1/n)

$$ A\left(n\right)\ =\ \sum _{k=1}^n\left(k\times \frac{1}{n}\right)\ =\ \frac{1}{n}\times \sum _{k=1}^nk\ =\frac{1}{n}\ \times \frac{n\left(n+1\right)}{2}\ =\ \frac{n+1}{2} $$

- 순차검색(Sequential Search)에서 찾고자 하는 수 x가 배열 S에 없는 경우에는,
  (x가 k번째에 위치할 확률 p/n, x가 배열에 없을 확률 1-p)

$$ A\left(n\right)\ =\ \sum _{k=1}^n\left(k\ \times \frac{p}{n}\right)\ +\ n\left(1-p\right)\ =\ n\left(1-\frac{p}{2}\right)\ +\frac{p}{2} $$

- 알고리즘이 실행할 단위연산의 최소 횟수를 통해 최선 시간복잡도(Best case Time Complexity)를 구할 수 있다
- 순차 검색(Sequential Search)의 Best-Case Time Complexity B(n) = 1이다.

1.4 차수 (Order)

- 시간복잡도(Time Complexity)가 n, 100n과 같은 경우 linear-time Algorithm 이라고 한다.
- 시간복잡도(Time Complexity)가 (n^2), (0.01n^2)과 같은 경우 quadratic-time Algorithm이라고 한다.

* 차수의 직관적인 소개(An Intutive Introduction to Order)

$$ \theta \left(\lg n\right)\ <\theta \left(n\right)\ <\ \theta \left(n\lg n\right)\ <\ \theta \left(n^2\right)\ <\ \theta \left(n^3\right)\ <\ 2^n $$

* 차수의 정식 소개 (Rigorous Introduction to Order)

1. Big-O

- 주어진 복잡도 함수 f(n)에 대해서 O(f(n))은 정수 N 이상의 모든 n에 대해서 다음 부등식이 성립하는
  양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

$$ g\left(n\right)\ \le \ c\ \times f\left(n\right) $$

 - Big O는 함수의 asymptotic upper bound(점근적인 상한)을 정한다.

2. Omega

- 주어진 복잡도 함수 f(n)에 대해서 Omega(f(n))은 N이상의 모든 n에 대해서 다음 부등식을 만족하는
양의 실수 c와 음이 아닌 정수 N이 존재하는 복잡도 함수 g(n)의 집합이다.

$$ g\left(n\right)\ \ge \ c\ \times f\left(n\right) $$

 - (Big-O)와 Omega와 Theta

-Reference-
Neapolitan, Richard E., 『Foundation of algorithms FIFTH EDITION』

std::list (데이터 순차적 저장 및 접근, 데이터 중복 O)

- 중간에 데이터 삽입 및 삭제가 자주 일어날 때 사용한다.
- <list> header를 include 해준 뒤에, std::list를 사용할 수 있다.
- 데이터에 Random Access 하는 경우가 적을 때, 사용하는 것이 좋다. (리스트는 순차적 접근만 가능하므로)
- 저장할 데이터 개수가 많거나, 검색을 자주하는 경우에는 사용하지 않는 것이 좋다.
- 가변적인 길이를 가질 수 있으며, 중간에 비어있는 데이터가 존재하지 않는다.

- list 코드 예시

#include <iostream>
#include <list>

using namespace std;

int main(){
  list<int> lt;
  lt.push_back(2); // lt = {2}
  lt.push_back(3); // lt = {2, 3}
  lt.push_back(4); // lt = {2, 3, 4}
  lt.push_back(4); // lt = {2, 3, 4, 4}
  
  lt.push_front(1); // lt = {1, 2, 3, 4, 4}
  lt.push_front(0); // lt = {0, 1, 2, 3, 4, 4}

  lt.pop_front();   // lt = {1, 2, 3, 4, 4}
  lt.pop_back();    // lt = {1, 2, 3, 4}
  
  lt.push_back(1);  // lt = {1, 2, 3, 4, 1}
  lt.remove(1);     // lt = {2, 3, 4} (특정값 원소 모두 제거)

  // 'list iterator'를 이용하여 list에 접근할 수 있음.
  list<int>::iterator lt_iter;
  for (lt_iter = lt.begin(); lt_iter != lt.end(); lt_iter++) 
      cout << *lt_iter << " ";
  printf("\n");

  // 특정값들로 list 선언하는 법
  list<int> lt2 = {5, 7, 6, 8};

  // 오름차순으로 정렬
  lt2.sort();  // lt2 = {5, 6, 7, 8}

  // lt와 lt2를 merge sort로 합침 (lt2에 lt 원소들을 추가)
  lt2.merge(lt); // lt2 = {2, 3, 4, 5, 6, 7, 8}

  list<int>::iterator lt2_iter;
  for (lt2_iter = lt2.begin(); lt2_iter != lt2.end(); lt2_iter++)
	  cout << *lt2_iter << " ";
  printf("\n");

  return 0;
}

std::map (Key 중복 X, Value 중복 O)

- 많은 자료들 사이에서 검색이 용이해야 할 때 사용한다.
- <map> header를 include 해준 뒤에, std::map를 사용할 수 있다.
- Key와 Value는 pair 형태이다.
- C++의 std::map의 경우, key를 기준으로 오름차순 정렬을 자동으로 수행한다.
- 많은 데이터를 저장해야 하고, 검색이 빨라야 할 때 사용하면 좋다.
- 인덱스를 사용하지 않고, iterator를 사용한다.
- 중복 Key value는 사용이 불가능하다. (= 각 Key value는 unique 해야 한다.)

- map 코드 예시

#include <iostream>
#include <string>
#include <map>

using namespace std;

int main(){
  // <key, value>의 pair 형태로 map을 선언함.
  map<string, int> m;

  // map에 데이터 삽입 (key는 중복불가, value는 중복가능)
  m.insert({"ABC", 123});
  m.insert({"BCD", 456});
  m.insert({"CDE", 123});
  // m.insert({"ABC", 789}); 는 key 중복으로 데이터 삽입이 되지 않음.

  // 'map iterator'를 이용하여 map에 접근할 수 있음.
  map<string, int>::iterator m_iter;
  for(m_iter = m.begin(); m_iter != m.end(); m_iter++)
    cout << "key: " <<  m_iter->first << ", value: " << m_iter->second << endl;

  // map에서 데이터 검색 (iterator를 반환하고, 못찾을 시 m.end()를 반환)
  map<string, int>::iterator find_iter;
  find_iter = m.find("ABC");
  
  if(find_iter != m.end())
    cout << "found key: " << find_iter->first << ", found value: " << find_iter->second << endl;
  else
    cout << "can't find data in map!" << endl;

  // map에서 데이터 변경
  m["ABC"] = 789;
  m["BCD"] = 101112;
  
  return 0;
}

​

std::unordered_map (hash_map) (Key 중복 X, Value 중복 O)

- 많은 자료들 사이에서 검색이 용이해야 할 때 사용한다.
- <unordered_map> header를 include 해준 뒤에, std::unordered_map를 사용할 수 있다.
- Key와 Value는 pair 형태이다.
- c++ std::map과 다르게, hash_map은 자동으로 정렬을 수행하지 않는다. (넣은 순서대로 데이터를 유지)
- 많은 데이터를 저장해야 하고, 검색이 빨라야 할 때 사용하면 좋다.
- 인덱스를 사용하지 않고, iterator를 사용한다.
- 중복 Key value는 사용이 불가능하다. (= 각 Key value는 unique 해야 한다.)​

- unordered_map (hash_map) 코드 예시

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

int main(){
  // <key, value>의 pair 형태로 unordered_map을 선언함.
  unordered_map<string, int> um;

  // unordered_map에 데이터 삽입 (key는 중복불가, value는 중복가능)
  um.insert({"ABC", 123});
  um.insert({"BCD", 456});
  um.insert({"CDE", 789});
  // um.insert({"ABC", 789}); 는 key 중복으로 데이터 삽입이 되지 않음.

  // 'unordered_map iterator'를 이용하여 unordered_map에 접근할 수 있음.
  unordered_map<string, int>::iterator um_iter;
  for (um_iter = um.begin(); um_iter != um.end(); um_iter++)
	  cout << "key: " << um_iter->first << ", value: " << um_iter->second << endl;

  // unordered_map에서 데이터 검색 (iterator를 반환하고, 못찾을 시 m.end()를 반환)
  unordered_map<string, int>::iterator find_iter;
  find_iter = um.find("ABC");

  if (find_iter != um.end())
	  cout << "found key: " << find_iter->first << ", found value: " << find_iter->second << endl;
  else
	  cout << "can't find data in unordered_map!" << endl;

  // unordered_map에서 데이터 삭제
  um.erase(find_iter); // <"ABC", 123> pair 삭제

  // unordered_map에서 데이터 변경
  um["BCD"] = 888;
  um["CDE"] = 999;

  return 0;
}

std::set (데이터 중복 X, 순서보장 X)

- 많은 자료들 사이에서 검색이 용이해야 할 때 사용한다.
- 인덱스를 사용하지 않고, iterator를 사용한다.
- 중복 Key value는 사용이 불가능하다. (= 각 Key value는 unique 해야 한다.)
- 이진 균형트리로 자료구조가 구성되어 있다.

- set 코드 예시

#include <iostream>
#include <string>
#include <set>

using namespace std;

int main(){
  // int type의 데이터를 담는 set 선언
  set<int> s;

  // set에 데이터 삽입 (key는 중복불가, value는 중복가능)
  s.insert(1); // s = {1}
  s.insert(2); // s = {1, 2}
  s.insert(3); // s = {1, 2, 3}
  s.insert(4); // s = {1, 2, 3, 4}
  //s.insert(1); 는 key 중복으로 데이터 삽입이 되지 않음.

  // 'set iterator'를 이용하여 set에 접근할 수 있음.
  set<int>::iterator s_iter;
  for (s_iter = s.begin(); s_iter != s.end(); s_iter++)
	  cout << "value: " << *s_iter << endl;

  // set에서 데이터 검색 (iterator를 반환하고, 못찾을 시 s.end()를 반환)
  set<int>::iterator find_iter;
  find_iter = s.find(1);

  if (find_iter != s.end())
	  cout << "found value: " << *find_iter << endl;
  else
	  cout << "can't find data in set!" << endl;

  // set에서 데이터 삭제
  s.erase(find_iter); // '1' value 삭제

  return 0;
}

* 참고자료

1. https://gamdekong.tistory.com/94
2. https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=psd0217&logNo=220308769007
3. https://velog.io/@esun1903/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-List-Map-Set%EC%9D%98-%ED%8A%B9%EC%A7%95%EA%B3%BC-%EC%B0%A8%EC%9D%B4%EC%A0%90
4. https://blockdmask.tistory.com/79

std::string class?

- c++에서는 문자열을 다루기 위해 std::string class를 사용할 수 있다.
- <string> header를 include 해준 뒤에, string class를 사용할 수 있다.
- 코딩테스트에서 문자열을 처리하는 문제가 빈번하게 나오니, 미리 사용법을 알아두면 좋을 것 같다.

std::string 사용법

- C++ code에서 string를 사용하기 위해서는 <string> header를 include해주어야 한다.

#include <string>

* 선언 (Declaration)

- 기본적인 string 선언법

#include <string>

using namespace std;

string s("Hello World!");
string s1 = "Hello World!";
string s2(s1);

* 사용법

1. string에서의 위치 지칭 및 string의 크기 구하기
  - N 크기의 길이를 가지는 string의 indexing은 0부터 N-1 까지 가능하다.
  - string class는 c언어의 char*(char배열)과는 달리 '\0'가 마지막에 삽입되지 않아도 된다.
  (예를 들어, 5크기의 길이를 가지는 string은 0~4까지의 index에 접근할 수 있다.)

string s = "ABCDE";

int s_len = s.size();    // size of string (5)
int s_len2 = s.length(); // size of string (5)

string::iterator begin_it = s.begin();  // first element를 가르키는 iterator
string::iterator end_it = s.end();      // end element를 가르키는 iterator

char front_val = s.front();  // front_val: 'A'
char back_val = s.back();    // back_val: 'E'

char first_val  = s[0];      // first_val: 'A'
char first_val2 = s.at(0);   // first_val2: 'A'
char second_val  = s[1];     // second_val: 'B'
char second_val2 = s.at(1);  // second_val2: 'B'
char last_val  = s[4];           // last_val: 'E'
char last_val2 = s[s_len-1];     // last_val2: 'E'
char last_val3 = s.at(4);        // last_val3: 'E'
char last_val4 = s.at(s_len-1);  // last_val4: 'E'

2. string에서의 값 추가 및 삭제, 복사, 검색
  - find()는 앞에서부터, rfind()는 뒤에서부터 검색 문자(열)을 찾아, 해당 index를 반환해준다.
  (못 찾았을 경우에, 'std::npos' 라는 쓰레기값을 반환해준다.)

- vector에서와 같이, string에서도 push_back()과 pop_back()이 가능하다.
- string은 원하는 곳에 문자(열)을 삽입하거나 삭제할 수 있지만, 시간복잡도가 O(n)이 소요된다.
- string에서 맨 뒤에 문자(열)을 삽입하는 것은 append()나 '+' operation을 사용하면 된다.
- clear() 함수를 사용하면 해당 string 변수를 size가 0인 string으로 초기화 할 수 있다.

string s = "ABCDE";

int B_idx = s.find('B');   // B_index: 1
int D_idx = s.rfind('DE'); // D_index: 3

s.insert(0, "123");   // s: "123ABCDE"
s.append("456");      // s: "123ABCDE456"
s = s + "FGH";        // s: "123ABCDE456FGH"

s.erase(0, 3);        // s: "ABCDE456FGH" (0~2[=3-1] index 값을 삭제)
s.erase(s.find('4')); // s: "ABCDE" (index 0부터 검색하여 최초의 '4' 위치 이후의 값을 다 삭제)

s.clear();            // Initialize string variable 's' 
s.push_back('F');     // s: "F"
s.push_back('G');     // s: "FG"
s.pop_back();         // s: "F"

3. string class에서의 유용한 기능들 (비교, substring, char*로의 변환)
  - 문자열을 비교하는 compare()는 같을 때 0, 다를 경우 -1 혹은 1을 반환한다.
    ([숫자 < 영어대문자 < 영어소문자] 순으로 비교를 진행하여 자신이 더 크면 1, 작으면 -1을 반환한다.)

  - 'substr()'의 경우, 한개의 parameter만 입력 시 문자열의 끝부분까지 잘라서 반환한다.
    (만약 2개의 parameter를 입력한다면, 그 길이만큼만 잘라서 반환한다.)

  - 'c_str()'을 이용하여 c++ class인 string에서 c type의 char* 로의 변환이 가능하다.

string s = "ABCDE";

int c_val;
c_val = s.compare("ABCDE"); // c_val: 0
c_val = s.compare("abcde"); // c_val: -1
c_val = s.compare("12345"); // c_val: 1

string sub_str1 = s.substr(2);       // sub_str1: "CDE"
string sub_str2 = s.substr(1, 3);    // sub_str2: "BCD"
string sub_str3 = s.substr(2, 5000); // sub_str3: "CDE"

const char* ctype_c = s.c_str(); // ctype_c: "ABCDE"

4. string을 특정 delimiter을 통해 parsing(tokenizing)하기​
(1) istringstream class (delimiter가 1개일 때)
  - string을 parsing(tokenizing)하는 방법 중 하나로 istringstream class을 사용할 수 있다.
  - stringstream class는 <sstream>을 include 한 뒤에 사용할 수 있다.

#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main()
{
	string line = "first second third fourth";
	stringstream sstream(line);
	string token;

	while (getline(sstream, token, ' '))
	  cout << token << endl;
	/* output:
	first
	second
	third
	fourth
	*/
	return 0;
}

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main()
{
	string s = "apple,pear,peach,melon";
	vector<string> v;

	int prev_idx = 0;
	int cur_idx = s.find(",");

	while (cur_idx != string::npos) {
		string sub_s = s.substr(prev_idx, cur_idx - prev_idx);
		v.push_back(sub_s);
		prev_idx = cur_idx + 1;
		cur_idx = s.find(',', prev_idx);
	}

	v.push_back(s.substr(prev_idx, cur_idx - prev_idx));

	for (int i=0; i<v.size(); i++) 
		cout << v[i] << endl;
	/* output:
    apple
    pear
    peach
    melon
    */
	
	return 0;
}

(3) 정규 표현식(Regular Expression)을 사용하는 방법
- 정규표현식을 잘 아는 사람이라면, 아래 링크에 첨부된 방법들을 사용하면 좋을 것 같다.
(https://plein-de-verite.tistory.com/339)

*참고자료
1. https://blockdmask.tistory.com/338
2. https://chbuljumeok1997.tistory.com/42

Algorithm header에는?

- 코딩테스트를 준비하다보면, 필수적으로 정렬/순열 등을 사용해야 할 때가 있다.
- 이 때, <algorithm> header에 있는 함수 한 두개를 사용함으로써 위 요소들을 구현할 수 있다.
- C++ code에서 Algorithm header를 사용하기 위해서는 <algorithm> header를 include 해주면 된다.
- 코딩테스트 내에서는, 주로 vector container와 함께 사용되는 경우가 많다.

Algorithm header에 속한 함수들

* 대수 비교(min, max)

  - 두 수 중 큰 값(작은 값)을 return 해준다.

#include <stdio.h>
#include <algorithm>

using namespace std;

int main(){
  int i_A = 10;
  int i_B = 5;

  printf("max: %d\n", max(i_A, i_B)); // 10
  printf("min: %d\n", min(i_A, i_B)); // 5

  double d_A = 10.5;
  double d_B = 5.75;

  printf("max: %lf\n", max(d_A, d_B)); // 10.5
  printf("min: %lf\n", min(d_A, d_B)); // 5.75

  return 0;
}

* 정렬(sort)

- 기본(default)으로는 수들을 작은 것부터 큰 것으로 정렬하는 오름차순 정렬을 수행한다.
- 내림차순 정렬을 수행하기 위해서는 <functional>의 greater<int>()를 사용해야 한다.
- vector를 정렬하고 싶을 땐, sort 함수의 인자로 container의 시작과 끝 iterator 값을 넣어준다.
- Return value는 none이다.

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

int main(){
  // 오름차순 정렬
  vector<int> v1{7, 5, 4, 1, 3, 2, 6};
  sort(v1.begin(), v1.end()); // v1 = {1, 2, 3, 4, 5, 6, 7}

  for(int i=0; i<v1.size(); i++){
    printf("%d ", v1[i]);
  }
  printf("\n");

  // 내림차순 정렬
  vector<int> v2{7, 5, 4, 1, 3, 2, 6};
  sort(v2.begin(), v2.end(), greater<int>());

  for (int i = 0; i < v2.size(); i++) {
	  printf("%d ", v2[i]); // v2 = {7, 6, 5, 4, 3, 2, 1}
  }
  printf("\n");

  return 0;
}

* 순열(next_permutation, prev_permutation)

- next_permutation은 현재 vector(또는 array)로 표현된 순열의 다음 순열을 구해준다. (O(n))
- prev_permutation은 현재 vector(또는 array)로 표현된 순열의 이전 순열을 구해준다. (O(n))
- 위 함수들의 인자로 container의 시작과 끝 iterator 값이나 array의 주소값들을 넣어준다.
- 다음(이전) 순열이 있다면 true를, 없다면 false를 반환한다.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  // next_permutation
  vector<int> v1 = {1, 2, 3, 4};

  do {
    for(int i=0; i<4; i++)
	  printf("%d ", v1[i]);
	printf("\n");
	/*
	  1 2 3 4
	  1 2 4 3
	  1 3 2 4
	  ...
	  4 2 3 1
	  4 3 1 2
	  4 3 2 1
	*/
  } while(next_permutation(v1.begin(), v1.end()));

  // prev_permutation
  vector<int> v2 = { 4, 3, 2, 1 };

  do {
	  for (int i = 0; i < 4; i++)
		  printf("%d ", v2[i]);
	  printf("\n");
	  /*
		4 3 2 1
		4 3 1 2
		4 2 3 1
		...
		1 3 2 4
		1 2 4 3
		1 2 3 4
	  */
  } while (prev_permutation(v2.begin(), v2.end()));

  return 0;
}

* 이분 탐색(binary_search)

- bool binary_search(ForwardIterator first, ForwardIterator last, const T& val);
- 위 함수들의 인자로 (1) container의 시작과 끝 iterator 값이나 (2) array의 주소값들을 넣어준다.
- 컨테이너(배열에) 찾고자 하는 값 val이 있다면 true를, 없다면 false를 반환한다.

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
  vector<int> v = {10, 11, 12, 13, 14, 15, 16};
  int arr[7] = {20, 21, 22, 23, 24, 25, 26};

  int find_v = 14;
  int find_a = 21;

  if(binary_search(v.begin(), v.end(), find_v))
    printf("the value %d is found in vector v!\n", find_v);
  else
    printf("the value %d is not found in vector v!\n", find_v);

  if (binary_search(arr, arr+7, find_a))
	  printf("the value %d is found in array arr!\n", find_a);
  else
	  printf("the value %d is not found in array arr!\n", find_a);

  return 0;
}