본문 바로가기

전체 글299

ShiftOr 알고리즘 이번 시간에는 ShiftOr이라는 근사 문자열 매칭 알고리즘에 대하여 이야기해보고자 합니다. unix 계열의 agreap이라는 명령어에서 사용하고 있습니다.https://en.wikipedia.org/wiki/Agrep agrep - WikipediaFrom Wikipedia, the free encyclopedia agrep (approximate grep) is an open-source approximate string matching program, developed by Udi Manber and Sun Wu between 1988 and 1991,[1] for use with the Unix operating system. It was later ported to OS/2, DOS, anden.. 2024. 7. 28.
Two-Way String-Matching에 대하여 오늘은 KMP 방식과 Boyer-Moore의 방식을 조합하여 양방향으로 탐색하는 Two-Way String Matching Algorithm에 대하여 알아보도록 하겠습니다. python 3.10에서 적용한 이후 약 25배가량의 엄청난 효과를 보았다고 알려진 알고리즘 입니다.C의 strstr의 하위 문자열 함수를 구현하는데에도 사용되어져 있습니다. 찾고자 하는 문자열이 앞에 있는 경우개수 / 문자열 길이 / 패턴 길이kmp(s)boyer-moore (s)rabin-karp (s)two-way String Macthing (s)100,000 / 2,000 / 107.926154.06316.30524.87610,000 / 5,000 / 100.96616.5241.7982.69 찾고자 하는 문자열이 뒤에 있는 .. 2024. 7. 21.
rabin-karp 이번에는 hashing을 활용한 문자열 매칭 알고리즘인 라빈-카프(rabin-karp)에 대해 알아보고자 합니다.  라빈-카프 알고리즘의 시간복잡도는 O(N)으로 지금까지 진행하였던 왠만한 문자열 매칭 알고리즘보다 빠르다는 장점이 있습니다.그치만, 여러 가지 다양한 부분에서 문제점이 있어 실제 서비스에서는 사용하기 어렵다는 단점이 있습니다. 장점 - 시간이 빠르다단점 - hashing 값이 충돌이 날 수 있다. - overflow가 발생할 수 있다. "abbaba"라는 문자열에 "aba"라는 문자가 포함되어 있는지 확인하는 방법을 예시로 들어보겠습니다.hashing을 사용하기 때문에, 자리수마다의 문자의 아스키 코드 넘버에 특정 값을 곱하여 하나의 숫자 단위로 표현합니다.2를 활용하여 예시를 들면 pat.. 2024. 7. 11.
예외 처리 방법 Spring boot를 사용하시면, 다음과 같은 방법들로 api 요청을 보냅니다.@PostMapping({"/api"})@GetMapping({"/get/api"})만약 다음과 같이 요청이 가능한 api가 있을 때, 없는 api를 요청할 경우, 500에러를 발생하게 됩니다. 해당 에러에 대하여 특정 반환값 or 페이지를 출력하기 위해선 500 에러를 잡아서 다른 response를 보내야 합니다.@ControllerAdvicepublic class GlobalExceptionHandler { @ExceptionHandler(HttpMessageNotReadableException.class) public ResponseEntity handleHttpMessageNotReadableExceptio.. 2024. 7. 7.
Boyer-Moore vs KMP https://lms0806.tistory.com/210 A Fast StringSearching Algorithm 리뷰해당 논문은 boyer–moore 알고리즘 이라고 불리는 kmp와 비슷한 알고리즘에 대하여 설명하고 있습니다. 보이어무어 알고리즘은 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것에서 KMP와 유사lms0806.tistory.com이전 포스팅에서 보이어-무어에 대해 설명중인 논문에 대해 설명을 했었습니다.https://lms0806.tistory.com/211 JAVA에서의 Boyer-Moore해당 글은 보이어 무어 알고리즘을 사용하고 있는 JAVA의 내부 코드에 대해 이야기하고자 합니다.Boyer-Moore에 대해서는 해당 글 참조 부탁드립니다.https://lms0806.tisto.. 2024. 6. 25.
JAVA에서의 Boyer-Moore 해당 글은 보이어 무어 알고리즘을 사용하고 있는 JAVA의 내부 코드에 대해 이야기하고자 합니다.Boyer-Moore에 대해서는 해당 글 참조 부탁드립니다.https://lms0806.tistory.com/210 A Fast StringSearching Algorithm 리뷰해당 논문은 boyer–moore 알고리즘 이라고 불리는 kmp와 비슷한 알고리즘에 대하여 설명하고 있습니다. 보이어무어 알고리즘은 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것에서 KMP와 유사lms0806.tistory.com 해당 글의 마지막에 보이어 무어 알고리즘을 사용하고 있는 BMPatter.java에 대해 링크를 남긴적이 있습니다.이제는 저희가 자주 사용중인 내부 라이브러리 함수 중에 Boyer-Moore 알고리즘을 .. 2024. 6. 23.
A Fast StringSearching Algorithm 리뷰 해당 논문은 boyer–moore 알고리즘 이라고 불리는 kmp와 비슷한 알고리즘에 대하여 설명하고 있습니다. 보이어무어 알고리즘은 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것에서 KMP와 유사합니다. 단, 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용하여 오른쪽 끝부터 비교하여 문자열 매칭을 진행합니다. 다음과 같이 "EAT A APPLE"의 문장에 "APPLE"이라는 단어가 있는지 체크하는 과정을 거친다고 가정해보겠습니다.APPLE의 맨 뒤 단어인 E와 같은 위치에 있는 단어는 A로 서로 다르다는 것을 인식하였습니다.이후, A라는 단어가 찾고자 하는 APPLE 이라는 단어에 포함되어 있는지 확인하고, 포함되어 있다면 해당 위치로 이동을 시킵니다.위치로 이동결과, APPLE이라는 단어를 찾.. 2024. 6. 16.
int vs Integer int와 Integer의 차이는 원시타입과 객체타입로 보시면 됩니다.그러나 둘다 숫자를 저장한다는 공통점을 가지고 있습니다.'그러면 int대신에 Integer로 전부 통일시키면 괜찮지 않을까?' 라는 생각을 하게 되었고, 이를 기반으로 시간 테스트를 진행해 보았습니다. 가장먼저 각 값들을 n번 선언해보았습니다. int a = 0; long beforeTime = System.currentTimeMillis(); for(int i = 0; i  intInteger시간(ms)14 이번엔 값 선언 후, +1 연산을 수행해 보았습니다.  int a = 0; long beforeTime = System.currentTimeMillis(); for(int i = 0; i  intInteger시간(ms)1.. 2024. 6. 9.
알아두면 좋은 for, switch 자바로 소스코드를 작성하다 보면, for문(반복문)이나 switch(조건문) 등의 코드를 작성하게 됩니다.해당 코드들을 편리하게 사용하기 위한 방법들에 대해 이야기해보고자 합니다. for문for문에 대해서는 일반적으로 해당 방식으로 사용합니다.ArrayList arr = new ArrayList():int sum = 0;for(int i = 0; i 굳이 i라는 변수를 for문내에서 말고는 사용하지 않은 경우, 특정 컬렉션들의 값들을 전부 출력하는 경우에는 더 효율적은 foreach문이 존재합니다. foreach문은 해당 방식으로 사용이 가능합니다.ArrayList arr = new ArrayList();int sum = 0;for(int a : arr) { sum += a;} switch문기본적으로 j.. 2024. 6. 2.

티스토리툴바