데이터구조와 알고리즘/개념정리 (12) 썸네일형 리스트형 [탐색 알고리즘] 보이어-무어(Boyer-Moore) 방법으로 문자열 탐색하기 Boyer-Moore 탐색 알고리즘 보이어무어 탐색법은 브루트포스 탐색 및 KMP 탐색보다 효율이 좋은 알고리즘이다. int search(String text, String pattern){ int txtIndex; int pattIndex; int txtLen = text.length(); int patLen = pattern.length(); int[] skip = new int[Character.MAX_VALUE + 1]; for(txtIndex = 0; txtIndex patLen - pp) ? skip[txt.charAt(pt)] : patLen - pp; txtIndex += Math.max(skip[text.charAt(txtIndex)], patLen - pattIndex); } retur.. [탐색 알고리즘] KMP법으로 문자열 탐색하기 KMP법 KMP법은 브루트포스법을 개선한 탐색 알고리즘이다. 브루트포스법은 검색하는 도중 문자열이 불일치하면 탐색을 시작한 바로 다음 위치로 이동해 다시 탐색하는 방법이다. 처음부터 끝까지 전부 탐색하기 때문에 그만큼 효율적이지는 못한 방법이다. KMP법을 사용하면 검색이 실패하는 경우, 비교했던 결과를 활용해 다시 검색을 시작할 효율적인 위치를 조정할 수 있다. 참고로 KMP법은 Kruth, Morris, Pratt 3명이 비슷한 시기에 고안했기 때문에 이름의 앞글자를 따서 붙여진 이름이다. int search(String text, String pattern){ int txtIndex = 1; int pattIndex = 0; int[] skip = new int[pattern.length() + 1.. [탐색 알고리즘] 브루트포스법(brute force)으로 문자열 탐색하기 브루트포스 알고리즘 브루트포스법은 문자열을 검색하는 방법 중 기본적인 알고리즘이다. 영어를 직역하면 [brute] - 잔혹한, 악랄한, [force] - 힘, 폭력 이니까 "강제적인 힘"으로 탐색하는 알고리즘 혹은 무차별적으로 대입해 찾아내는 알고리즘이라고 보면 되겠다. 이 알고리즘은 처음부터 끝까지 전부 대입해보는 방법이 주요 특징이다. 비밀번호 숫자 4자리를 해킹하는 상황이라면, 0000부터 9999까지 전부 넣어보고 열리는 것을 찾는 방식이다. Java code int search(String text, String pattern){ //검색할 커서 int textIndex = 0; int patternIndex = 0; while(textIndex != text.length() && pattern.. 정렬 알고리즘5 - 퀵정렬(Quick Sort) 퀵정렬(Quick Sort) 작동방식 정렬할 피봇(기준값)을 정하고, 피봇을 기준으로 크기가 큰 그룹과 작은 그룹으로 나눈다. 나뉜 각 그룹에서 다시 피봇을 정하고, 피봇 기준으로 크기가 큰 그룹과 작은 그룹으로 나눈다. 그룹을 더이상 나눌 수 없을때까지 위 과정을 반복한다. 특징 명칭에서 알 수 있듯이 빠른 정렬 방법이다 분할 정복 알고리즘의 한 기법 퀵 정렬은 부분교환 정렬(Partition Exchange Sort)이라고도 불림. 요소간 비교하는 방식으로 정렬되는 방식 그룹 나누는 함수를 재호출 하는 즉, 재귀적으로 호출하는 방식이다. 임의의 피봇(기준값을 정한다. 꽤 빠른 정렬 방법에 해당한다. 그룹에서 어떤 요소를 피봇으로 정하는지에 따라 정렬의 성능이 결정된다. 데이터를 나열한 순서가 좋지 않.. 이전 1 2 3 다음
