KMP(Knuth-Morris-Pratt) 알고리즘과 보이어－무어(Bo… | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 25년 1회차
KMP(Knuth-Morris-Pratt) 알고리즘과 보이어－무어(Boyer-Moore) 알고리즘에 대한 설명으로 옳지 않은 것은?
1
KMP 알고리즘은 패턴 문자열의 첫 문자부터 순차적으로 대상 문자열과 부분 문자열의 일치 여부를 판단한다.
2
KMP 알고리즘은 패턴 문자열과 대상 문자열을 한 차례 비교한 후 얻을 수 있는 추가 정보로 비교 횟수를 감소시킨다.
3
보이어－무어 알고리즘은 패턴 문자열의 마지막 문자부터 역순으로 대상 문자열과 부분 문자열의 일치 여부를 판단한다.
4
보이어－무어 알고리즘은 전처리(preprocessing) 과정 없이 곧바로 일치 여부를 판단할 수 있다.
해설
옳지 않은 설명은 보이어-무어 알고리즘이 전처리 없이 곧바로 비교한다는 내용이다.
보이어-무어는 비교 전에 패턴을 분석해 나쁜 문자 이동표·착한 접미부 이동표를 만들어 두고, 불일치 시 이 표로 건너뛸 거리를 정한다.
- KMP는 패턴의 첫 문자부터 왼쪽에서 오른쪽으로 비교하므로 옳다.
- KMP는 앞선 비교에서 얻은 접두부·접미부 일치 정보(실패 함수)로 비교 횟수를 줄이므로 옳다.
- 보이어-무어는 패턴의 마지막 문자부터 역순으로 비교하므로 옳다.
오류나 개정된 내용이 보이면 알려주세요