이번 글은 눈 앞에 보이는 최선의 선택만 하는 알고리즘 Greedy 알고리즘에 관한 내용입니다. Greedy 알고리즘은 이전에 다뤘던 Dynamic Programing 이나 Divide and Conquer 알고리즘처럼 사용하기 위한 필수 조건이 있는 것은 아닙니다. 하지만 미래는 내다보지 않고 눈 앞에 보이는 최선의 선택만 하는 탐욕적인 알고리즘이기 때문에 최적의 답을 찾기 위한 조건은 있습니다. 최적의 부분 구조를 갖고 각 단계에서 탐욕스러운 선택이 각 문제에서 최종 답을 구하기 위한 최선의 선택이라는 탐욕적 선택 속성을 갖고 있다면 최적의 답을 보장할 수 있습니다. 간단하고 빠르다는 장점을 갖고 있지만 최적의 답을 보장해주는 조건에 사용하는 것이 아니라면 최적의 답을 보장받지 못한다는 단점을 갖고 ..

이번 글은 하나의 문제는 단 한 번만 풀도록 하는 효율적인 알고리즘, Dynamic Programming에 대해 다룹니다. 동적 계획법(DP, Dynamic Programming)은 한 번 푼 문제는 저장해놓고 공간복잡도를 늘리는 대신 시간복잡도는 줄이는 방식입니다. 지난 포스팅에서 합병 정렬과 퀵 정렬을 하며 다뤘던 분할 정복 방식(Divide and Conquer)과 유사한 알고리즘입니다. 분할 정복 방식도 문제를 더 작은 문제로 나눠서 풀었었죠? 동적 계획법도 비슷한 조건을 갖고 있습니다. DP를 적용하기 위한 2가지 조건입니다. 1. 최적 부분 구조(Optimal Substructure) - 전체 문제의 답을 부분 문제의 답을 이용하여 풀 수 있는 구조 2. 중복되는 부분 문제(Overlappin..

이번 글은 유사도 검정을 통해 알게 된 NMF(Non-negative Matrix Factorization) 기법에 대해 알아보겠습니다. NMF은 유사도 검정 전 텍스트 데이터에서 특성을 추출하는 것 외에도 차원 축소, 토픽 모델링 등에 사용됩니다. NMF는 하나의 객체정보를 음수를 포함하지 않은 두 개의 부분 정보로 인수분해하는 방법입니다. 즉, 음수를 포함하지 않은 행렬 m x n 행렬 R을 음수를 포함하지 않은 행렬 W, H의 곱으로 분해하여 의미 있는 특징을 추출하는 기법입니다. (위키백과) NMF의 목적은 공통 특성만을 가지고 정보를 줄이는 것입니다.이를 수식과 뉴스 기사에서 단어를 기반으로 특성을 추출하는 예시로 표현하면 아래와 같습니다. 행렬 R은 데이터셋으로 행은 샘플, 열은 feature..

kkomoran 형태소 분석기를 이용하던 중 아래와 같은 오류가 발생했습니다. 데이터를 보니 🦚 과 같은 이모지가 들어있더라고요. 이모지는 utf-8 언어셋을 사용하는 형태소 분석기에서 매핑되지 않아 오류가 나타나게 된 것입니다. 아래를 참고하여 해결하였습니다. removing emojis from a string in Python I found this code in Python for removing emojis but it is not working. Can you help with other codes or fix to this? I have observed all my emjois start with \xf but when I try to search for str. stackoverflow.c..

문서의 유사도를 검정하는 방법에 대해 알아보겠습니다. 순서 1. 자카드 유사도 2. 코사인 유사도 3. 코사인 유사도 vs. 유클리디안 유사도 1. 자카드 유사도 자카드 유사도는 두 문서에서 공통되는 단어가 많을수록 다른 단어가 적을수록 비슷한 문서라고 판단하는 가장 간단한 유사도 기법입니다. 식으로 나타내면 공통 단어 개수/전체 단어 개수로 아래와 같습니다. 자카드 유사도를 구하는 함수는 아래와 같습니다. 자카드 유사도는 원소의 개수에 따라 0~1 사이의 값을 가지고 1에 가까울수록 유사도가 높습니다. 2. 코사인 유사도 코사인 유사도는 순서 상관없이 단어를 벡터로 바꾼 후에 벡터 방향을 이용하여 유사도를 계산하는 방법입니다. 벡터의 방향이 같으면 코사인 유사도는 1, 직각이면 0, 다른 방향이면 -1..

지난 포스팅에서 선형 탐색과 이진 탐색에 대한 내용을 다뤘습니다. 이진 탐색을 하기 위해서는 정렬된 상태여야 한다는 조건이 있었죠. 그래서 이번 포스팅은 정렬에 관한 내용을 다루겠습니다. 정렬? 그냥 sort메서드나 sorted함수 사용하면 안되나? 라고 생각하실 수 있지만 아래 그림처럼 각 정렬 알고리즘은 시간/공간 복잡도가 각 상황에 따라 다르기 때문에 상황에 맞는 알고리즘을 사용하는 것이 효율적인지 생각해야 합니다. 순서 1. 선택정렬 2. 삽입 정렬 3. 합병 정렬 4. 퀵 정렬 모든 정렬의 설명은 내림차순 기준입니다. 1. 선택 정렬(Selection Sort) 선택 정렬은 현재 위치에 들어갈 값을 선택하여 정렬하는 것입니다. 아래 그림과 같이 배열 값 중 가장 작은 값을 찾습니다. 가장 작은 ..