728x90 반응형 알고리즘6 Efficient String Matching : An Aid to Bibliographic Search 리뷰 이번엔 Efficient String Matching : An Aid to Bibliographic Search이라는 논문에 대해 리뷰해볼까 합니다. 해당 논문은 유명한 문자열 매칭 알고리즘인 "아호코라식"에 대한 논문입니다. 아호 코라식 알고리즘에 대해 이해하기에 앞서 kmp와 trie 알고리즘에 대해 어느 정도 알고계시면 이해하기 쉽습니다. KMP "ABAABC"라는 문자열에 "ABC"라는 단어가 부분 문자열로 존재하는지 체크하는 과정을 단순 반복문을 통하여 진행하게 되면, 맨 앞에 단어부터 해당 형식으로 진행하게 됩니다. kmp 알고리즘을 활용하게 된다면, 해당 형식처럼 진행을 하게 됩니다. kmp는 기존 문자열 매칭방식과 다르게 fail function이라는 실패 함수를 활용하게 됩니다. "ABC.. 2024. 4. 23. 트리를 활용한 문자열 비교 알고리즘 해당 알고리즘은 결정적 유한 오토마타를 학습하면서 떠오른 아이디어로 개발하였습니다. https://ko.wikipedia.org/wiki/%EA%B2%B0%EC%A0%95%EC%A0%81_%EC%9C%A0%ED%95%9C_%EC%83%81%ED%83%9C_%EA%B8%B0%EA%B3%84 결정적 유한 상태 기계 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. --> ko.wikipedia.org 기존 map을 활용하여 중복을 제거하고, containsKey로 해당 문자열을 포함하고 있는지 체크하는 방식이 아닌, 트리를 활용하여 중복도 제거하고, 부분 문자열이 아닌 특정 문자열이 있는지 체크하는 알고리즘 입니다. 기존의 트리를 생각한다면 이런방식의 무방향 트리나, 방향이 있는 트리를 .. 2023. 8. 17. 알고리즘 학습 방법 알고리즘 오픈톡방에 있다 보면 여러 가지 알고리즘 학습 관련 질문들이 들어옵니다. 이에 대한 답변들을 정리해서 블로그 링크를 드리게 위해 작성해 봤습니다. 1. 백엔드 개발자인데 JAVA로 알고리즘을 학습해야 할까요? 언어는 그저 도구이며, 가장 자신 있는 언어로 알고리즘 학습을 하는 게 맞습니다. 그러나, 특정 회사들은 직군별 코딩테스트 언어를 제한하고 있습니다. 이러한 회사들을 위해서라면, JAVA로 준비하는 게 좋으나 한 가지 언어를 잘 다룰 수 있다면, 다른 언어로 알고리즘 준비를 하는 데는 얼마 걸리지 않다고 생각이 들기 때문에 자유롭게 선택하셔서 하시면 될 거 같습니다. 2. 알고리즘 학습은 어떻게 하는 게 좋을까요? 학습 방식은 사람마다 다릅니다. 저는 특정 알고리즘으로 풀리는 문제의 소스를.. 2023. 3. 6. 비트연산 과연 더 빠른가? 비트연산이란? "한 개 혹은 두 개의 이진수에 대해 비트 단위로 적용되는 연산이다." - 위키백과- 비트연산을 사용하는 이유? 컴퓨터가 자료형(int, long double 등등)을 비트로 변환하는 작업을 사용자가 미리 해주기 때문에 빠름 대표적으로 > = /이 있음 정말로 비트연산이 기본 연산보다 빠른가? 여러 언어들마다 실행시간을 측정할 수 있습니다. java 곱하기 + 나누기 long beforeTime = System.currentTimeMillis(); long n = 1, m = 1; for(int i = 0; i < 1000000; i++) { for(int j = 0; j < 5000; j++) { n *= 2; m *= 2; n /= 2; m /= 2; } } long afterTime .. 2023. 2. 28. 이전 1 2 다음 728x90 반응형
