알고리즘에서 '보이어-무어(Boyer-Moore)' 문자열 검색 알고리즘의 핵심 아이디어는?

Q: 알고리즘에서 '보이어-무어(Boyer-Moore)' 문자열 검색 알고리즘의 핵심 아이디어는?

패턴을 오른쪽 끝부터 비교하며, 불일치 시 패턴을 최대한 많이 건너뛰는 휴리스틱을 사용한다 보이어-무어 알고리즘은 패턴의 오른쪽 끝부터 왼쪽으로 비교합니다. 불일치가 발생하면 'Bad Character'와 'Good Suffix' 두 가지 규칙으로 패턴을 크게 건너뛸 수 있어, 실제 텍스트에서 평균적으로 O(n/m) 이하의 비교만으로 검색이 가능합니다.

어려움 freeCodeCamp

보기 및 정답

A 패턴을 오른쪽 끝부터 비교하며, 불일치 시 패턴을 최대한 많이 건너뛰는 휴리스틱을 사용한다

B 패턴의 첫 글자부터 텍스트와 한 글자씩 순차적으로 비교하며 일치 여부를 확인한다

C 해시 값을 사용하여 패턴과 텍스트의 부분 문자열을 비교하며, 롤링 해시 기법을 활용하는 방식이다

D 접미사 트리를 사전에 구성한 후 트리 탐색을 통해 패턴의 출현 위치를 검색한다

해설

보이어-무어 알고리즘은 패턴의 오른쪽 끝부터 왼쪽으로 비교합니다. 불일치가 발생하면 'Bad Character'와 'Good Suffix' 두 가지 규칙으로 패턴을 크게 건너뛸 수 있어, 실제 텍스트에서 평균적으로 O(n/m) 이하의 비교만으로 검색이 가능합니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

로그인

추가 정보 입력

회원가입

비밀번호 찾기

알고리즘에서 '보이어-무어(Boyer-Moore)' 문자열 검색 알고리즘의 핵심 아이디어는?

해설

코딩, 제대로 배우고 싶다면?

관련 문제

모두를 위한 진짜 쎈 바이브코딩