문자열 매칭을 위한 알고리즘으로 옳은 것은? | [7급 국가직 알고리즘] 25년 1회차 기출문제 상세 페이지
1[7급 국가직 알고리즘] 25년 1회차
문자열 매칭을 위한 알고리즘으로 옳은 것은?
1
합병 정렬 알고리즘
2
라빈 카프(Rabin-Karp) 알고리즘
3
백트래킹(backtracking) 알고리즘
4
후위 순회(postorder traversal) 알고리즘
해설
문자열 매칭 알고리즘은 라빈-카프 알고리즘이다.
라빈-카프는 패턴과 본문 구간을 해시 값으로 바꿔 비교하고, 한 칸 이동할 때 해시를 상수 시간에 갱신해 일치 후보를 빠르게 찾는다.
- 합병 정렬은 분할 정복 방식의 정렬 알고리즘이다.
- 백트래킹은 해 공간을 탐색하다 유망하지 않으면 되돌아가는 탐색 기법이다.
- 후위 순회는 트리의 노드를 왼쪽·오른쪽 서브트리 다음 루트 순으로 방문하는 순회 방법이다.
오류나 개정된 내용이 보이면 알려주세요