Algorithm
-
[Algorithm] - 문자열 매칭 ( 보이어무어 알고리즘 )Algorithm/Algorithm 2022. 4. 27. 02:20
보이어-무어 알고리즘 부르트포스, KMP 알고리즘보다 향상된 알고리즘이며 더 자주 사용된다고 한다. 보이어-무어 알고리즘의 작동은 KMP 알고리즘과 유사하게 불필요한 비교는 건너뛰고 유의미한 비교만 진행하겠다. 알고리즘 KMP 알고리즘의 개선이 된 알고리즘으로, 시간 복잡도는 최악의 경우 O(N) 평균적인 경우 O(N/M)입니다. 이전에 KMP 알고리즘이 O(N+M)이기 때문에 향상이 이루어졌습니다. KMP 알고리즘의 경우에는 접두사와 접미사가 같은 최대길이를 저장하는 배열을 만들어 앞에서부터 검사를 진행하였다면, 보이어-무어 알고리즘은 문자열을 검색할때 주로 뒤에서 부터 확인합니다. KMP 알고리즘과 같이 건너뛰는 경우를 저장하는 배열(skip_table)을 만들어야 합니다. 이때 배열은 본문 문자열이..
-
[Algorithm] - 기본 문자열 처리Algorithm/Algorithm 2022. 4. 12. 16:05
문자열 처리 문자열 관련하여 반복되는 개념들이 자주 나와 정리하기 위하여 쓴 글입니다. 1. 회문 ( palindrome ) 문자열에 대해서 거꾸로 봐도 동일한지 여부 # 1. 회문(palindrome) temp = '가나다다나가' def palindrome ( data ) : if data == data[::-1] : return True return False print ( palindrome(temp) ) print( temp[::-1]==temp ) 2. 정규 표현식 정규 표현식을 이용한 문자열 컨트롤 ( re ) re.sub( '패턴' , '바꿀문자열' , '적용할 문자열' ) re.compile('패턴') = 문자열 내에서 패턴 찾을 때 사용 match = 문자열의 처음부터 패턴이 일치하는지 ..
-
[Algorithm] - 최소 신장 트리Algorithm/Algorithm 2022. 4. 11. 14:27
신장 트리 연결 그래프의 부분 그래프로서 그 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리로 모든 노드는 적어도 하나의 간선에 연결 ( 단 , 싸이클 X ) 아래 그림은 신장트리를 나타난 예시이다. 아래 그림은 신장트리가 아닌 예시이다. Node에 Edge가 연결되지 않거나 , Cycle이 발생되어 Tree의 개념을 상실한 경우이다. 우측 마지막 그림에서는 Edge가 새롭게 생성된 경우이다. 최소 신장 트리 Graph Edge에 Cost가 부여된 그래프를 가중치 그래프 또는 네트워크라고 합니다. 이때 Cost란 비용이나 거리를 의미하는 값이 될 수 있습니다. 신장 트리 비용은 신장 트리를 구성하는 모든 간선의 비용 중 최소의 합 최소 Cost를 알기 위해서는 Edge들의 가중치를 가장 작은것은..