-
Manacher's Algorithm
목차 1. 개요 2. 기본 3. 구현 4. 문제풀이 5. 마무리 6. 참고자료 개요 이 포스트를 쓰며 학기가 시작되어 모든 알고리즘들을 한번씩 보면서 넘어가던 도중 사람들이 잘 관심 가지지 않지만, 알아두면 재미있을법한 알고리즘인 Manacher’s Algorithm 을 소개해보고자 한다. Manacher’s Algorithm은 String 내에 존재하는 모든 Palindrome을 $O(N)$에 구하는 강력한 알고리즘이다. 물론 이 알고리즘이 실전에 출제되는 경우는 매우 드물지만 원리 자체가 재미있고 시간복잡도가 $O(N)$이 되는 원리가 재미있는 알고리즘이므로 자세하게 설명해보고자 한다. 팰린드롬 팰린드롬을 모르는 사람을 위해 간단히...
-
AMP(Accelerated Mobile Pages) 기여
들어가며 그동안 블로깅을 하면서 추가한 기능들을 AMP로 옮기려고 보니 가장 문제가 되는 것이 외부 스크립트를 쓰는 것들이었다. 크게 두 가지로 구문 강조와 수식이 있는데, 전자는 찾아보니 그냥 GitHub Gist를 쓰라는 이야기가 많아서 일단은 그냥 두기로 했다. 이제 수식을 쓰기 위한 내용이다. 일반 웹페이지에서는 다음과 같이 MathJax를 사용하면 된다. 그러나 AMP의 정책상 내부에서 Javascript를 사용할 수 없기에, Extension을 하나 만들고 본 프로젝트에 인정을 받으면 된다. 이에 이미 만들어져 있던 것이 <amp-mathml> 이었고 형식은 다음과 같다. 오류...
-
HPX parallel partition 알고리즘
안녕하세요. 오늘은 제가 예전에 HPX 라는 오픈소스에 구현했던 parallel partition 알고리즘에 대해 간단히 소개하고 설명하는 시간을 가져보도록 하겠습니다. » 이 글을 좀 더 좋은 가독성으로 읽기 « 출처 먼저 이 포스팅에서 다루는 알고리즘/코드의 출처는 다음과 같습니다. HPX : https://github.com/STEllAR-GROUP/hpx 관련 MR : https://github.com/STEllAR-GROUP/hpx/pull/2778 소스코드 : https://github.com/STEllAR-GROUP/hpx/blob/master/hpx/parallel/algorithms/partition.hpp 소개 parallel partition 알고리즘은 여러 개의 연산 유닛 (쉽게 말하면 cpu) 들을 이용해서 partition 알고리즘을 수행하는 것을 말합니다. 이 포스팅에서는 독자가 partition 알고리즘에 대해서 이미 알고있다고 가정합니다. partition 알고리즘에...
-
알고 나면 유용한 TeX 팁들
TeX은 Donald Knuth가 만든 조판 언어이며, 수많은 분야에서 논문, 책자, 강의 자료 등을 만드는 데 사용됩니다. TeX에 대한 찬양을 하기에는 여백이 너무 부족하므로 생략하도록 하겠습니다. 이 포스트는 TeX 설치법이나 입문 또한 다루지 않습니다. 해당 내용은 Overleaf 같은 온라인 TeX 편집기 사이트에서 찾아보시길 바랍니다. 대신, 이 포스트는 어느 정도 TeX을 쓸 수 있는 분들에게 유용할 (혹은 이미 알고 있을) 팁을 다룹니다. 그림 폴더 경로 설정 일반적으로 TeX에 이미지를 넣을 때는 \includegraphics를 사용합니다 (graphicx 패키지 필요). 이...
-
MobX 내부 살펴보기
React는 상태 관리(State management)를 위해 기본적으로 setState 함수를 사용합니다. React를 처음 접하기 시작했다면 몇 가지 컴포넌트들을 만들고, 활용해보면서 React가 props와 state를 변경하는 것 만으로도 인터렉티브한 웹 어플리케이션을 얼마나 쉽고 간단하게 만들 수 있는지에 감탄할겁니다. 하지만 여러분들의 어플리케이션의 규모가 커짐에 따라 setState만으로는 상태 관리가 충분하지 않다는 것을 느끼게 됩니다. 관리해야 할 컴포넌트가 늘어나고, 자연스럽게 컴포넌트 간의 의존성이 생기게 됩니다. 여러분은 React의 State API를 대체할 무언가를 찾으러 나설 겁니다. 그 중 가장 대표적인 두 라이브러리가 Redux와 MobX이죠....