Overview 최소 신장 트리(Minimum Spanning Tree | MST)란 한 그래프에 속해 있는 모든 정점을 잇는 최소 비용의 부분 그래프를 의미합니다. 다시 말해서, 가장 적은 비용으로 모든 정점들을 이어주는 그래프를 의미하는 것입니다. 네트워크 장비에 관한 포스팅에서 스위치(네트워크 장비)를 통해 여러 개의 컴퓨터들을 연결하는 과정에 대해서 살펴보았습니다. 이 때, 컴퓨터 사이에 두 개 이상의 네트워크 경로가 존재할 경우, 네트워크 루핑 현상이 발생할 수 있으며, 이를 막기 위해 스위치는 스패닝 트리 프로토콜을 통해 컴퓨터와 컴퓨터 사이에는 단 하나의 루트만 존재하게끔 조정해 줍니다. 이 스패닝 트리 프로토콜이 바로 최소 스패닝 트리와 밀접하게 연관되어 있습니다. 최소 신장 트리는 최소 ..

Overview & Definition 머지 소트 트리는 백준 알고리즘 문제 13544 수열과 쿼리3 문제를 해결하기 위해서 사용하였던 자료구조입니다. 세그먼트 트리를 변형하여 만든 구조이기 때문에 초기화 하는 방법과, 쿼리 날리는 방법 등이 세그먼트 트리와 상당히 유사합니다. 세그먼트 트리는 리프 노드(Leaf Node)에 각 배열의 원소를 집어넣고, 부모노드에 자식 노드들의 최댓값이나 최솟값, 혹은 부분합을 저장해서 특정 구간에 대한 질의(Query)를 빠르게 처리하는데 특화된 자료구조입니다. 머지 소트 트리는 부모 노드에 각 자식 노드를 머지한 결과값을 저장한 배열을 저장합니다. 예를 들어서 왼쪽 자식 노드가 [1, 3, 5], 오른쪽 자식 노드가 [2, 4, 6]인 상태라면, 부모 노드는 [1, ..

Overview 트리 자료구조는 데이터를 효율적으로 저장하고, 빠른 시간에 탐색, 수정 및 추가 삭제 연산을 진행할 수 있도록 도와줍니다. 구간 트리(Segment Tree)는 이 트리 구조의 이점을 살려서 특정 구간에서의 최대, 최소 값등을 빠르게 구할 수 있도록 합니다. 구간 트리는 특히 일차원 배열의 특정 구간에 대한 질문들(최대, 최소값 등)을 빠르게 대답하는 데에 주로 사용합니다. 예를 들어, 일차원 배열의 특정 구간에서 최대인 값을 찾기 위해서는 특정 구간을 일일이 순회하면서 최소값을 찾아야 했습니다. 하지만, 구간 트리를 이용하면 특정 구간의 최대값을 미리 전처리해서 부모 노드에 저장하는 방식을 취하기 때문에 (일종의 다이나믹 프로그래밍 방법이라고도 할 수 있습니다.) 훨씬 더 빠른 시간에 ..

Overview 펜윅 트리 (Fenwick Tree)는 구간 합을 빠르게 구하기 위해 고안된 자료구조입니다. 결론부터 말씀을 드리면 구간트리의 진화된 형태라고도 할 수 있습니다. 기존의 배열 자체에서 구간 합을 구하기 위해서는 해당 구간을 모두 순회하면서 값을 더해야 하므로 구간 길이에 비례하는 시간이 소요됩니다. O(N)의 시간복잡도를 갖는다는 의미이죠. 이를 더 빠르게 구현하기 위해 고안된 자료구조가 바로 구간트리이며, 구간트리가 갖는 장점을 살리면서 메모리를 훨씬 더 절약할 수 있도록 고안된 자료구조가 바로 펜윅 트리입니다. (구간 트리에 관한 자세한 내용은 구간 트리를 다룬 포스팅을 참고해주세요) Definition 펜윅 트리가 갖는 중요한 아이디어는 구간 합을 구하기 위해서 부분 합만을 빠르게 ..

Overview 문자열 매칭은 여러 곳곳에서 흔하게 사용되는 알고리즘 중의 하나입니다. 당장에 브라우저에서 command + f 나 ctrl + f를 눌렀을때 나타나는 검색 바에서도 문자열 매칭을 통해 찾고자하는 문자열의 위치를 알려줍니다. 가장 단순한 문자열 매칭 방법은 해당 페이지에 있는 모든 문자열에 대해서 찾고자 하는 문자열을 일일이 대입하는 방식일 것입니다. 전체 문자열의 길이를 $n$, 찾고자 하는 문자열의 길이를 $m$이라고 하면 $O(mn)$ 의 시간이 소요되게 될 것입니다. 이는 문자열의 길이가 굉장히 긴 경우에는 심각한 비효율성을 초래하기 때문에 개선의 필요성이 있으며, 이를 효율적으로 개선한 방법 중의 하나 ( $ O(m+n) $ 의 시간복잡도를 가지고 있음 )가 이제 소개할 KMP알..