시래 블로그

정렬 알고리즘 중 하나인 병합 정렬(Merge sort)에 대해 알아보겠습니다. 이 글은 《Introduction to Algorithms》 3th edition을 정리한 것입니다. 분할 정복 병합 정렬은 분할 정복(divide-and-conquer)라는 접근법을 이용하는 정렬 알고리즘입니다. 그렇기 때문에 분할 정복이 무엇인지 살펴봐야 합니다. 분할 정복은 문제를 작게 쪼개서 해결하는 방식입니다. 구체적으로는 다음 3단계를 거쳐 문제를 해결합니다. 분할(divide) 하나의 커다란 문제를 그보다 크기가 작은 하위 문제(subproblem)로 분할합니다. 하위 문제는 기존 문제와 크기만 다를 뿐, 같은 문제여야 합니다. 정복(conquer) 문제가 충분히 작아질 때까지 계속해서 하위 문제로 분할합니다. ..

정렬 알고리즘 중 하나인 삽입 정렬(Insertion sort)에 대해 알아보겠습니다. 이 글은 《Introduction to Algorithms》 3th edition을 정리한 것입니다. 기본 개념 삽입 정렬은 카드 게임을 할 때 우리가 카드를 정렬하는 방식과 같은 방식으로 작동합니다. 처음에는 손에 카드가 없는 상태로 시작합니다. 카드 더미에서 카드를 한 장씩 가져와서 왼손에 쥐는데, 새로 가져온 카드를 알맞은 위치에 넣습니다. 알맞은 위치를 찾기 위해서 새로 가져온 카드를 왼손에 쥔 카드와 비교합니다. 오른쪽부터 왼쪽으로 차례대로 비교합니다. 예시 a) 오른쪽으로 갈수록 큰 수가 오도록 정렬을 한다고 하겠습니다. 순서가 [5, 2, 4, 6, 1, 3]인 배열을 정렬하고자 합니다. 계속해서 카드에 ..

텍스트 데이터를 분석할 때 가장 흔히 사용하는 방법이 단어 수를 세는 것입니다. 각각의 텍스트에 등장한 단어 수를 알면 이를 기반으로 키워드를 추출한다거나, 표절 검사, 문서 분류 등 다양한 분석을 할 수 있습니다. 예를 들어 아래와 같은 세 개의 문장이 있을 때, 누구나 한번쯤은 사랑에 웃고 누구나 한번쯤은 사랑에 울고 그것이 바로 사랑 사랑 사랑이야 문장별로 단어가 몇 번 등장했는지 표(행렬)로 나타낼 수 있습니다. 누구나 한번쯤 사랑 웃고 울고 그것 바로 문장1 1 1 1 1 문장2 1 1 1 1 문장3 3 1 1 이렇게 한 번 정리를 해놓으면, 이후 여러 가지 분석에 이용할 수 있습니다. 예를 들어 '사랑이 5번 등장했으니, 무언가 중요한 단어가 않을까'라거나, '문장1과 문장2는 문장3보다 비슷..

자카드 유사도(Jaccard similarity)는 두 집합의 유사도를 측정할 때 사용하는 방법 중 하나입니다. 2가지 사례만 들어보겠습니다. 뉴스를 언론에서 자체적으로 만들어낼 수도 있지만, 연합뉴스가 취재한 뉴스를 사와서 조금 수정한 뒤 배포하는 경우도 있습니다. 그러면 다양한 언론사에서 수집한 뉴스 데이터라도 비슷하거나 똑같은 뉴스가 있을 수 있는 것이죠. 만약 구글 뉴스처럼 사용자에게 뉴스를 제공하는 일을 한다면 문서 간 유사도를 파악해 비슷한 뉴스는 걸러내서 서비스해야 합니다. 다른 사례는 두 고객 간의 유사도를 파악하는 일입니다. 넷플릭스처럼 고객이 좋아할 만한 영화를 알고리즘으로 추천하는 일을 할 때, 고객 간 유사도를 사용할 수 있습니다. 나와 취향이 유사한 사람이 좋아한 영화는 내가 봐도..

파이썬 sklearn을 사용하다 보면, 희소행렬(sparse matrix)을 반환해줄 때가 있습니다. from sklearn.feature_extraction.text import CountVectorizer s = ['I love you', 'you love me'] count_vec = CountVectorizer() m = count_vec.fit_transform(s) m toarray 메서드를 이용하면 흔히 사용하는 넘파이 배열로 변환할 수 있지만, 애초에 왜 희소행렬을 반환해주는가 의문이 생깁니다. m.toarray() 희소행렬을 사용하는 이유 위에서는 두 개의 문장을 2 x 3 크기의 행렬로 바꾸는 작은 예시를 들었지만, 실전에서는 대규모 행렬을 다루어야 하는 경우가 흔합니다. 이 경우 메모..