알고리즘26 Rabin-Karp 알고리즘 KMP 알고리즘과 더불어 문자열을 탐색하는 알고리즘 중 하나이다. Rabin-Karp 알고리즘은 해싱을 이용해서 문자열을 비교하는 알고리즘으로, 최악의 경우 O(MN)이지만 평균적으로는 선형에 가까운 빠른 속도를 가진다. Rabin-Karp 알고리즘은 다음과 같이 진행된다. - 패턴의 해시값을 계산한다. - 비교하려는 문자열에서 패턴의 길이만큼 잘라서 해시값을 계산한다. - 해시값을 비교한다. (해시값이 같다면 정확히 일치하는 것이고, 다르다면 첫글자를 빼주고 다음 글자를 추가한다.) - (문자열 - 패턴)의 길이만큼 반복하고 종료한다. 예를 들어 패턴은 ABAC 문자열은 CABABACD라고 하면 패턴의 해시값을 다음과 같이 구한다. static int cal(String pattern){ int sum.. 2023. 4. 14. KMP 알고리즘(2) 지난 번에는 KMP 알고리즘의 패턴에 관해 알아보았다. 그럼 이번에는 그 패턴에서 구한 이동 위치 저장 배열을 가지고 어떻게 비교 문자열에 적용하는지 확인해보자. 패턴은 다음과 같다. ABCDABA 비교할 문자열은 다음과 같다. ABCDABCDABABCDCD 이 두 문자열을 비교할 것이다. 우선 코드로 살펴보자. static void KMP(String str, String pattern){ int []arr = getTable(pattern); char[] text = str.toCharArray(); char[] pt = pattern.toCharArray(); int j=0; for(int i=0;i0&& text[i]!=pt[j]) j=arr[j-1]; if(text[i]==pt[j]){ if(j.. 2023. 4. 14. KMP 알고리즘(1) KMP 알고리즘은 패턴 매칭에 사용되는 알고리즘으로 Knuth, Morris, Pratt이라는 천재 세명이 만든 알고리즘이다. 기본적인 개념은 패턴을 매칭하는 과정에서 불일치가 발생한 텍스트 문자열의 앞 부분에 어떤 문자가 있는지를 미리 알고, 이를 통해 불일치가 발생한 앞 부분에 대해 다시 비교하지 않고 매칭을 수행할 수 있다. 라는 개념이다. 브루트 포스로다가 때려 박아서 비교하는 거는 시간 복잡도가 O(MN)이되는데 반해, KMP 알고리즘의 시간 복잡도는 O(N+M)이 된다. 여기서 N은 문자열 길이이고, M은 패턴의 길이다. 이런 개념을 가지고 KMP 알고리즘을 알아보자. 일단 KMP알고리즘은 접두사와 접미사를 차례대로 이용한다. ABCABCABC 라는 문자가 있다면 한개를 비교할 때의 접두사와 .. 2023. 4. 14. [S/W 문제해결 응용] 10일차 - 작업순서 D6 문제는 위와 같다. 간단하게 정리하자면 작업들에는 먼저 선행해야할 작업들이 있고, 이 작업들을 모두 수행하는 순서를 출력하라는 것이다. 위상정렬을 사용해서 출력하면된다. 위상정렬 알고리즘을 통해 Queue에 넣고 Queue에서 빼내면서 차례대로 출력을 하면 된다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; publ.. 2023. 4. 3. 이전 1 2 3 4 ··· 7 다음
