Algorithms (10) 썸네일형 리스트형 KMP 알고리즘 문자열 검색 알고리즘으로 많이 등장하는 KMP 알고리즘에 대해서 알아보겠습니다. KMP는 Knuth Morris Partt의 줄임말로 이 알고리즘을 발견한 사람 이름을 딴 것입니다. 어떤 문자열 A에 문자열 B가 있는지 확인하려면 단순하게 A 문자열(길이 N)과 B 문자열(길이 M)을 하나하나 비교한다면, 시간 복잡도는 O(NM)가 될 것입니다. KMP 알고리즘은 이 시간 복잡도 보다 더 효율적으로 줄여 O(N+M) 만에 문자열을 검색할 수 있는 방법입니다. 어떻게 획기적으로 시간 복잡도를 줄일 수 있었는지 KMP에 대해서 알아보겠습니다. 먼저, KMP 알고리즘을 알기 전에 미리 알아야 할 사전 지식을 살펴보겠습니다. 사전지식 접두사(Prefix)와 접미사(Suffix) 우선 접두사와 접미사가 무엇인지 .. LCA - 최소 공통 조상 LCA(Lowest Common Ancestor) 알고리즘이란?트리에서의 두 정점 u, v에서 가장 가까운 공통 조상을 찾는 알고리즘입니다. 즉, 가장 가까운 공통 조상은 두 정점 u, v를 자손으로 가지는 노드들 중 깊이가 가장 깊은 노드를 의미합니다. 이 글에서는 LCA를 2가지 방법으로 구해보겠습니다. 첫 번째는 O(N)만에 구할 수 있는 알고리즘이고 두 번째 방법은 O(logN)만에 구할 수 있는 알고리즘입니다. 1. O(N) 알고리즘지금 소개해 드릴 이 방법은 간단합니다. 먼저 알고리즘부터 살펴보겠습니다.[알고리즘] 1. 두 정점 u, v의 깊이가 같은지 확인합니다. 만약 두 정점의 깊이가 다르다면 두 정점의 깊이가 같아질 수 있도록 한 칸씩 트리를 타고 올라가면서 깊이를 맞춰줍니다. 2. 두 .. 이전 1 2 다음
