Overview 문자열 매칭은 여러 곳곳에서 흔하게 사용되는 알고리즘 중의 하나입니다. 당장에 브라우저에서 command + f 나 ctrl + f를 눌렀을때 나타나는 검색 바에서도 문자열 매칭을 통해 찾고자하는 문자열의 위치를 알려줍니다. 가장 단순한 문자열 매칭 방법은 해당 페이지에 있는 모든 문자열에 대해서 찾고자 하는 문자열을 일일이 대입하는 방식일 것입니다. 전체 문자열의 길이를 $n$, 찾고자 하는 문자열의 길이를 $m$이라고 하면 $O(mn)$ 의 시간이 소요되게 될 것입니다. 이는 문자열의 길이가 굉장히 긴 경우에는 심각한 비효율성을 초래하기 때문에 개선의 필요성이 있으며, 이를 효율적으로 개선한 방법 중의 하나 ( $ O(m+n) $ 의 시간복잡도를 가지고 있음 )가 이제 소개할 KMP알..

Image Style Transfer Using Convolutional Neural Networks, Gatys et al. 논문을 참조하여 정리한 글임을 서두에 밝힙니다. Style Transfer Abstract 신경망을 이용한 스타일 전이(Neural Style Transfer)는 2015년 이 논문('Image Style Transfer Using Convolutional Neural Networks')에 소개된 방법으로, 원본 이미지 (natural image)에서 Style과 Content를 분리해내고 이들을 재조합하여 새로운 이미지를 만들어내는 것에 대한 아이디어를 소개하고 있습니다. 위 사진에서 확인할 수 있는 것처럼 하나의 이미지(호숫가와 집이 있는 그림)에서 Content를 추출하고 ..

*본 포스팅은 Stanford CS231n 강의를 참조하였음을 미리 밝힙니다. *캡쳐된 일부 강의 자료들은 CS231n에서 제공하는 PPT 슬라이드를 참조하였습니다. 현대 딥러닝의 아쉬운 점 중 하나는 딥러닝의 학습 과정을 딥러닝 코드를 작성한 사람조차 알기가 어렵다는 점입니다. 모델 학습이 성공했다면 왜 성공했는지, 실패했다면 왜 실패했는지를 해석하기가 어려운데, 그 이유는 기본적으로 딥러닝 모델은 많은 데이터를 한꺼번에 처리하며, 여러 겹의 레이어를 학습시키는 과정에서 적어도 수만 가지의 파라미터를 다루어야 하기 때문입니다. 따라서 VIsualize(시각화)를 통해 각각의 레이어에서 무슨 일이 일어나고 있는지, 더 나아가서 학습 전반적이 과정에서 무슨 일이 일어나고 있는지를 연구하려는 여러 시도들이 ..

*본 포스팅은 Stanford CS231n 강의를 참조하였음을 미리 밝힙니다. *캡쳐된 일부 강의 자료들은 CS231n에서 제공하는 PPT 슬라이드를 참조하였습니다. 현대 딥러닝의 아쉬운 점 중 하나는 딥러닝의 학습 과정을 딥러닝 코드를 작성한 사람조차 알기가 어렵다는 점입니다. 모델 학습이 성공했다면 왜 성공했는지, 실패했다면 왜 실패했는지를 해석하기가 어려운데, 그 이유는 기본적으로 딥러닝 모델은 많은 데이터를 한꺼번에 처리하며, 여러 겹의 레이어를 학습시키는 과정에서 적어도 수만 가지의 파라미터를 다루어야 하기 때문입니다. 따라서 VIsualize(시각화)를 통해 각각의 레이어에서 무슨 일이 일어나고 있는지, 더 나아가서 학습 전반적이 과정에서 무슨 일이 일어나고 있는지를 연구하려는 여러 시도들이 ..

풀이 stable sort를 통해 구현한다면 쉽게 해결할 수 있는 문제이다. Stable Sort란 정렬 알고리즘의 종류가 아닌 알고리즘의 정렬 방식에 관한 것으로 동일한 키 값을 가진 원소들에 대하여 정렬하기 전과 정렬하기 후의 value가 같은 순서를 가지도록 정렬하는 방식을 의미한다. 예를 들어 [key, value] 쌍을 갖는 객체들이 다음과 같이 나열되어 있다고 하자 [3, "철수"] [2, "영희"] [1, "훈이"] [2, "맹구"], [2,"뚱이] key값에 대하여 위 객체들을 오름차순으로 정렬한다고 할 때, Stable Sort는 객체들을 다음과 같이 정렬한다. [1, "훈이"] [2, "영희"] [2, "맹구"] [2, "뚱이"] [3, "철수"] 즉, key 값이 동일한 경우 정렬되기..

빅데이터를 다루기 위해서, 즉 Stream Data를 다루기 위해서 Moment라는 개념을 정리해 둘 필요가 있다. 여러 물리량을 다루는 데 있어서 모멘트라는 개념이 많이 쓰이기도 하기 때문에 낯설지는 않은 개념이겠지만, 확실하게 짚고 넘어가는 것이 좋다. m(i)를 특정한 값 i가 Stream 에 등장한 횟수라고 정의할 때, kth Moment는 아래 그림과 같이 스트림에 있는 N개의 m(i)를 각각 k승 한 값들의 합으로 나타낼 수 있다. 이 모멘트는 k값에 따라 각기 다른 특정한 의미를 갖는데, 모멘트를 정의하는데 사용했던, m(i)의 의미를 생각해보면 쉽게 이해할 수 있다. 0th moment = m(i)의 값이 의미가 없어지므로, 스트림 내에서 서로 다른 원소의 개수를 의미한다. 1st mome..