BM 검색 알고리즘

알고리즘/검색 알고리즘 2020.11.17

BM 검색 알고리즘이란? 문자열을 데이터에서 검색할 때, 검색할 문자열의 끝에서부터 비교하다가 일치하지 않는 문자를 만나면 검색할 문자열만큼 이동하여 검색을 수행하는 알고리즘. 고안자인 Boyer-Moore 법이라고도 한다. - 찾고자 하는 문자열이 중복되지 않을 경우 예를 들어 다음과 같은 데이터에서 'MYBK' 처럼 중복되지 않는 문자열을 찾을 경우. M Y B B A G M Y B K 찾고자 하는 문자열인 'MYBK'의 마지막 문자 'K'와 배열의 4번째 데이터, 배열[3] 데이터인 'B'를 비교한다. 서로 다르므로 4칸을 건너뛰고 검색한다. - 찾고자 하는 문자열이 중복되는 경우 예를 들어 다음과 같은 데이터에서 'MBMBC' 처럼 중복되는 문자열을 찾을 경우. M B M B M B C K A B..

KMP 검색 알고리즘

알고리즘/검색 알고리즘 2020.11.17

KMP 검색 알고리즘이란? 문자열 안에서 부분 문자열을 검색할 때, 검색에 실패한 위치를 기반으로 비교할 필요가 없는 문자열은 건너뛰고, 다음 번 검색 위치를 결정하는 알고리즘. - 찾고자 하는 문자열이 중복되지 않을 경우 예를 들어 다음과 같은 데이터에서 'MYBK' 처럼 중복되지 않는 문자열을 찾을 경우. M Y B B A G M Y B K 'MYB'까지는 일치하지만 4번째 K가 일치하지 않는다. 이럴 경우 'MYB' 다음 위치부터 검색을 다시 시작한다. - 찾고자 하는 문자열이 중복되는 경우 예를 들어 다음과 같은 데이터에서 'MBMBC' 처럼 중복되는 문자열을 찾을 경우. M B M B M B C K A B M B M C M B A B C A 'MBMB' 까지는 일치하지만 5번째 C가 일치하지 않..

문자열 검색(String Search) 알고리즘 1. 브루트-포스법

알고리즘/검색 알고리즘 2020.11.17

문자열 검색(String Search) 알고리즘 주어진 문자열에서 찾고자 하는 문자열이 있을 때, 해당 문자열의 위치를 찾는 알고리즘. 브루트-포스법이란? 텍스트의 맨 앞부터 한 문자씩 살펴보며 패턴의 첫 자와 일치하는 문자를 찾고, 일치한다면 그 문자부터 패턴의 나머지와 일치하는지 검사한다. 불일치한다면 텍스트의 다음 문자부터 다시 검사한다. 선형검색을 확장한 알고리즘으로, 단순법, 소박법이라고도 한다. 자바로 구현하기 package algorithm; public class BFMatch { //브루트-포스법으로 문자열을 검색하는 메서드 static int bfMatch(String txt, String pat) { int pt = 0;//txt 커서 int pp = 0;//pat 커서 //텍스트 커..

이진 검색(Binary Search) 알고리즘

알고리즘/검색 알고리즘 2020.11.17

이진 검색(Binary Search) 알고리즘이란? 이미 키 값으로 정렬된 데이터를 대상으로, 중앙 값을 이용해 검색하는 알고리즘. 전체 데이터의 중앙 값을 찾아 검색하려는 데이터와 비교하여 중앙 값보다 작으면 왼쪽 부분의 중앙 값을 다시 취하고, 중앙 값보다 크면 오른쪽 부분의 중앙 값을 다시 취해 비교하는 작업을 반복하는 알고리즘. 선형 검색보다 좀 더 빠르다. 자바로 구현하기 //요솟수가 n인 배열 a에서 key와 같은 요소를 이진 검색한다. static int binSearch(int[] a, int n, int key) { int pl = 0; int pr = n-1; while(pl a[pc]) { pl = pc+1; } else if (key < a[pc]) { pr = pc-1; } } r..

순차 검색(Sequential Search) 또는 선형 검색(Linear Search) 알고리즘

알고리즘/검색 알고리즘 2020.11.17

순차 검색(Sequential Search) 알고리즘이란? 주어진 데이터를 처음부터 검색하는 알고리즘. 무작위로 늘어놓은 데이터 모임에서 검색을 수행할 때 유효. 순차 검색 종료조건 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 검색할 값과 같은 요소를 발견한 경우 자바로 구현하기 //요솟수가 n인 배열 a에서 key와 같은 요소를 선형 검색한다. static int seqSearch(int[] a, int n, int key) { for(int i=0; i

검색 알고리즘

알고리즘/검색 알고리즘 2020.11.17

검색 : 많은 데이터 속에서 원하는 데이터를 찾는 것. 검색 알고리즘이란? 정해진 단위 절차를 반복하면서 원하는 결과를 찾는 것. 검색 알고리즘 종류 1. 배열 검색 (배열 자료구조를 이용한 검색) 순차 검색(Sequential Search) 또는 선형 검색(Linear Search) 이진 검색(Binary Search) 문자열 검색(String Search) KMP 검색 알고리즘을 이용한 문자열 검색 BM 검색 알고리즘을 이용한 문자열 검색 2. 선형 리스트 검색 3. 이진 검색 트리 검색