Move Fast

언어적 특징

• 인터프리터(Interpreter) 언어로 별도의 컴파일 없이 실행된다.

• 별도로 타입 명시를 하지 않으며, 실행 중에 타입이 변경 가능(Dynamically typed)하다. 

• 객체 지향적(Object-oriendted) 언어로, 접근 제한자를 가지지 않지만 네이밍(Naming)의 언더스코어(_)로 접근 제한을 구분한다.

  • 이름 맨 앞에 언더스코어 1개이면 protected, 2개이면 private 이며, 그 외는 public 으로 구분한다.

• 함수(function)와 클래스(class)는 일급 객체(The first-class objects)로, 모든 변수(매개변수, 로컬변수 등)에 할당 가능하며 일반적으로 다른 객체에 적용 가능한 연산을 모두 지원한다.

• PYTHONPATH: 인터프리터가 파이썬 프로그램이 실행될 때 import된 모듈들이 실제 디스크에 어디에 위치했는지 알기 위해 사용하는 환경변수. 따라서 프로그램이 내장 모듈에 대해 ImportError 를 일으키면 가장 먼저 살펴봐야하는 부분이다.

• PEP는 Python Enhancement Proposal의 약자로, 가독성 높은 파이썬의 코딩 스타일 중 하나이며, PEP8이 대중적이다.

• 주석은 # comment 과 """ comment """ 가 있는데, 후자는 docstring 용도로 사용된다.

  • 참고: Docstrings are not actually comments, but, they are documentation strings. These docstrings are within triple quotes. They are not assigned to any variable and therefore, at times, serve the purpose of comments as well.

• 파이썬 인터프리터에서는 help() 와 dir() 이라는 함수를 사용할 수 있는데, 라이브러리를 잘 모를 경우 굉장히 유용하다.

  • The help() function is used to display the documentation string and also facilitates you to see the help related to modules, keywords, attributes, etc.

  • The dir() function is used to display the defined symbols. (클래스의 어떤 메소드가 있는지 확인할 때 매우 편하다.)

• 파이썬 패키지(package)는 여러 모듈을 포함하는 네임스페이스의 집합이다. 최상위 패키지 디렉토리 안에 패키지 디렉토리가 있을 수 있는데 이들 안에 __init__.py 를 작성하면 해당 디렉토리 패키지임을 명시하는 것이다. 따라서 다른 디렉토리에서 다음과 같이 해당 모듈을 사용할 수 있다.

"""
예시: from 패키지명 import 모듈명

~/mypkg $ tree
.
├── utils
│   └── __init__.py
│   └── mini_module.py
│   └── large_module.py
└── subpkg
    ├── __init__.py
    └── new_module.py

mypkg 를 상위 디렉터리로 하고 위와 같은 구조를 가질 때,
subpkg의 new_module.py에서는 아래의 형태로 utils 의 모듈을 사용할 수 있다.
"""

from utils import mini_moudle
from utils.mini_module import *
from utils.large_moudle import MyObject

메모리 관리

• 파이썬은 내부적(C언어로 작성되었음)으로 PyObject 라는 객체를 생성해서 데이터를 관리하는데, 데이터들은 Python Private Heap Space 라는 곳에 저장된다. 일반적으로 지역 변수는 스택에 저장된다고 배웠으나, 곧 살펴볼 파이썬의 내장 타입들은 모두 객체이며 힙 영역에 저장된다.

>>> a = 1
>>> type(a)
<class 'int'>

• Private Heap 은 파이썬이 스스로 관리하는 곳이기 때문에 파이썬 코드로는 프로그래머가 직접적으로 메모리를 할당하거나 해제할 수 없다. 직접 살펴보고 싶다면 파이썬 C 라이브러리를 사용해야 한다.

  • 누군가 메모리 할당을 살펴본 흔적

• PyObject는 멤버로 참조 카운트(reference count)를 가지는데, 이는 객체가 참조될 때 1씩 증가하고 참조되지 않을 경우 1씩 감소한다. 그리고 reference count = 0 이 되면 메모리는 해제된다.
  

  • sys 모듈의 getrefcount() 함수를 이용해서 count를 직접 확인해볼 수 있다.

  • 아래의 첫 출력 결과가 2인 것은 sys.getrefcount() 함수의 인자로 참조되었기 때문에 1이 아니라 2로 출력되는 것이다.

>>> import sys
>>> a = []
>>> sys.getrefcount(a)
2
>>> b = a
>>> sys.getrefcount(a)
3
>>> del a
>>> sys.getrefcount(b)
2

• 그러나, 아래와 같이 순환 참조(Circular References)가 발생할 경우 레퍼런스 카운팅 기법으로는 메모리를 관리할 수 없다.

  • 순환 참조란 서로 다른 객체가 서로를 참조하는 경우를 의미한다. 여기서 두 객체가 삭제될 경우 참조 횟수는 0보다 큰 상태이지만 객체를 이미 삭제해버려서 해당 객체들에 접근할 수 없다는 문제가 발생한다.

>>> class Obj:
...     def __init__(self):
...         print('Hello,', id(self))
...
...     def __del__(self):
...         print('Bye,', id(self))
...
>>> o1 = Obj()
Hello, 4470886656
>>> o2 = Obj()
Hello, 4470654432
>>> sys.getrefcount(o1)
2
>>> sys.getrefcount(o2)
2
>>> dir() # 선언한 클래스와 생성된 인스턴스가 네임스페이스에 존재한다.
['Obj', '__annotations__', '__builtins__', '__doc__', '__loader__', '__name__',
'__package__', '__spec__', 'o1', 'o2']
>>> o1.x = o2
>>> o2.x = o1
>>> sys.getrefcount(o1)
3
>>> sys.getrefcount(o2)
3
>>> del o1 # o2.x 로 참조되므로 o1의 reference count = 1
>>> del o2 # o1.x 로 참조되므로 o2의 reference count = 1
>>> dir() # 삭제되었기 때문에 네임 스페이스에는 없으나 실제로 __del__() 메소드는 호출되지 않았다.
['Obj', '__annotations__', '__builtins__', '__doc__', '__loader__', '__name__',
'__package__', '__spec__']

• 순환 참조와 같은 이슈를 해결하기 위해 파이썬은 가비지 콜렉터(Garbage Collector) 기능을 제공한다. 가비지 콜렉터는 gc 모듈을 import 해서 수동으로 관리할 수 있지만 파이썬에서는 자동으로 관리할 것은 권장한다.

  • 누군가 CPython 으로 가비지 콜렉터의 기능을 살펴본 흔적

• 가비지 콜렉팅은 다음과 같이 동작한다.

  • 0~2세대로 객체들을 구분(이를 Generational Garbage Collecting 이라 한다.)하는데, 처음 객체가 생성되면 0세대로 분류된다. 그리고 각 세대별로 저장된 객체가 임계값(threshold, 최대로 저장할 객체의 개수)에 이르면 쓰레기 수집(collect)이 진행된다.

  • 한 번 수집기가 실행될 때마다 해당 프로그램은 중단되므로 성능에 큰 영향을 미친다.

  • 수집기가 실행되고 각 세대별로 살아남은 객체는 다음으로 옮겨진다. 0세대에서 살아남은 객체는 1세대로, 1세대에서 살아남은 객체는 2세대로 옮겨진다.

  • 임계값은 세대마다 다르며, Generational Hypothesis(최근에 생성된 객체일수록 빨리 제거되며, 최근에 생성된 객체는 오래된 객체를 참조할 가능성이 적다는 가설)에 따라 0세대의 임계값이 가장 높다.

• gc 모듈을 이용해서 임계값을 바꾸거나 쓰레기 수집 기능을 직접 실행할 수 있다.

  • 임계값 변경 함수: gc.set_threshold(threshold0[, threshold1[, threshold2]])

  • 쓰레기 수집 기능 함수: gc.collect()

>>> import gc
>>> gc.get_threshold()	# 0세대는 700, 1세대는 10, 2세대는 10개까지 보관한다.
(700, 10, 10)
>>> gc.get_count()	# 0세대는 71개의 객체가 있다.
(71, 0, 0)
>>> gc.collect()	# 순환 참조로 삭제되지 않았던 객체들이 삭제되었다.
Bye, 4470886656
Bye, 4470654432
4
>>> gc.get_count()
(22, 0, 0)

• 그 외에 참조 카운트로 메모리를 관리하다보니 Global Interpreter Lock(이하 GIL) 과 관련된 이슈도 존재한다. GIL은 파이썬 인터프리터 전역에 락 변수(lock variable)를 설정해놓은 것으로, 멀티 쓰레딩 시 임계 영역(critical section)에서는 단일 쓰레드만이 실행되도록 한다.

  • 임계 영역이란 둘 이상의 쓰레드가 동시에 접근했을 때 프로그램의 실행에 critical 하게 영향을 줄 수 있는 부분을 뜻한다.

  • 한 프로세스에서 실행중인 쓰레드들은 스택(+레지스터)을 제외한 나머지 모든 영역을 공유한다.

• GIL 을 도입한 이유는 파이썬의 모든 객체가 힙에 저장되다 보니 멀티쓰레딩 환경에서 reference count 변수에 경쟁 조건(race condition)이 발생하는 것을 막기 위해서이다. 만약 reference count 변수를 멤버로 가지는 파이썬 객체마다 락 변수를 걸게 되면 데드락(deadlock)이 발생할 수 있으며 성능에 좋지 않기 때문에 파이썬 인터프리터 전역적으로 막아버린 것이다. 즉, 파이썬에서 단일 쓰레드만이 특정 객체 접근할 수 있도록 했다. 따라서 threading 모듈을 이용해서 멀티쓰레딩을 하더라도 실제로는 1개의 CPU가 여러 쓰레드를 번갈아가면서 실행시키다보니 컨텍스트 스위칭(context switching)이 빈번하게 발생하여 단일 쓰레드보다 성능이 떨어질 수 있다. (물론 이와 관련된 해결책으로 비동기 프로그래밍, 멀티프로세싱 등이 있는데 다음에 후술하겠다.)

  • 누군가의 GIL 성능에 관한 조사 흔적

Built-in Types

• Integers

• Floating-point

• Complext numbers

• Strings

• Boolean

• Built-in functions: 파이썬 인터프리터에 내장된 함수들로 위에서 설명했던 help()와 dir()이 이에 해당된다. 별도의 모듈을 import하지 않고 사용가능하다.

  • type() vs isinstance(): 파이썬의 데이터들은 모두 객체로 저장되지만, 내장형 타입(표준 데이터 타입)을 검사하기 위해 type(변수명) 함수를 사용하고 커스텀 클래스로 만든 객체들은 isinstance(변수명, 클래스명)로 클래스 타입을 검사한다. 즉, 파이썬 환경에서 인스턴스(=객체)와 내장형 타입을 구분하기 위해 제공하는 함수라고 볼 수 있다. 물론 표준 데이터 타입에 대해서도 isinstance 함수를 사용할 수 있다. 예를 들어, x = 1; isinstance(x, int); 의 출력 결과는 True 이다.

• 내장형 타입 관련 연산

• 비교 연산자

  • 파이썬에서는 직접 변수의 값을 비교할 때는 == 연산자를 사용하지만, 메모리 주소를 비교할 때(=동일 객체인지 등)는 is 연산자를 사용한다. 변수에 저장된 메모리 주소를 확인하려면 id(변수명) 함수를 사용하면 된다.

>>> a = 1000
>>> b = 1000
>>> a == b
True
>>> a is b
False
>>> id(a), id(b)
(4398724144, 4398724176)

접미사 배열

• 접미사 배열이란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. by Wikipedia
• 문자열 "banana" 의 접미사는 다음과 같다.

Suffix Array:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

• 사전순으로 정렬하면 다음과 같다.

Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na
2: nana

Naive Method

• 모든 접미사 문자열에 대해 비교한 경우: 비교할 때 O(N) 이 걸리고, 정렬할 경우 O(N*log(N)) 이 걸린다.
• 다음과 같은 방법으로 접미사 배열을 얻을 경우 O(N^2 * log(N)) 의 시간 복잡도를 갖는다.
• 일반적으로 문자열의 접미사를 모두 저장하기 보다는 접미사의 시작 위치만 저장하여 메모리를 절약한다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct NaiveComparator {
  const string& s;
  NaiveComparator(const string& s) : s(s) {}
  bool operator() (int i, int j) {
    const char* ptr = s.c_str();
    return strcmp(ptr + i, ptr + j) < 0;
  }
};

// O(N^2 * log(N)), where N is the length of the given string.
vector<int> getSuffixArray(const string& s) {
  vector<int> sfx(s.size());
  generate(sfx.begin(), sfx.end(), [x=0]() mutable { return x++; });
  sort(sfx.begin(), sfx.end(), NaiveComparator(s));
  return sfx;
}

int main() {
  string s = "banana";
  vector<int> sfx = getSuffixArray(s);
  return 0;
}

Manber-Myers Algorithm

• 접미사 배열 생성 시, O(N * log(N)^2) 의 시간복잡도를 갖는다.
• 아이디어는 정렬 시 매 비교마다 각 접미사의 t번째 글자를 기준으로 정렬을 해주는 것이다. 이 때 t는 2배씩 증가한다.
• 정렬을 여러 번 하는데도 빠르게 동작하는 이유는 이전에 비교한 결과를 이용하여 두 문자열의 대소비교를 O(1) 만에 끝낼 수 있기 때문이다. 즉, 정렬할 때 두 문자열의 모든 문자들을 살펴볼 필요가 없다.
• 아래에서 사용된 group[i]은 s[i]부터 시작하는 접미사가 속한 그룹으로, 첫 글자가 같으면 같은 그룹 번호를 가지는 것으로 시작한다. 따라서 초기값은 별도의 번호 없이 s[i]를 그룹 번호로 가진다.
  • 그리고 매 t번째 글자를 기준으로 정렬한 후, t번째 글자가 같은 것끼리 같은 그룹으로 묶는다. 즉, 처음 나뉜 그룹에서 인접한 접미사들이 다음 글자마다 그룹핑되는 것이다.
  • 매 정렬 후, 새 그룹 번호를 할당하는 이유는 t번째 글자마다 그룹핑을 다시하기 때문이다.
  • 비교되는 두 문자열 중 하나가 t보다 짧은 경우를 대비하여 group[n] = -1로 고정시켜놓음으로써 항상 i+t 와 j+t 가 n을 넘기지 않도록 해놓는다. t가 길이를 넘기기 이전에 맨 앞으로 보내지기 때문에 operator() 함수의 if문에서 필터링된다.
• t = 1 일 때 정렬하면, 첫 글자가 같은 접미사들은 sfx 배열 내에서 인접한 위치에 있게 된다.
• t = 2 일 때 정렬하면, 이미 첫 글자가 같은 접미사는 같은 그룹이므로 두번째 글자만 비교하여 순서가 바뀌게 된다.
• 4 < t < n 인 동안 위와 같이 계속 반복한다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct Comparator {
  vector<int> group;
  int t;
  Comparator(vector<int>& group, int t) : group(group), t(t) {}
  bool operator() (int i, int j) {
    if (group[i] != group[j]) return group[i] < group[j];
    return group[i+t] < group[j+t];
  }
};

// O(N * log(N))
vector<int> getSuffixArray(const string& s) {
  int n = s.size(), t = 1;
  vector<int> group(n+1, -1), sfx(n);
  for (int i = 0; i < n; i++) {
    group[i] = s[i];
    sfx[i] = i;
  }
  
  while (t < n) {
    Comparator comparator(group, t);
    sort(sfx.begin(), sfx.end(), comparator);
    t *= 2;
    vector<int> newGroup(n+1, -1);
    newGroup[sfx[0]] = 0;
    for (int i = 1; i < n; i++) {
      newGroup[sfx[i]] = newGroup[sfx[i-1]];
      // 사전순으로 앞에 위치하면 현재 그룹 번호를 이전 그룹 번호보다 1 증가
      if (comparator(sfx[i-1], sfx[i])) newGroup[sfx[i]]++;
    }
    group = newGroup;
  }
  return sfx;
}

int main() {
  string s = "banana";
  vector<int> sfx = getSuffixArray(s);
  return 0;
}

• 중간 결과를 출력해보면 t 가 증가할 때마다 정렬 결과가 변경되는 것을 알 수 있다.

Initial: 0 1 2 3 4 5 
Suffix Array:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

[t = 1] sfx: 5 1 3 0 2 4 
Suffix Array:
5: a
1: anana
3: ana
0: banana
2: nana
4: na      <--- 아직 첫번째 글자만 비교했기 때문에 na 는 뒤에 있다.
----------------
[t = 2] sfx: 5 3 1 0 4 2 
Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na      <--- 두번째 글자를 비교한 후 na가 앞으로 옮겨졌다.
2: nana
----------------
[t = 4] sfx: 5 3 1 0 4 2 
Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na
2: nana
----------------

• "mississipi" 에서 t번째 글자마다 그룹핑을 다시하여 그룹 번호가 변경된다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct Comparator {
  vector<int> group;
  int t;
  Comparator(vector<int>& group, int t) : group(group), t(t) {}
  bool operator() (int i, int j) {
    if (group[i] != group[j]) return group[i] < group[j];
    return group[i+t] < group[j+t];
  }
};

vector<int> getSuffixArray(const string& s) {
  int n = s.size(), t = 1;
  vector<int> group(n+1, -1), sfx(n);
  for (int i = 0; i < n; i++) {
    group[i] = s[i]-'a';
    sfx[i] = i;
  }
  
  // DEBUG
  cout << "Initial: ";
  for (int i = 0; i < n; i++) cout << sfx[i] << " ";
  cout << endl << "Suffix Array:" << endl;
  for (auto i : sfx) cout << "Group[" << i << "] = " << group[i] << ": " << s.substr(i) << endl;
  cout << endl;

  while (t < n) {
    Comparator comparator(group, t);
    sort(sfx.begin(), sfx.end(), comparator);
    t *= 2;
    vector<int> newGroup(n+1, -1);
    newGroup[sfx[0]] = 0;
    for (int i = 1; i < n; i++) {
      newGroup[sfx[i]] = newGroup[sfx[i-1]];
      if (comparator(sfx[i-1], sfx[i])) newGroup[sfx[i]]++;
    }
    
    // DEBUG
    cout << "t = " << t << ": ";
    for (int i = 0; i < n; i++) cout << sfx[i] << " ";
    cout << endl << "Suffix Array:" << endl;
    for (auto i : sfx) cout << "Group[" << i << "] = " << group[i] << ": " << s.substr(i) << endl;
    cout << "----------------" << endl;
    
    group = newGroup;
  }
  return sfx;
}

int main() {
  string s = "mississipi";
  vector<int> sfx = getSuffixArray(s);
  return 0;
}

Initial: 0 1 2 3 4 5 6 7 8 9 
Suffix Array:
Group[0] = 12: mississipi
Group[1] = 8: ississipi
Group[2] = 18: ssissipi
Group[3] = 18: sissipi
Group[4] = 8: issipi
Group[5] = 18: ssipi
Group[6] = 18: sipi
Group[7] = 8: ipi
Group[8] = 15: pi
Group[9] = 8: i

t = 2: 9 7 1 4 0 8 3 6 2 5 
Suffix Array:
Group[9] = 8: i
Group[7] = 8: ipi
Group[1] = 8: ississipi
Group[4] = 8: issipi
Group[0] = 12: mississipi
Group[8] = 15: pi
Group[3] = 18: sissipi
Group[6] = 18: sipi
Group[2] = 18: ssissipi
Group[5] = 18: ssipi
----------------
t = 4: 9 7 1 4 0 8 6 3 5 2 
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[1] = 2: ississipi      <---- 같은 그룹 내에서 4번째 글자 기준으로 그룹핑이 다시 된다.
Group[4] = 2: issipi
Group[0] = 3: mississipi
Group[8] = 4: pi
Group[6] = 5: sipi
Group[3] = 5: sissipi
Group[5] = 6: ssipi
Group[2] = 6: ssissipi
----------------
t = 8: 9 7 4 1 0 8 6 3 5 2 
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[4] = 2: issipi
Group[1] = 2: ississipi
Group[0] = 3: mississipi
Group[8] = 4: pi
Group[6] = 5: sipi
Group[3] = 6: sissipi
Group[5] = 7: ssipi
Group[2] = 8: ssissipi
----------------
t = 16: 9 7 4 1 0 8 6 3 5 2 
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[4] = 2: issipi
Group[1] = 3: ississipi
Group[0] = 4: mississipi
Group[8] = 5: pi
Group[6] = 6: sipi
Group[3] = 7: sissipi
Group[5] = 8: ssipi
Group[2] = 9: ssissipi
----------------

최장 공통 접두사 배열

• 접미사 배열에서 이전 접미사와 공통되는 접두사의 길이를 저장한 배열이다. by Wikipedia
• 알고리즘 대회에서는 어떤 문자열이 주어질 때 2번 이상 반복되는 연속되는 부분 문자열의 최대 갈이를 구할 때 주로 사용된다.
  • 해결책은 어떤 부분 문자열은 주어진 문자열의 접미사의 접두사라는 점을 이용하여 인접한 접미사끼리 공통되는 부분 중 가장 긴 것을 찾아내는 것이다.
• LCP 배열의 경우, 문자열의 길이가 길면 접미사를 비교하는데 시간이 오래걸리는 점을 보완하기 위해 인접한 접미사끼리 비교할 때 공통되는 문자들은 건너뛰어 시간을 절약한다. 예를 들면, mississipi 에서 접미사 ipi 와 issipi 를 비교할 때 이전에 i와 ipi 가 비교되었기 때문에 i는 세지 않고 바로 다음 글자인 p와 s부터 길이를 측정하는 것이다.
• 주의할 점은 LCP 배열을 만들 때, 문자열 비교 시간을 절약하기 위해 첫번째 위치에서부터 비교해야 하므로 prevSfx 처럼 접미사 배열에서 이전 접미사의 위치를 저장할 필요가 있다. 0번째 접미사는 이전 접미사가 없으므로 -1을 저장한다.

// 위와 동일

vector<int> getLongestCommonPrefix(const string& s, const vector<int>& sfx) {
    int n = s.size();
    vector<int> plcp(n), prevSfx(n), lcp(n);
    prevSfx[sfx[0]] = -1;
    for (int i = 1; i < n; i++) prevSfx[sfx[i]] = sfx[i-1];
    for (int i = 0, common = 0; i < n; i++) {
        if (prevSfx[i] == -1) plcp[i] = 0;
        else {
            while (s[i+common] == s[prevSfx[i]+common]) common++;
            plcp[i] = common;
            if (common > 0) common--;
        }
    }
    for (int i = 0; i < n; i++) lcp[i] = plcp[sfx[i]];
    return lcp;
}

int main() {
    string s = "mississipi";
    vector<int> sfx = getSuffixArray(s);
    for (int x : sfx) cout << s.substr(x) << endl;
    vector<int> lcp = getLongestCommonPrefix(s, sfx);
    int maxLen = 0, start = 0;
    for (int i = 0; i < lcp.size(); i++) {
        if (maxLen < lcp[i]) {
            maxLen = lcp[i];
            start = i;
        }
    }
    cout << "LongestCommonPrefix: " << s.substr(start, maxLen) << endl;
    return 0;
}

/*
i
ipi
issipi
ississipi
mississipi
pi
sipi
sissipi
ssipi
ssissipi
LongestCommonPrefix: issi
*/

• 소스 코드: 익명 함수 사용 시, 훨씬 빠르다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> getSuffixArray(const string& s) {
    int n = s.size();
    vector<int> g(n+1, -1), sfx(n), ng;
    for (int i = 0; i < n; i++) { g[i] = s[i]; sfx[i] = i; }
    
    for (int t = 1; t < n; t <<= 1, g = ng) {
        auto cmp = [&](int i, int j)->bool {
            if (g[i] != g[j]) return g[i] < g[j];
            return g[i+t] < g[j+t];
        };
        sort(sfx.begin(), sfx.end(), cmp);
        ng.clear(); ng.resize(n+1, -1); ng[sfx[0]] = 0;
        for (int i = 1; i < n; i++) {
            ng[sfx[i]] = ng[sfx[i-1]];
            if (cmp(sfx[i-1], sfx[i])) ng[sfx[i]]++;
        }
    }
    
    return sfx;
}

vector<int> getLongestCommonPrefix(const string& s, const vector<int>& sfx) {
    int n = s.size();
    vector<int> plcp(n), prevSfx(n), lcp(n);
    prevSfx[sfx[0]] = -1;
    for (int i = 1; i < n; i++) prevSfx[sfx[i]] = sfx[i-1];
    for (int i = 0, common = 0; i < n; i++) {
        if (prevSfx[i] == -1) plcp[i] = 0;
        else {
            while (s[i+common] == s[prevSfx[i]+common]) common++;
            plcp[i] = common;
            if (common > 0) common--;
        }
    }
    for (int i = 0; i < n; i++) lcp[i] = plcp[sfx[i]];
    return lcp;
}

int main() {
    string s; cin >> s;
    vector<int> sfx = getSuffixArray(s);
    vector<int> lcp = getLongestCommonPrefix(s, sfx);
    for (int x : sfx) cout << x+1 << " ";
    cout << endl << "x" << " ";
    for (int i = 1; i < lcp.size(); i++) cout << lcp[i] << " ";
    cout << endl;
    return 0;
}

이미지 출처: https://book.algospot.com

책을 처음 샀을 때는 2018년 1월 10일. (대략 3년 동안 가지고 있을 줄은 몰랐다)

당시 대학교 3학년이었는데, 친구 추천으로 정말 생각없이 샀었다. (이렇게 어려운 줄 몰랐지)

오늘 오후에 이 책을 완독(2020년 11월 28일)했는데, 여러모로 많은 생각이 들어 경험을 글로 공유하고자 한다. 게다가 실제로 책을 산 사람들은 많은데 후기글은 거의 못 본 것 같다.

책을 사기 전에는 알고리즘에 대한 지식은 거의 없었다. (백준 문제 30개 풀었나..? 학교수업은 just trash)

아무튼 알고리즘 지식은 무다 없을 무 ;;

* 참고로 필자는 내년에 졸업을 앞둔 대학교 4년제 컴공과 학생이다.

기억을 더듬어보면, 책을 받자마자  "나도 이제 알고리즘의 왕이 될 수 있겠지?!" 뭐 그런 생각을 하면서 읽기 시작했던 것 같다. 마치 나는 해적왕이 될거야;

그리고 변수의 이해부터 점점 졸리더니 ㅋㅋㅋ 동적 계획법(Dynamic Programming)의 어딘가에서 멈춰버렸다

물론 어려운 것도 있었지만 사실 알고리즘이 급하지 않아서 언젠가는 하겠지하고 책을 고이 모셔둔(쳐박아둔) 것이었따

그리고 2년 정도 흘렀나,,, (백준 문제 한 150개 풀었을 무렵) 고이 모셔둔(쳐박아둔) 종만북이 생각나서 다시 공부나 해볼까? 했는데 책을 덮고 펼치고 덮고 펼치고 를 반복했었다. (나레기 ..;)

아무튼 막학기에 캡스톤을 해야 해서 이전 겨울 방학때 1부라도 끝내자 해서 울며 겨자먹기로 1부를 읽기 시작했고, 그마저도 다 못해서 (매일 몇 시간씩 했는데도 너무 어렵더라;) 학기 중에 주말에 짬내서 봤다.

그리고 인턴하면서 2부를 시작했는데 진짜 ㅋㅋㅋ 웰컴투더헬 ..

집에ㅅ ㅓ창문에 대고 혼자 소리지르고 싶은거 굉장히 많이 참았다. 그리고 벽에 대고 머리 계속 쥐어박고 ㅠㅠ

책을 보면서 답답한 마음도 있었는데 설명이 이해가 되지 않아서 앞쪽으로 넘어가 다시 읽고를 무한 반복하다보니 시간이 오래 걸렸다. (정말 ㄹㅇ무한재생) 그리고 종만 님의 은혜로운 설명을 보면서 무릎을 탁 치고 (코드 보고 내 이마를 탁 치고;;) 를 여러 번하면서 확실히 실력 향상이 느껴지긴 하지만, 다음 장에 어려운거 또나오면 까먹는 문제가 발생했다.

한 5문제 있으면,

(와 이걸 이렇게?)

(와 이걸 이렇게?)

(와 이걸 이렇게?)

(와 이걸 이렇게?)

(와 이걸 이렇게?)

마지막 것만 기억남 ㅋㅋㅋㅋㅋㅋㅋㅋ

수록된 알고리즘은 각각 설명하고나서 문제를 살펴보는데 "문제 -> 접근 -> 풀이 -> 해설" 순서로 내용을 다룬다.

필자의 경우는 <문제> 읽고 혼자 고민하다가 안되면, <접근> 읽고 고민하고 그러다 안되면, 바로 풀이랑 해설을 보고 공부를 했는데 공부하는 방식은 개인의 스타일대로 하면 되는거고 나는 좀.. 오기(?) 자존심(?)이 좀 있어서 "그래도 이거는 풀 수 있겠지^^.."라는 마음으로 희망하나 버리지 않고 도전했었다.

물론 난이도 높은 문제들은 바로 풀이를 보는 것이 나았다 ㅎ;

책에는 문제별로 (하, 중, 상 이런 식으로) 난이도가 있어서 난이도가 "상"이면 30분 고민하고 안되면 바로 풀이로 넘어갔다.

왜 꼭 그런 문제들 있지 않나,, 30분 고민해도 감이 안오고 점점 딥슬립하게 되는 ㅋㅋ

실제로 그런 경우는 정말 <경험이 없어 아이디어가 생각조차 나지 않는 상황>인 경우가 대부분이었고 (난 멍청하지 않아..)

한 번 그런 풀이를 보고 나면 아래의 두 상황 중 하나가 되게 된다.

유사한 문제가 나왔을 때는 풀 수 있거나 vs 아이디어는 떠올랐는데 구현을 못하거나

구현을 못하는 건 필자의 경우 언어를 제대로 활용하지 못했던 게 큰 이유(뒤늦게 C++ 라이브러리를 정리했다지^^7)였고, 정석대로 구현하는 방법이 있는데 마찬가지로 경험이 없던 것이 문제가 되는 거였다. **이론만 안다고 되는게 아니더라..**

가끔은 내용을 이해하고 직접 짜보고 문제 풀어(무한 디버깅)보고 했는데 6시간이 지나기도 했다.

근데 넘어간 페이지는 3페이지 ㅋㅋ

그러면 자연스레 속에서 깊은 한숨이 나오면서 쓰레빠신고 동네 한바퀴 돌아준다. 안그러면 me쳐버림;

그리고 자기 전에 "ㅅㅂ 한 건했다" 이러고 ;

물론 가끔 일어난 일 ^^,,

뒤로 갈수록 자주 일어나는 일

체감상 느끼는 어려움은 난이도 "상" 문제들을 기준으로 했을 때 인공지능 수업시간에 C++로 다층퍼셉트론 구현한 거와 비슷하거나 그 이상이다. 역전파법(backpropagation)도 이론은 들으면 고개 끄덕끄덕하는데 실제 구현하라하면 'ㅁ'..

난이도 "중" 문제들은 60% 는 어렵다. 정말 어렵다. 비슷한 문제조차 못풀어봤다면 3시간 줘도 못 푼다.

라는 생각이 들만큼 입문자가 풀 수 있는 난이도는 아니라고 생각한다. BUT 종만 님의 알고리즘 설명이 있다면 몇 시간 걸리긴해도 풀 수는 있을 듯하다. 나머지 40%는 알고리즘 문제 좀 풀어봤다? 싶으면 도전해볼 가치는 있다. 대신 알고리즘이 뭔지에 따라 걸리는 시간은 확연히 차이가 난다.

책이 굉장히 두꺼운데 생각보다 알고리즘별로 문제가 많이 수록되어 있지는 않다. 있어봤자 5개가 최대인데 (아마?) 고작 5개 문제 풀어보고 감잡았쓰 - 완전 접쑤 - 라고 할 수는 없지 않나... 그래서 필자의 경우 leetcode에 비슷한 문제가 있는지 찾아보고 다음 챕터로 넘어가기 전에 머리도 식힐 겸 해당 문제들을 풀어봤다. 비슷한 문제니 푸는데 시간이 많이 걸리지는 않았음. leetcode 에 없으면 백준으로~

아무튼,, 주절주절 어렵다어렵다어렵다.. 디퓌컬ㅌ~ 라고 글을 썼지만, 그럼에도 이 책을 많은 사람들이 찾는 건 다 그럴만한 이유가 있지 않겠나..

확실히 읽기 전과 후는 다르다.

아래는 필자 입장(알고리즘 경험 zero)에서 이 책을 읽고 얻어간 것들을 정리한 것.

** 참고로 알고리즘과 자료구조는 다른 이론이기 때문에 알고리즘은 모르더라도 자료구조는 알고 읽기를 바람.

** 최소한 본인이 자주 사용할 언어(혹은 사용중인 언어)에서 전통적인 자료구조(스택, 큐, 우선순위 큐 등)가 어떻게 제공되는지도 무조건 알고 시작해야 함.

• 알고리즘 문제들은 보통 현실 상황을 반영하려 하므로, 대놓고 큐에 뭐 넣어라, 스택에 뭐 넣어라 그러지 않음. 따라서 주어진 문제 상황을 이해하고 이를 어떻게 자료(Data)로 표현할 지가 문제 해결의 핵심인데 (시작이 반이라고) 종만북은 자료구조를 설계하는 방법을 A-to-Z 방식으로 설명함.

• 문제의 해결책마다 시간 복잡도를 왜 그렇게 계산했는지 알려줌. 이게 진짜.. 종만의 미덕이 아닐까? 실제로 재귀 탐색만 하더라도 모든 노드가 아니라 부분 노드만 탐색한다던지 하면 계산하기 복잡한데, 참 수학을 잘하시는 종만 쓰앵님은 계산을 하셔서 알려주심.

• 정당성의 증명. 사실 이 부분은 너무 어려워서 포기한 것들이 손가락으로 셀 정도로 있음. (참새가 어찌 봉황의 뜻을 알겠소) 아니면 그 당시에 이해해도 지금 봐도 모르는 부분은 당연히 존재함 ㅋㅋ. 이 부분은 귀류법이나 귀납법으로 소개한 알고리즘이 반드시 해를 찾는다라는 사실을 증명함. --> 만약 직관이 아니라 증명하는 걸 습관처럼 한다면 그때는 종만북이 필요없을 듯 싶음..

• leetcode 의 난이도 hard 나, 백준의 정답률 20-30% 정도의 문제들을 해결할 수 있는 능력이 생김 (모든 문제 X)

• 다양한 알고리즘 지식, 문제 풀이 경험, 등등 (+ 내가 멍청하다는 사실 ㅠㅠ && 항상 겸손히 배워갈 의지 ^^)

참고: 이 책은 심장과 정신건강에 해롭기 때문에, 본인이 굳건한 멘탈과 이를 갈고 도전할 의지가 있다면 꼭 사길 바람. 뭐든지 쉬워지기전에는 모든게 어렵다고.. 나는 몰라서 못푼거지 멍청하지 않아..

만약 대회 경험도 다수 있고, (SCPC 수상자는 안봐도 될듯..) 큰 대회에 자주 출전해 본 사람이라면, 책을 살 필요가 있나 싶음.

정 읽다가 힘들면 아침부터 "나는 유노윤호다"라고 생각하자.

내일부터는 종만북을 다시 읽을 듯함. 나중에 시간만 되면 추가 후기를 써보던가 해야겠음..

원래 진리를 담은 책은 매번 읽을 때마다 얻어가는게 다르다고 하지않던가..

Threading Building Blocks

Threading Building Blocks (TBB) is a C++ template library developed by Intel for parallel programming on multi-core processors. Using TBB, a computation is broken down into tasks that can run in parallel. The library manages and schedules threads to execute these tasks.

by Wikipedia

How to use

on MacOS (tested on Catalina)

1. brew install tbb

2. echo | gcc -v -x c++ -E -

   • If there is not /usr/local/include below #include <...> search starts here:

   • Include the path first.

   • Also, check ls -l /usr/local/lib/*tbb*

3. ln -s /usr/local/Cellar/tbb/2020_U3_1/include/tbb /usr/local/include/tbb

4. g++ -g -std=c++17 <FILENAME> -pthread -ltbb

5. ./a.out

There are some useful library files.

It's fast!

I referred to parallel_reduce().

#include <iostream>
#include <vector>
#include <numeric>
#include <chrono>
#include <tbb/parallel_reduce.h>
#include <tbb/blocked_range.h>
using namespace std;
using namespace tbb;

class SumFoo {
    float* my_a;
public:
    float my_sum;
    void operator()( const blocked_range<size_t>& r ) {
        float *a = my_a;
        float sum = my_sum;
        size_t end = r.end();
        for( size_t i=r.begin(); i!=end; ++i )
            sum += a[i];
        my_sum = sum;
    }

    SumFoo( SumFoo& x, split ) : my_a(x.my_a), my_sum(0) {}

    void join( const SumFoo& y ) {my_sum+=y.my_sum;}

    SumFoo( float a[] ) :
        my_a(a), my_sum(0)
    {}
};

float SerialSumFoo( float a[], size_t n ) {
    float sum = 0;
    for( size_t i=0; i!=n; ++i )
        sum += a[i];
    return sum;
}

float ParallelSumFoo( float a[], size_t n ) {
    SumFoo sf(a);
    parallel_reduce( blocked_range<size_t>(0,n), sf );
    return sf.my_sum;
}

const size_t MAX_SZ = 10'000'000;
float a[MAX_SZ];
int main() {
    for (int i = 0; i < MAX_SZ; i++) a[i] = 0.1;

    {
        const auto t1 = std::chrono::high_resolution_clock::now();
        float result = SerialSumFoo(a, MAX_SZ);
        const auto t2 = std::chrono::high_resolution_clock::now();
        const std::chrono::duration<double, std::milli> ms = t2 - t1;
        cout << "Serial Sum = " << result << ", took " << ms.count() << " ms" << endl;
    }
    {
        const auto t1 = std::chrono::high_resolution_clock::now();
        float result = ParallelSumFoo(a, MAX_SZ);
        const auto t2 = std::chrono::high_resolution_clock::now();
        const std::chrono::duration<double, std::milli> ms = t2 - t1;
        cout << "Parallel Sum: " << result << ", took " << ms.count() << " ms" << endl;
    }

    return 0;
}

• In addition, we are able to use Parallel STL.

• Before including headers, install pstl from OneDPL.