알고리즘

제네릭 프로그래밍

제네릭 프로그래밍이란 대부분의 일반적인 설정에서 효율 저하 없이 작동할 수 있도록 알고리즘과 자료구조를 설계하는 데 초점을 맞춘 프로그래밍에 대한 접근법이다. (알고리즘 산책, 2015)

크리스마스 강연

2008년, 나는 1826년 마이클 패러데이가 첫 연사로 나선 왕립 연구소 크리스마스 강연(Royal Institution Christmas Lectures)의 180번째 연사로 선발되는 행운을 누렸다. 2008년 당시 나의 강연은 컴퓨터과학이란 주제로 진행된 최초의 강연이었다. 강연을 준비하며 컴퓨터과학을 일반 대중에게 설명할 방법을 고심하느라 많은 시간을 쏟았지만, 활용할 자료가 거의 없고 이런 필요를 다루는 대중 서적 또한 거의 전무하다는 사실을 깨달았다. 따라서 금번 맥코믹의 새 책 출간은 내겐 더욱 환영할 만한 일이다. (미래를 바꾼 아홉 가지 알고리즘, 2011)

크리스 비숍이 추천사에서 언급한 2008년 강연 영상

P-NP

  • P: Polynomial Time 다항식 시간 동안 ‘답을 해결할 수can provide an answer 있는’ 문제. 해결 문제.
  • NP: Non-deterministic Polynomial Time 다항식 시간 동안 ‘주어진 답이 맞는지 확인할 수can be verified 있는’ 문제. 검산 문제.

NP는 하나의 경우에 대해서 옳은지 그른지 보는 것이고, P는 해답이 되는 경우를 찾을 때 까지 모든 경우에 대해 옳고 그름을 따지는 것. P-NP 문제의 가장 중요한 쟁점은 수학적 귀납법으로 경우의 수를 P의 영역으로 넣을 수 있는지의 여부를 묻는 것으로 볼 수 있다. 대표적인 예로, 정렬 문제의 경우 경우의 수가 이지만, 이미 수학적 귀납법으로 나아가 으로 수렴된 바 있다. ref

A polynomial is a linear combination of terms that look like Constant * x^k. On the opposite, exponential means something like k^x, where in both case k is a constant and x is a variable. ref

Big O

Big-O 표기법은 다음 수식으로 표현될 수 있다.

O(f(n)) = s + C * f(n) + t

s는 작업 준비 시간이고, C는 비례 상수, t는 작업 정리 시간이다. 어떤 알고리즘에는 s, C, t들이 굉장히 큰 값일 수 있는데, 그런 경우 s+tC*f(n)을 압도할 수 있다. (전문가를 위한 C++, 2011)

Dynamic Programming

“컴퓨터 과학이 여는 세계”에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 ‘기억하며 풀기’로 번역했다.

분할정복divide and conquer과 차이는 부분 문제를 최대한 많이 이용하도록 나눈 다음, 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용

  • 피보나치 수열
  • Coin Change Problem동전 교환 문제: Greedy와 대조적으로 가장 작은 금액에 대해 최적의 솔루션을 찾고 각 금액에 대해 최적의 솔루션을 찾는다.
  • LCS 문제를 풀기 위해 동적 계획법을 사용하기도 한다.
    • 메모이제이션memoization은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

탐욕Greedy 알고리즘

배낭 문제(Knapsack Problem)는 조합 최적화의 대표적 문제다. 근사Approximation 알고리즘인 탐욕Greedy 알고리즘은 가장 무거운 물건을 먼저 고른다.

Viterbi algorithm

mini example를 구현했다. \delta_3 의 값이 A, B 모두 잘못되어 있으며, (5) 수식이 잘못 표기되어 있다.

알고리즘을 Python으로 구현했을때, brute force 방식으로 전부 계산했을때 맥북 기준 30초가 넘어간다. DP를 적용해 max_delta_tr를 구하여 \psi를 위한 max 값을 기억하며 풀 경우 7초가 걸렸다.

성능 개선을 위해 동일한 알고리즘을 C++로 구현해봤는데, 65초로 훨씬 늦다. CPU 사용률은 100%를 넘지 못하며 이는 Python도 마찬가지다. 동일한 100%인데 일반적인 기대와 달리 심각한 성능 차이가 난다.

동일한 알고리즘을 Java로 구현하면 3초대에 실행된다. time값은 6.5초 정도가 출력된다.

6.46s user 1.17s system 167% cpu 4.561 total

Java는 별도 처리를 하지 않았음에도 불구하고 CPU 사용률이 180%를 넘어간다. CPU 코어를 고르게 활용하는 것으로 보이며 일부 null 처리를 하여 계산 횟수도 C++에 비해 조금 적긴 하나 이 부분이 중요한 것 같진 않다.

Java가 가장 빠르고 Python, C++ 순이다. 일반적으로 가장 빠를 것으로 예상되는 C++가 비교가 무색할 정도로 성능이 낮다. 멀티 쓰레딩으로 개선이 될 것으로 보이나 아쉽게도 시도 해보진 못했다.

언어 시간 CPU 연산
Python 2 16s 100% 1,869,188
Python 3 7s 100% 1,869,188
C++ 65s 100% 2,314,485
Java 3s 180% 2,095,600

Viterbi는 단순 행렬 연산의 반복이다. 논문과 달리 stack underflow를 방지하기 위해 log로 합산했으며, 0 일때도 이후 계산을 잇기 위해 라플라스 스무딩 처리를 했다.

C++에서 std::mapstd::unordered_map으로 바꾸는 것만으로 한 문장에 7.38s가 걸리던 것을 2.55s로 줄일 수 있었다. 34% 수준으로 줄었으므로, 위 결과는 22s가 될 것으로 예상된다. 물론 그래도 느리기 때문에 좀 더 최적화는 필요하다.

String Manipulation

Aho Corasick

아호 코라식 알고리즘은 finite set of strings의 요소를 찾는 일종의 사전-매칭 알고리즘으로, 동시에 모든 문자열을 찾는다.

문자열은 중복 순열Permutations with repetition이므로 가 가능하다. (k elements, length n) 모든 위치에 가능하므로 문장의 길이인 (256 - 패턴 길이 n) * 패턴의 갯수 1,000,000개를 분자로 하여 분모로 나누면 매칭 확률을 구할 수 있다. C++구현에 버그가 있었고 직접 패치했다.

첫 실행시 트라이tries를 메모리에 읽어들이는 시간이 다소 걸리지만 이후 문장 부터는 비교가 필요 없을 정도로 빠른 성능을 보여준다. 대부분의 문장이 1~2ms 이내에 처리된다.

무작위성

가상의 동전 던지기를 수백만 번 했을 때의 결과처럼 편향이 없고 패턴이 나타나지 않는 난수를 컴퓨터나 기계장치로 만들어내는 것은 극히 어렵다. (뉴욕타임스 수학, 2013, 1988년 기사) 도널드 커누스의 책 『The Art of Computer Programming』 에서도 random에 대해 여러 챕터를 할애한다.

기타

DNA 프로파일링은 복잡함으로 인해 Approximation Algorithm 근사 알고리즘 사용 (넘버스, 2017)


2017 Book Reports · 2018 Book Reports · 2019 Book Reports · AWS · Activation, Cost Functions · Android Development · CNN, RNN · C++ · Decision Tree · Docker · Go · HTML, CSS, JavaScript · Hadoop, Spark · Information Retrieval · Java · Jupyter Notebooks · Keras · LeetCode · LifeHacks · MySQL · NLP 가이드 · NLP 실험 · NLP · Naive Bayes · OAuth 2.0 · OOP · Project Management · Python Data Structure Cheatsheet · Python · RSA · Software Deployment · Support Vector Machine · TensorRT · Word Embedding · XGBoost · Scikit Learn · 거리 · 데이터 마이닝 · 데이터 사이언스 · 딥러닝 · 머신러닝 분류기 · 머신러닝 · 미래학 · 비지니스 · 사회심리학 · 수학 · 알고리즘 · 영어 · 운영체제 · 이산수학 · 인공지능 · 자료구조 · 진화생물학 · 컴파일러 · 컴퓨터시스템구조 · 통계학 응용 · 통계학 ·
is a collection of Papers I have written.
© 2000 - Sang-Kil Park Except where otherwise noted, content on this site is licensed under a CC BY-NC 4.0.
This site design was brought from Distill.