Study/Algorithm
-
[Algorithm] 알고리즘 - 문자열 매칭(Pattern Matching)Study/Algorithm 2020. 8. 27. 19:00
문자열 매칭 또는 패턴 매칭은 컴퓨터 과학에서 중요한 문제이다. 노트패드나 워드파일 또는 웹 브라우저 데이터베이스에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. 문자열 매칭 방법의 종류는 아래와 같다. 1. Naive Matching (원시적인 매칭) - $O(mn)$ 2. Automata Algorithm (오토마타를 이용한 매칭) - $\Theta(n + |\sum| m)$ 3. Rabin-Karp Algorithm (라빈-카프 알고리즘) - $\Theta(n)$ 4. Knuth-Morris-Pratt(KMP) Algorithm (KMP알고리즘) - $\Theta(n)$ 5. Boyer-Moore Algorithm (보이어-무어 알고리즘) - $\Theta(n)$ Wor..
-
알고리즘 소개Study/Algorithm 2020. 5. 6. 12:24
알고리즘은 주어진 문제를 해결하기 위한 단계적 절차 또는 방법이다. 알고리즘은 명확하게 기술되어야 하고 유한한 시간 내에 모든 유효한 입력에 대해 올바른 해를 주어야 한다. 주어진 문제를 해결하는 여러 개의 알고리즘들 중 시간적으로 효율적인 알고리즘을 선택해야 한다. 문제를 알고리즘으로 해결하는 단계별 과정들은 다음과 같다. 1. 문제 이해: 주어진 문제를 완전히 이해해야 한다. 2. 알고리즘 설계: 주요 알고리즘 설계 기법을 참고하여 알고리즘을 설계햐야 한다. 3. 정확성 증명: 알고리즘이 정확하다는 것을 증명해야 한다. 4. 알고리즘 분석: 알고리즘의 시간(혹은 공간) 효율성을 분석해야 한다. 5. 알고리즘 구현: 알고리즘은 컴퓨터 프로그램으로 구현해야 한다. 알고리즘은 자연어나 의사 코드로 표현한다..