코딩못하는사람

트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조입니다. 우리가 검색을 할 때 자동으로 완성시켜주는 단어들을 보면 트라이가 사용된 예입니다. 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간복잡도를 갖고 길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것입니다. 우리는 문자열에서의 검색을 개선하기 위하여 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있습니다. 트라이의 형태 아래 그림은 문자열 집합 = {"AE" , "ATV", "ATES", "ATEV", "DE" ,"DC"} 가 존재할 때 트라이의 예입니다. 다음과 같은 모양으로 트리를 만들어서 연산을 문자열의 길이만큼하는 시간복잡도를 갖게하는 것입니다. 이에 따라 트리의 특징은 시간이 O(M)..

Supervised Learning (지도학습) Linear Regression (예측) Binary Classification (이진 분류) Multi-label Classification (다중 분류) Linear Regression (선형 회귀분석) Cost function (Loss Function) 예측을 하는 값과 실제 결과 값의 차이를 나타내는 함수이다. 예측을 하는 데이터를 바꾸어가면서 실제 결과 값과 차이를 그래프로 나타낼 수 있다. 제일 적절한 예측을 하는 가설은 바로 cost function이 최소가 되는 가설일 것이다 경사 하강법 sklearn LinearRegression 사용법 from sklearn.linear_model import LinearRegression을 통하여 싸이..

1 NumPy 기본: 배열과 벡터 연산 Numpy 에서 제공하는 것 • 효율적인 다차원 배열인 ndarray는 빠른 배열 계산과 유연한 브로드캐스팅 기능 제공 • 반복문을 작성할 필요 없이 전체 데이터 배열을 빠르게 계산 할 수 있는 표준 수학함수 • 배열 데이터를 디스크에 쓰거나 읽을 수 있는 도구와 메모리에 적재된 파일을 다루는 도구 • 선형대수, 난수 생성기, 퓨리에 변환 기능 데이터 분석 에서 중요하게 생각하는 기능 • 벡터 배열 상에서 데이터 가공, 정제 , 부분집합, 필터링 변형 그리고 다른 여러 종류의 연산을 빠르게 수행 • 정렬, 유일 원소 찾기, 집한 연산 같은 일방적인 배열 처리 알고리즘 • 통계의 효과적인 표현과 데이터를 수집 요약하기 • 다양한 종류의 데이터를 병합하고 역끼 위한 데..

KMP 알고리즘이란? 우리가 문서에서 컨트롤+F눌러서 문자를 검색하던 항상 쓰였던 알고리즘이다. 알고리즘을 어떻게 구현하였을지 단순히 생각해보면 당연히 모든 인덱스에서 한번씩 패턴을돌려보는 N이 텍스트의 길이,M이 패턴의 길이라고 할 때 O(N*M)을 생각할 것이다. 하지만 KMP알고리즘은 O(N+M)정도로 줄여준다 KMP알고리즘에는 두가지 함수가 필요하다 전처리 테이블 KMP알고리즘은 접두사와 접미사를 기반으로 만드는 전처리 테이블이 필요하다 접두사와 접미사 같을때의 최대길이를 저장해주는 것이다 코드로 구현하면 다음과 같다. KMP 함수구현 이렇게 전처리 테이블을 만들면 이제 테이블을 활용하여 겹치는 부분들을 활용하여 j는 순서대로 돌지만 i를 테이블값에 따라 빙빙 돌리면 된다 그림으로 보면 3번 인덱..