문제 https://www.acmicpc.net/problem/5052 풀이 N = 10^5 이기 때문에, O(NlogN) 이하의 알고리즘이 필요합니다. Trie 라는 자료구조는 문자열의 검색 및 업데이트에 최적화 되어있습니다. Trie란? 문자열의 Search Tree 입니다. 위 그림처럼, 단어들의 첫 글자부터 하나씩 depth가 깊어지며 node를 만들기 시작합니다. Trie의 Update 및 Search 등은 Trie의 트리의 높이만큼의 시간뿐이 걸리지 않습니다. (매우빠름) 위 문제에서는, 각 번호들로 Trie 를 만들면서 단어가 끝나는 지점에 표시를 해줍니다. void Node::insert(char* word) { if(word[0] == '\0') { this->isLast = true; ..

문제 https://www.acmicpc.net/problem/2042 풀이 N => 수의 개수, 10^6 M => 업데이트 횟수, 10^4 K => 구간합을 구하는 횟수, 10^4 일반적인 방법으로, 구간합을 구할 떄 마다 배열의 합을 계산할 경우, 한번의 구간합마다 O(N) 이 걸리게 될 것입니다. 이 경우, 최대 K*N = 10^10 이 걸리게 되므로, 문제를 제한시간 내에 풀 수 없습니다. 따라서, 구간합을 구할 때 O(logN) 이하의 알고리즘이 필요합니다. 이를 구현하기 위하여 Segment tree를 아래와 같이 구현합니다. 트리의 Node가 begin~end 까지의 구간합을 갖고 있다고 가정할 때, 왼쪽 Subtree는 begin~1/2*end 오른쪽 Subtree는 1/2*end+1 ~ ..

1. Linked list 란 ? - 선형 데이터 구조로, 각 원소들은 연속적인 메모리에 존재하지 않으며 ( 즉, linked list의 원소들은 각각 떨어진 메모리 공간에 존재합니다 ), 각 원소들은 pointer를 통해 연결되어있습니다. 2. Linked List의 구현 실제 데이터를 담고있는 Node 와, Node들의 연결체인 Linked List의 구현으로 나뉩니다. 각각의 Node는 이전Node인 prev, 다음 Node인 next 라는 포인터변수를 가지고 있습니다. Linked List는 가장 앞 Node인 head와 가장 뒷 Node인 tail를 가지고 있습니다. 또한, Linked list에 node를 삽입해주는 함수인 add 와, 특정 Node를 지워주는 함수인 remove 함수를 갖고 ..

1. Binary search 란 ? Binary Search 란 정렬 된 배열에서 특정 값을 찾기 위해 사용되는 Search 알고리즘입니다. O(logN) 의 시간복잡도로, 빠른 시간 내에 원하는 값을 찾을 수 있습니다. 2. Binary Search 의 방법 1) 배열의 가장 왼쪽(left) index와 가장 오른쪽(right) index의 중간값(center = (left+right)/2)을 선택하여 찾고자 하는 값과 비교합니다. 2) 원하는 값이 center 보다 작다면, center 기준 왼쪽 배열을 선택하여 1의 과정을 반복합니다. ( right = center ) 3) 원하는 값이 center 보다 크다면, center 기준 오른쪽 배열을 선택하여 1의 과정을 반복합니다. ( left = c..

1. Quick sort 란 ? 분할정복을 이용한 정렬 알고리즘입니다. 정렬 알고리즘 중 O(NlogN) 으로 빠른편에 속하는 알고리즘입니다. 2. Quick Sort 의 자세한 설명 1) Pivot을 Array의 가장 마지막 원소로 선정합니다. 2) [ Pivot 보다 작은 원소들 - Pivot - Pivot 보다 큰 원소들 ] 의 형태가 되도록 배열을 분할합니다. 3) 이 과정을 Pivot 기준 왼쪽배열, 오른쪽 배열을 나누어 반복합니다. (배열을 더이상 나눌 수 없을 때 까지) 3. Code #include using namespace std; // This is quick sort algorithm. // a Array 를 출력해주는 함수입니다. void printArray(int a[], int..

알고리즘 공부를 시작하기 앞서 개발환경 셋팅이 필요합니다. 현재 이름있는 에디터 중 하나인 visual code를 이용한 개발환경 셋팅을 진행할 것입니다. 이 포스트는 Windows OS 기준으로 설명합니다. 1. visual code 설치 https://code.visualstudio.com/download Download Visual Studio Code - Mac, Linux, Windows Visual Studio Code is free and available on your favorite platform - Linux, macOS, and Windows. Download Visual Studio Code to experience a redefined code editor, optimized f..