KMP(Knuth-Morris-Pratt) 알고리즘의 주된 용도는?

어려움 freeCodeCamp

보기 및 정답

A 문자열에서 패턴을 O(n + m) 시간에 효율적으로 검색하는 알고리즘이다(n: 텍스트 길이, m: 패턴 길이)

B 배열의 각 원소를 비교 없이 자릿수별로 분류하여 O(n) 시간 내에 정렬하는 알고리즘이다

C 가중치가 있는 그래프에서 출발 정점부터 모든 다른 정점까지의 최단 경로를 구하는 알고리즘이다

D 편향된 이진 탐색 트리의 높이를 줄이기 위해 좌우 회전(rotation) 연산을 수행하여 균형 있게 재구성하는 알고리즘이다

KMP 알고리즘은 문자열 검색에서 실패 함수(failure function)를 사전 계산하여, 불일치 발생 시 이미 비교한 정보를 활용해 건너뜁니다. 단순 비교의 O(nm) 대비 O(n+m)으로 효율적이며, 텍스트 에디터 검색, DNA 서열 매칭 등에 사용됩니다.

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

로그인