알고리즘

고지식한 패턴 검색 알고리즘완전탐색, O(NxM)라빈-카프 알고리즘해시 값 함수를 이용, 슬라이딩 윈도우, O(1)x(N-M+1)보이어-무어 알고리즘끝에서부터 문자열을 비교, 뒤로 얼마나 건너뛸지를 미리 skip배열에 저장한다. O(N/M)KMP 알고리즘앞에서부터 문자

최소신장트리 : 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치들의 합이 최소인 신장 트리정점의 개수가 N일때 N(N-1)/4 -> N^2/4를 기준으로 간선이 많다 적다를 판단한다간선이 적으면 Kruskal간선이 많으면 Prim간선중심으로 최소신장트리를