알고리즘2 KMP 알고리즘 KMP 알고리즘은 빠른 문자열 검색을 돕는 알고리즘이다. 찾고자 하는 문자열을 pattern 이라고 하고 모든 문장을 all string 라고 하자. KMP 알고리즘을 구현하기 위해 해야할 것이 있다. 1. Pattern 문자열을 이용해 pi(파이)배열을 만들어야 한다. 2. pi 배열을 이용해 빠른 문자열을 검색해준다. pi배열 이란, Pattern 문자열에 있는 접두사 (Prefix) 와 접미사 (Suffix)가 같아 지는 최대 길이를 나열해 놓은 배열이다. 말로 설명하지니 좀 어려우므로 아래 그림을 통해 확인해보자. 예를 들어, pattern이 "abcdabc" 라면 단어의 길이가 7인데, 1개씩 늘려가며 접두사와 접미사가 겹치는 최대 길이를 나타내 보면, pi배열은 [0, 0, 0, 0, 1, 2.. 2023. 4. 26. 동적 프로그래밍(Dynamic Programming)을 이용한 피보나치(Fibonacci) 수 구하기 (Python) 보통 코딩을 배울 때, 피보나치 구현을 배울 때는 재귀(Recursion)를 이용한 방법으로 구현한다. 그러나 재귀 방식의 알고리즘은 시간복잡도가 O(n^2)로 아주 오래 걸리기 때문에 보통은 동적 프로그래밍(DP)를 이용하는 편이다. 동적 프로그래밍의 시간복잡도는 O(n)이다. 재귀 방식의 피보나치 수를 구하는 함수 def recursion(n): if n==1 or n==2: return 1 else: return fibo(n-1) + fibo(n-2) 동적 프로그래밍 방식의 피보나치 수를 구하는 함수 def dp(n): dp = [1,1] if n==1 or n== 2: return 1 for i in range(2,n): dp.append(dp[i-1]+dp[i-2]) return dp[-1] 2022. 1. 11. 이전 1 다음
