'Programming'에 해당되는 글 7건

펜윅 트리(Fenwick Tree) == BIT(Binary Indexed Tree)

- 구간합을 구할 때 log(n)정도의 복잡도를 가지고 있다.

구현을 하기 위해서는 입력받은 값의 2진수에서 처음 1이 나오는 곳의 값을 알아야 한다.

예를 들어서 5의 2진수는 101 이고 처음 1이 나오는 곳의 값은 1이다.

또 다른 예.

3 == 11    -> 1

4 == 100   -> 4

7 == 111   -> 1

12 == 1100-> 4

이렇게 N개를 받은 배열을 A[N]이라고 치면 L[N]은 A의 원소들마다 처음 1이 나오는 곳의 값이다.

또, Tree[i]는 A[i] 부터 앞으로 L[i]개의 합을 저장해놓았다.

L[i]를 구하기 위해서는 아래의 공식이 적용된다.

L[i] = (i & -i);

왜냐하면, 아래의 예시를 보자.

      -num = ~num + 1
       num = 100110101110101100000000000
      ~num = 011001010001010011111111111
      -num = 011001010001010100000000000
num & -num = 000000000000000100000000000

~num은 num의 1의 보수고, +1한게 2의 보수인데 AND를 했을 때 처음 1이 나오는 곳의 값을 얻을 수 있다.

그럼 Tree배열을 사용해서 어떻게 구간합을 구하냐면, 앞서 말했듯이 Tree배열은 A[i]부터 앞으로 L[i]개의 합을 저장해놓았다.

Tree[i]     = A[i] + A[i + 1] + ... + A[i + L[i] - 1]

Tree[i - k - 1] =A[i - k - 1] + A[i - k] + ... + A[i - k - 1 + L[i] - 1]

Tree[i] - Tree[i - k - 1] =  A[i - k] + A[i - k + 1] + ... + A[i + L[i] - 1]

즉, i까지 합 - (k - 1)까지 합 = k부터 i까지의 합 이기때문에 빼주기만 하면 된다.

#include <iostream>

#include <string>

#include <cstring>

using namespace std;

template<typename var>

void Swap(var *des, var *src){

    var temp = *des;

    *des = *src;

    *src = temp;

}

template<typename var>

void quick_sort(var arr[], int left, int right){

    if(left > right)

        return;

    var pivot = arr[left];

    var temp;

    int l = left + 1, r = right;

    while(l <= r){

        while(arr[l] <= pivot) l++;

        while(arr[r] > pivot) r--;

        if(l > r) break;

        // Swap

        Swap(&arr[l], &arr[r]);

    }

    Swap(&arr[r], &arr[left]);

    quick_sort(arr, left, r-1);

    quick_sort(arr, r+1, right);

}

#include <iostream>

void Bubble(int *arr, int arr_len)

{

for(int i = 0; i < arr_len - 1; i++)

{

for(int k = 0; k < (arr_len-i)-1; k++)

{

if( arr[k] < arr[k+1] )

{

int temp = arr[k]

arr[k] = arr[k+1];

arr[k+1] = temp;

}

}

}

int main(int argc, char *argv[])

{

int arr[5] = { 6, 2 , 9, 10, 4 };

Bubble(arr, 5);

for(int i=0; i<5; i++)

{

cout << " " << arr[i];

}

cout << endl;

return 0;

}

두번째 For문에 (arr_len-i)-1을 해준이유는

6 2 9 10 4

배열에서 가장 큰값을 맨뒤로 보내게 되기 때문이다.

2 6 9 4 10

이런식으로 처음 소팅하게되면 10을 제외한 나머지 값들만 정렬하면 되기때문에

(arr_len-i)-1 을 해주었습니다.

2진수변환.zip

하드코딩 or 재귀함수 덩어리 or 둘다

소스코드

Tree.zip

원래 스택에 초기화라는 기능은 없지만 여러번 확인을 해보기 위해 초기화를 만들었습니다.ㅋㅋ

소스코드

스택.zip

예전에 처음 짜봤던 거라 너무 하드 코딩한듯 하네요.ㅋㅋㅋ

소스코드

도서관리.zip