binary indexed tree 에 대한 설명 : 

[1] https://en.wikipedia.org/wiki/Fenwick_tree

[2] https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-%20trees/

[3] http://blog.secmem.org/486

트리 생성 (update)

구간 합 [1, x]

wiki : http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

특정 두 노드 간의 최단 거리를 구하는 데 사용함.

distance 가 양수 값을 가지는 경우에만 적용.

알고리즘:

아래 알고리즘에서 u := Extract_Min(Q)는 점의 집합 Q에서 가장 작은 d[u]값을 찾은 다음 그 점 u를 Q에서 제거한 후 반환하는 함수를 가리킨다.

만약 모든 v에 대해서가 아니라 특정한 s에서 t까지의 최단 거리만을 알고 싶다면 9번째 행에서 u = t일 때 종료하면 된다.

s에서 t까지의 최단 경로는 다음과 같이 얻을 수 있다.

이제 S는 s에서 t까지의 최단경로 상에 있는 점들의 목록이 된다.

문제 : 

Extract_Min() 를 구현하는 방법

소스 코드:

binary heap 구현 시,

root 를 0 으로 하는 것과 1 로 하는 것의 차이를 보자.

* i 의 child 

* i 의 parent

root 의 index 를 1 로 하여 구현하는 것이 계산이 더 간단하다.

뿐만 아니라 다음과 같은 이점이 있다.

index 를 2 진수로 변환하면, 같은 depth 인 경우 자리 수가 같아진다.

또한 가장 왼쪽 node 의 index 는 항상 첫 자리가 1 이고 나머지 자리는 모두 0 이 된다.

가장 마지막 node 의 index 는 항상 모든 자리가 1 이다.

이런 이유로, index 값만으로 depth 를 알 수 있고 그 외 유용한 연산을 더 빠르고 간편하게 해 낼 수 있다.

특별한 이유가 없다면 binary heap 구현은 root index 를 1 로 하는 게 좋다.

maximum subarray problem [1]

주어진 배열에서 합이 가장 큰 구간을 찾는 문제이다.

다음은 O(N^3) 방법. 전체를 순서대로 뒤지는 방법이다.

아래는 O(N^2) 방법.

int max_sum() { int input [] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; size_t size = sizeof(input)/sizeof(int); int i, j, sum; int value = 0xFFFFFFFF; for (i = 0; i < size; i++) { sum = 0; for (j = i; j < size; j++) { sum += input[j]; value = max(value, sum); } } trace("%d\n", value); return value; }

O(nlog n) 방법 : divide and conquer algorithm

int input [] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; size_t size = sizeof(input)/sizeof(int); trace("%d\n", max_sum(input, 0, size - 1)); int max_sum(int input[], int lo, int hi) { // 하나 뿐일 때 if (lo == hi) return input[lo]; int mid = (lo + hi) / 2; int left = 0xFFFFFFFF, right = 0xFFFFFFFF; int sum = 0; for (int i = mid; i >= lo; i--) { sum += input[i]; left = max(left, sum); } sum = 0; for (int j = mid + 1; j <= hi; j++) { sum += input[j]; right = max(right, sum); } int single = max(max_sum(input, lo, mid), max_sum(input, mid+1, hi)); return max(left + right, single); }

O(n) 방법 : Kadane's algorithm

int max_sum() { int input [] = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; size_t size = sizeof(input)/sizeof(int); int max_so_far = input[0], max_ending_here = input[0]; for (int i = 1; i < size; i++) { if (max_ending_here < 0) { max_ending_here = input[i]; // begin_temp = i; } else { max_ending_here += input[i]; } max_so_far = max(max_ending_here, max_so_far); //if (max_ending_here > max_so_far) { // begin = begin_temp; // end = i; //} } trace("%d\n", max_so_far); return max_so_far; }

references : 

[1] http://en.wikipedia.org/wiki/Maximum_subarray_problem

n 개 가운데 m 개를 고르는 모든 조합 ...

첫 번째 방법은 vector 를 이용하여 적절한 index 를 push 하는 방법이다.

일반적인 방법.

두 번째는 n 이 31 이하인 경우 사용가능하다.

bit 연산을 하므로 매우 빠르다.

대략 비교해 보면 후자가 5 ~ 7 배 빠른 것같다. (물론 경우에 따라 다르겠지만)

어차피 n 이 너무 커지면 경우의 수가 너무 많아 계산이 불가능하므로, 후자가 유용하게 사용될 수 있을 듯.

구글링 해 보니 요런 것도 있다.

http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/

이 페이지는 bit twidding hacks 에 관한 내용으로, 다음 페이지의 내용 중 일부를 해석, 분석, 시험한 내용입니다.

http://graphics.stanford.edu/~seander/bithacks.html

* 참고 : 

two's complement

http://en.wikipedia.org/wiki/Two's_complement

Compute the integer absolute value (abs) without branching

v 가 양수인 경우 (v = 10)

v 가 음수인 경우 (v = -10)

2's complement 를 구하는 방법과 동일하다.

Compute the minimum (min) or maximum (max) of two integers without branching

Determining if an integer is a power of 2

만약 v 가 0010 (2) 이라면,

만약 v 가 0110 (2) 이라면,

v 가 0 이면 true 가 되는 문제가 있다. (별도 handling 필요)

이 연산은 정수의 가장 오른쪽 1 을 하나 지우는 것과 같다.

그러므로, 비트 가운데 1 이 하나만 있는 경우 (power of 2) 가장 오른쪽 비트를 지우면 0 이 된다.

따라서, 음수에는 안 된다. (예문은 검사할 변수가 unsigned 로 되어 있음)

Conditionally set or clear bits without branching

조건 f 에 따라서 w 의 특정 비트 (m) 를 set 하거나 clear 하기 

여기서는 f 값이 true 인 경우 set, false 일 때 clear 한다.

f 는 1 이고 -f 는 1111 이 된다.

여기에 (-f ^ w) 를 계산하면 w 의 모든 비트를 뒤집니다.

그 결과에 & m 을 계산하면, set 하려는 비트 중에 0인 비트에만 1 이 할당 된다.

따라서, 그 결과에 w 와 XOR 를 씌우면, 기존에 이미 set 된 비트는 그대로 1 로 남고, 0 이었던 비트도 1 로 set 된다.

Counting bits set (naive way)

Counting bits set, Brian Kernighan's way

루프 한 번 마다 v & v - 1 을 하면 가장 오른쪽 비트(least significant bit)를 지운다.

gcc 에서는 내장 함수 __builtin_popcount() 를 사용하면 된다.

visual studio 2008 에서는 _mm_popcnt_u32(), _mm_popcnt_u64() 이런 게 있다. <nmmintrin.h> 필요.

참고 : http://msdn.microsoft.com/en-us/library/bb514083(v=vs.90).aspx

Select the bit position (from the most-significant bit) with the given count (rank)

The following 64-bit code selects the position of the r^th 1 bit when counting from the left. In other words if we start at the most significant bit and proceed to the right, counting the number of bits set to 1 until we reach the desired rank, r, then the position where we stop is returned. If the rank requested exceeds the count of bits set, then 64 is returned. The code may be modified for 32-bit or counting from the right.

Swapping values with XOR

Swapping individual bits with XOR

Compute modulus division by 1 << s without a division operator

d - 1 은 d 번째 부터 0111 이 된다.

즉 d 가 1000 이었다면 d - 1 은 0111 이다.

따라서 n 과 & 연산을 하면 하위 3 자리만 남는다.

Find the log base 2 of an integer with the MSB N set in O(N) operations (the obvious way)

v 를 한 칸씩 shift 하면서 r 을 증가 시킴.

Find the integer log base 2 of an integer with an 64-bit IEEE float

The code above loads a 64-bit (IEEE-754 floating-point) double with a 32-bit integer (with no paddding bits) by storing the integer in the mantissa while the exponent is set to 2⁵². From this newly minted double, 2⁵² (expressed as a double) is subtracted, which sets the resulting exponent to the log base 2 of the input value, v. All that is left is shifting the exponent bits into position (20 bits right) and subtracting the bias, 0x3FF (which is 1023 decimal). This technique only takes 5 operations, but many CPUs are slow at manipulating doubles, and the endianess of the architecture must be accommodated.

Eric Cole sent me this on January 15, 2006. Evan Felix pointed out a typo on April 4, 2006. Vincent Lefèvre told me on July 9, 2008 to change the endian check to use the float's endian, which could differ from the integer's endian.

이해 불가 ㅡㅡ;

Count the consecutive zero bits (trailing) on the right linearly

v ^ v - 1 을 하면 가장 가장 오른쪽 비트 (lsb) 자리부터 1이 채워지고, 한 번 shift 하면 1 이 하나 지워진다.

이 결과에서 shift 를 한 번 하면 11 만 남는다.

for 문은 1 의 개수를 센다.

gcc 라면 __builtin_ctz() 함수를 사용할 수 있다.

visual studio 에서는 _BitScanForward() 가 있다.

참고 : http://msdn.microsoft.com/en-us/library/wfd9z0bb%28VS.80%29.aspx

반대 방향으로 0 의 개수를 세는 함수는,

gcc 와 visual studio 에 대해서 각각 __builtin_clz(), _BitScanReverse() 가 있음.

Compute the lexicographically next bit permutation

Suppose we have a pattern of N bits set to 1 in an integer and we want the next permutation of N 1 bits in a lexicographical sense. For example, if N is 3 and the bit pattern is 00010011, the next patterns would be 00010101, 00010110, 00011001,00011010, 00011100, 00100011, and so forth. The following is a fast way to compute the next permutation.

또는,

복잡하군요 @.@

테스트 코드 : 

만약, 최고 값까지 다다른 다음에 한 번 더 호출하면 1 의 개수가 하나 줄어든 값이 튀어 나온다. (주의 !)

1. intro

유명한 문제 tsp 는 링크에서 자세한 설명을. [link]

문제를 요약하자면,

n 개의 도시가 주어지고, 각 도시간의 거리가 주어질 때,

모든 도시를 가장 최소의 거리로 이동하는 경로를 찾는 문제이다.

이 문제는 대표적인 NP-Hard 문제이며, time complexity 는 O(2^n) 이다.

 

2. 풀이

2.1. 모든 경우의 수에 대해 값 구하기

이렇게 하면 물론 안 되겠지만, 모든 경로의 수는 입력 도시 수 n 에 대해서 n ! 이다.

입력이 10 개라면 3,628,800 개이다. 20개라면 ? 2,432,902,008,176,640,000 ... 구하기 싫어질 듯. (factorial 에 대해서는 다음 참고 : http://en.wikipedia.org/wiki/Factorial)

이렇게 하면 풀 수 없다는 것만 알고 넘어가자.

 

2.2. dynamic programming 으로 풀기

기본적으로 이 방법도 모든 경로에 대해 거리 합을 구한다.

단, 차이는 앞선 방법에서 발생하는 중복을 모두 제거하여 계산 횟수를 줄이는 방법을 사용한다.

예를 들면,

1 > 2 > 3 > 4 > 5

1 > 2 > 3 > 5 > 4

이와 같은 경로로 이동한 경우의 값을 구할 때, 1 > 2 > 3 까지는 공통이므로 중복 계산할 필요가 없다.

이런 방식으로 문제를 풀면, 입력 도시 수가 10개이면 계산해야 하는 경로의 경우의 수는 2048 (2^11) 개로 아까보다 현저히 줄어들었다.

도시 수가 20개 이면, 약 200 만 번만 계산하면 된다. ㅎㅎ

 

문제 풀이

이 문제는 다음과 같이 나누어 풀 수 있다.

도시 {1, 2, 3, 4, 5} 가 있다고 했을 때, 최소 경로를 min {1, 2, 3, 4, 5} 이라고 정의하자.

그렇다면 최소 값은,

min {1, 2, 3, 4, 5} = min (

1 > min {2, 3, 4, 5}, // 1 에서 출발하여 {2, 3, 4, 5} 를 순회하는 최소값

2 > min {1, 3, 4, 5}, // 마찬가지로 2 에서 출발하여 나머지를 순회하는 최소값

3 > min {1, 2, 4, 5},

4 > min {1, 2, 3, 5},

5 > min {1, 2, 3, 4}

)

 

1 > min {2, 3, 4, 5} 은 다음과 같은 의미를 가진다.

1 > min {2, 3, 4, 5} = min (

distance(1, 2) + min (2 > {3, 4, 5}), // "1 에서 2까지 거리" + 2 에서 출발하여 나머지 도시를 순회하는 최소값

distance(1, 3) + min (2 > {2, 4, 5}),

distance(1, 4) + min (2 > {2, 3, 5}),

distance(1, 5) + min (2 > {2, 3, 4})

)

 

이렇게 반복해서 전개하면 마지막에는 4 > {5} 와 같이 가장 단순한 형태로 귀결된다. 이 값은 distance(4 ,5) 이다.

 

자료구조

위 내용을 코드로 변경하려면, 순회하고자 하는 도시들의 집합을 간단히 표현할 수 있어야 한다.

집합을 표현할 때, 가장 간단한 방법은 bit flag 를 이용하는 방법이다.

예를 들어 2진수 11111 은 집합 {1, 2, 3, 4, 5} 를 나타낸다.

 

그렇다면, 1 에서 출발하여 {2, 3, 4, 5} 를 순회하는 최소값은 다음과 같이 코드로 표현할 수 있다.

tsp (1, 0x1E) // 16 진수 1E 는 2진수로 11110 이 된다.

따라서 tsp 함수의 원형은 다음과 같이 쓰면 된다.

int tsp (int from, int toFlag);

 

함수 tsp 는 재귀적으로 호출된다.

1 2 3 4 5 6 7 8 9 10

int tsp (int from, int toFlag) {     int m = INT_MAX;     for (int i = 0; i < _n /* the nuber of cities */; i++) {         if (!(toFlag & (1 << i))) continue;           int v = _distance[from][i] + tsp(i, (toFlag & ~(1<<i)));         m = min(m, v);     }     return m; }

비트 플래그 연산에 익숙하지 않다면 다음을 참고 : http://forum.codecall.net/topic/56591-bit-fields-flags-tutorial-with-example/

4 번 라인은 toFlag 에 포함되지 않은 index 를 걸러낸다.

그래서 실제 계산 부분은 6 라인이다.

7 라인에서는 6 라인에서 계산된 값 중 가장 최소값을 저장한다.

 

이 코드에서는 종료 조건과 memoization 코드가 없다. 완성된 코드는 다음과 같다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

int tsp (int from, int toFlag) {     int &memo = _memory[from][toFlag]; // _memory[][] 가 0 로 초기화 되어 있어야 함.     if (memo != 0) {         return memo;     }     if (bitCount(toFlag) == 1) {         int to = getIndex(toFlag);         return _distance[from][to];     }       memo = INT_MAX;     for (int i = 0; i < _n /* the nuber of cities */; i++) {         if (!(toFlag & (1 << i))) continue;           int v = _distance[from][i] + tsp(i, (toFlag & ~(1<<i)));         memo = min(memo, v);     }     return memo; }

종료 조건은 toFlag 에 단 하나의 도시만 남는 경우이다. 

이 경우는 바로 distance(from, to) 를 반환하면 된다. to 는 알아서 구현해서 계산 하시기를 ... 

gcc 컴파일러를 사용한다면 bitCount() 를 구현할 필요 없이 __builtin_popcount() 를 사용할 수 있다.

역시 마찬가지로 getIndex() 대신 __builtin_ctz() 를 사용할 수 있다.

이에 대한 자세한 내용은 다음 링크를 참고 : http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

 

전체 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54

#include <iostream> #include <cstring> using namespace std;     int _n; // num const int MAX_SIZE = 15; // 입력 크기에 따라 충분히 (32 이상 될 수 없음) int _distance [MAX_SIZE][MAX_SIZE]; // _distance int _memory [MAX_SIZE][1<<MAX_SIZE]; // for memoization       void getInput() {     cin >> _n;     for (int i = 0; i < _n; i++) {         for (int j = 0; j < _n; j++) {             cin >> _distance[i][j];         }     }     memset(_memory, 0, sizeof(int) * MAX_SIZE * (1<<MAX_SIZE)); }      int tsp (int from, int toFlag) {     int &memo = _memory[from][toFlag]; // _memory[][] 가 0 로 초기화 되어 있어야 함.     if (memo != 0) {         return memo;     }     if (__builtin_popcount(toFlag) == 1) {         int to = __builtin_ctz(toFlag);         return _distance[from][to];     }       memo = INT_MAX; // 그냥 충분히 큰 수를 사용해도 된다     for (int i = 0; i < _n /* the nuber of cities */; i++) {         if (!(toFlag & (1 << i))) continue;           int v = _distance[from][i] + tsp(i, (toFlag & ~(1<<i)));         memo = min(memo, v);     }     return memo; }   int main() {     getInput();     int m = INT_MAX;     int allFlag = (1<<_n) - 1;     for (int i = 0; i < _n; i++) {         int v = tsp(i, allFlag & ~(1<<i));         m = min(m, v);     }     cout << m << endl;     return 0; }

# 입력  15 0 29 82 46 68 52 72 42 51 55 29 74 23 72 46 29  0 55 46 42 43 43 23 23 31 41 51 11 52 21 82 55  0 68 46 55 23 43 41 29 79 21 64 31 51 46 46 68  0 82 15 72 31 62 42 21 51 51 43 64 68 42 46 82  0 74 23 52 21 46 82 58 46 65 23 52 43 55 15 74  0 61 23 55 31 33 37 51 29 59 72 43 23 72 23 61  0 42 23 31 77 37 51 46 33 42 23 43 31 52 23 42  0 33 15 37 33 33 31 37 51 23 41 62 21 55 23 33  0 29 62 46 29 51 11 55 31 29 42 46 31 31 15 29  0 51 21 41 23 37 29 41 79 21 82 33 77 37 62 51  0 65 42 59 61 74 51 21 51 58 37 37 33 46 21 65  0 61 11 55 23 11 64 51 46 51 51 33 29 41 42 61  0 62 23 72 52 31 43 65 29 46 31 51 23 59 11 62  0 59 46 21 51 64 23 59 33 37 11 37 61 55 23 59  0     # 출력 262

 

3. 약간의 개선

나중에 쓰겠습니다. ㅎㅎ

sum of subset problem

이것은 대략 숫자의 set 에서 요놈의 부분집합의 합으로 0 을 만들 수 있는 지 여부를 체크하는 문제이다.

예를 들면, 주어진 집합 { −7, −3, −2, 5, 8} 에서 부분집합 { −3, −2, 5} 합은 0 이 될 수 있다.

대략 이 문제를 약간 변경하면, 어떤 정수 집합의 부분집합의 합이 N 이 될 수 있는 지를 확인하는 문제로 변경할 수 있다.

algospot 의 문제 WEIRD[2] 가 그 중 하나인데, 어떤 정수 n 의 부분집합의 합이 n 이 될 수 있는 지를 검사하는 문제이다.

이 문제는 NP-complete 이다.

1. 그냥 찾기

모든 부분집합에 대해서 합을 구하여 N 과 같은 지 검사하는 방법. 

이것은 대략 O(2^NN) 복잡도를 갖는다.

시도해서는 안 되는 알고리즘이다 ㅡㅡ

2. branch&bound 로 풀기 [3]

모든 부분집합을 tree 를 순회하지만 promising 하지 않으면 가지치기를 통해 더이상 검사하지 않는 방법이다.

대략 입력 w[] 에 대해 첫번째 원소부터 추가 또는 추가하지 않는 경우를 재귀(recursive)적으로 함수를 호출한다.

이렇게 하면 promising() 계산에 시간이 다소 오래 걸린다.

90 개짜리 입력을 넣으면 수분 이상 걸린다.

거의 비슷하지만 방법을 바꾸어서, 계산을 단순화 하면 훨씬 빨라진다.

원리는 i 번째 원소가 속할 지, 속할 지 않을 지에 따라 

속할 때는 sum 에서 값을 제외해 나가는 것이다. 이렇게 하면 promising() 에 해당하는 코드가 짧아진다.

예를 들어, 입력이 {1,2,3,4,6} 이고, N = 12 일때, 

정답 sub set 에 6 이 포함된다면, 원소 6을 제외한 {1,2,3,4}, N=6 으로 문제가 간소화 된다.

만약 6이 포함 안 된다면 {1,2,3,4}, N=12 가 된다.

남아 있는 원소의 합과 변경된 N 값을 바로 계산하여 호출하면 된다.

이렇게 하면 90개짜리 입력을 넣으면 약 150 ms 내에 결과가 나온다.

references:

[1] http://en.wikipedia.org/wiki/Subset_sum_problem

[2] http://algospot.com/judge/problem/read/WEIRD

[3] http://blog.naver.com/PostView.nhn?blogId=takku04&logNo=150017480080&redirect=Dlog&widgetTypeCall=true