자료구조: String Matching(2) 지난번에 이어서 패턴 문제를 KMP 알고리즘에서 어떻게 처리하는지에 대해 알아보겠다. KMP 알고리즘은 DFA와 비슷하면서도 조금 더 메모리를 적게 먹는 알고리즘이다. 전반적인 과정은 비슷하지만 텍스트와 패턴을 비교했을때 다른 글자가 나올경우 다른 방법으로 처리하게 된다. 위에가 text 밑에를 pattern이라고 하자. 그리고 위의 숫자가 써있는 표가 있다. 이것의 용도를 차차 설명하겠다. 일단 상황을 하나 가정하자 텍스트에 값들이 써져있다고 생각한다. 아래의 사진을 보자 일단 맨위의 숫자는 생각하지 말고 글자 위에 다음과 같은 숫자들이 있고 빨간색은 패턴과 텍스트가 서로 지금까지 일치함을 뜻한다. 그리고 이제 다음으로 볼글자가 다음과 같이 c로 같다고 생각해보자. c 위에는 어떤 숫자를 써야할까? D.. 더보기 자료구조 : String Matching(1) 이번 포스팅에서는 String Matching이 뭔지에 대해 알아보자. Problem Defintion Text : Simple String of Characters Pattern: Simple String of Characters To Do : find where in the Text Pattern Occurs String Matching 문제는 Text 에서 패턴을 발생하는 곳을 찾는 문제이다. abababcabcabcdabccbaabdabcabcdabcd 다음과 같은 text에서 abcabcd 를 찾는 문제라고 생각해보자. 일반적으로 사람이 이 일을 할때 어떻게 할수 있을까? 대보면서 한글자씩 옆으로 밀어가며 찾을 것이다. 이 방법은 상당히 느린 작업이고 이것보다 더 빠르게 찾는 방법이 존재한다. .. 더보기 자료구조 : Array for Search, Insert, Delete 이번 포스트에는 자료구조에서 자주 쓰이는 배열에서의 Search, Insert, Delete 에 대해 알아보겠다. Search, Insert, Delete 자료구조의 가장 중요한 연산들 책상 위를 보시오! (우리가 평소에도 많이 하는 작업들 공책에 쓰고 지우고...) 그렇다고 모든 자료 구조에 해당하는 것은 아니다. 예) 그래프 Item: 저장되는 대상을 부를 이름 정수만 가능한 것으로 생각을 하자. 임의의 배열을 통해서 알아보자. Array 임의의 배열의 형태를 생각해보자 배열은 index와 value로 구성되어있다. 그렇다면 위 배열을 토대로 배열 안에서 삽입, 삭제, 검색이 어떻게 이루어지는지 알아보자 How to Store Items in an Array? Packed vs Unpacked (빈자.. 더보기 이전 1 ··· 6 7 8 9 10 11 12 다음
