문제 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..