Ad hoc algorithms

 

Course - Programming - Professional - Ad Hoc Algorithms

 

SW Expert Academy

 

 

 

Anagram 찾기

 

- n개의 단어가 주어져 있을 때 anagram 쌍 개수를 구하라.

 

- 1. counting sort를 이용하여 각 단어의 알파벳들을 정렬.

 

- 2. radix sort를 이용하여 단어들을 정렬.

 

- 3. 순회하며 같은 단어들의 갯수를 세어 쌍의 개수를 더해줌.

 

 

 

정렬된 두 배열에서 합 찾기

 

- 크기 n인 정렬된 배열 A, B와 목표 값 X이 주어졌을 때, 두 배열에서 각각 하나의 원소를 골라 X를 만들 수 있는가.

 

- 통용되는 명칭인지는 모르겠으나 slider 알고리즘 이용.

 

- A는 왼쪽에서, B는 오른쪽에서부터 차례대로 확인하며 이동.

 

 

 

정렬된 두 배열을 merge했을 때 K번째 값 찾기

 

- 그냥 정렬해서 K번째 값을 찾는다고 하면 O(n)

 

- \( i_0 + j_0 = K - 1 \) 이며 \( A[i_0 + 1] \) 또는 \( B[j_0 + 1] \) 이 K번째 수를 만족하는 \( i_0 \), \( j_0 \)가 있다고 가정하자.

 

- 그렇다면 \( i + j = K - 1 \) 을 만족하는 모든 \( i \), \( j \) 쌍에 대해 \( i < i_0 \) 라면 \( A[i] < B[j] \), \( j < j_0 \)이라면 \( A[i] > B[j] \) 를 만족한다.

 

- 따라서 binary search로 \( i_0 \), \( j_0 \) 를 찾은 뒤 \( A[i_0 + 1] \)와 \( B[j_0 + 1] \)을 비교한다.

(둘 모두 있다면)

 

- 이런식으로 최적화하는 것이 대단하면서도 좀 변태 같다.

 

- 만약 문제 형태로 만든다면 정렬된 두 배열을 parameter로 주고 K번째 값을 return 하는 함수를 O(log n) 시간제한을 주고 구현하라고 만들 수는 있을 것 같다.

 

 

 

(감추어진) 자연수들을 정렬했을 때 가장 큰 gap 찾기

 

- 1부터 M까지의 범위에서 N개의 자연수가 입력으로 감추어진다. 이 자연수들을 정렬했을 때 가장 큰 gap(즉, 인접한 두 자연수의 차이)를 찾아라. M은 N에 비해 매우 크다.

 

- query(X, Y)를 호출하면 X와 Y 범위 안에 있는 자연수들의 최솟값과 최댓값을 알려준다.

 

- query의 호출 횟수를 줄이는 것이 좋다.

 

- query(1, M)으로 모든 자연수들의 최솟값 \( T_1 \)과 최댓값 \( T_N \)을 찾는다.

 

- \( T_N - T_1 \) 구간을 \( n - 1 \)개로 나누어 query에 집어넣고 답을 구한다.

 

- 결국 \( T_1 \)과 \( T_N \) 사이에는 \( n - 2 \)개의 자연수들이 있다.

 

- 따라서 구간을 \( n - 1 \) 로 나누었기 때문에 무조건 한 구간은 비어있다.

 

- 그렇기 때문에 구간 안에서 가장 큰 gap이 나올 수 없다.

 

 

 

달리기

 

- 달리기 시합이 진행 중이다. 각 사람들의 평소 실력과 현재 등수를 알고 있을 때 어떤 사람보다 등수가 높은 사람들 중 평소 실력이 작은 사람 명수의 합을 구하라.

 

- 현재 \( i \)등을 하고 있는 사람의 평소 실력은 \( A[i] \)이다.

 

- 모든 비교를 한다면 \( O(n^2) \)는 명백하다.

 

- merge sort를 하며 inversion counting을 하면 \( O(n log n) \)으로 해결 가능

 

- 실력의 범위가 한정적이라면 segment tree를 이용할 수도 있다. 역시 \( O(n log n) \)

 

 

 

연결 리스트에서 cycle 찾기

 

- 연결 리스트를 수정하지 않고 구하는 방법이 있을까

 

- pointer 두 개를 만들어 움직이게 한다. 한 pointer는 1칸씩, 다른 pointer은 2칸씩 움직인다.

 

- 만약 cycle이 있다면 어느 지점에서 두 pointer는 반드시 만나게 된다.

 

- cycle이 없다면 2칸 움직이는 pointer가 이동을 중지하게 된다.

 

 

 

혼자인 값 찾기

 

- 2n + 1개의 값이 배열에 저장되어 있는데, 단 하나의 값을 제외한 N개의 값이 두 번씩 나타난다. 한 번만 나타나는 값은 무엇인가?

 

- \( O(n^2) \) 만큼 비교한다.

 

- sorting을 하여 찾아낸다. ( \( O(n log n) \) )

 

- 모든 수에 대해 bitwise xor을 한다. (xor의 특성을 이용)

 

- \( k \) \( xor \) \( k = 0 \)

 

- 교환 법칙이 성립하기 때문에 혼자인 값만 살아남게 된다.

 

 

 

Bit Manipulation: 1인 비트들 세기

 

- 주어진 32비트 unsigned int에 1인 비트는 몇 개인가?

 

- 그냥 shift 하면서 비트 세기

 

- \( x \)와 \( x - 1 \)을 bitwise and 수행 -> 제일 오른쪽 1인 비트가 사라짐 -> 0이 될 때까지 반복하며 count

 

- 위키피디아에서 가져온 64비트 1인 비트를 세는 세 가지 방법. 아래로 갈수록 최적화됨.

 

- 대 단 하 다;; (변태 같다)

 

- 분할 정복, 병렬 처리의 콤비네이션

 

//types and constants used in the functions below
//uint64_t is an unsigned 64-bit integer variable type (defined in C99 version of C language)
const uint64_t m1  = 0x5555555555555555; //binary: 0101...
const uint64_t m2  = 0x3333333333333333; //binary: 00110011..
const uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64_t m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64_t m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64_t m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones
const uint64_t h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//This algorithm uses 24 arithmetic operations (shift, add, and).
int popcount64a(uint64_t x)
{
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits 
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits 
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits 
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits 
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits 
    x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits 
    return x;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with slow multiplication.
//This algorithm uses 17 arithmetic operations.
int popcount64b(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    x += x >>  8;  //put count of each 16 bits into their lowest 8 bits
    x += x >> 16;  //put count of each 32 bits into their lowest 8 bits
    x += x >> 32;  //put count of each 64 bits into their lowest 8 bits
    return x & 0x7f;
}

//This uses fewer arithmetic operations than any other known  
//implementation on machines with fast multiplication.
//This algorithm uses 12 arithmetic operations, one of which is a multiply.
int popcount64c(uint64_t x)
{
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    return (x * h01) >> 56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ... 
}

 

 

 

최대 subarray 찾기

 

- 주어진 배열 A[1...N]에서 그 합이 가장 큰 연속된 부분 A[i...j]를 찾아라. 저장된 값은 양/음수 모두 가능.

 

- \( O(n) \)으로 풀 수 있다.

 

- B[i]: i로 끝나는 연속된 subarray의 가장 큰 합

 

- B[i] = B[i - 1] + A[i] ( \( B[i - 1] + A[i] > 0 \) ), 0 ( \( B[i - 1] + A[i] <= 0 \) )

 

- 합이 음수가 되는 부분을 굳이 합칠 필요가 없다.

 

 

 

Game

 

- N개의 노드를 가진 그래프, 어떤 쌍의 노드들이 에지로 연결되어 있는지 정해지지 않았다.

 

- 노드 쌍이 질문으로 들어오면 둘을 잇는 엣지가 있는지 없는지 알려주어야 한다.

 

- 질문은 모든 쌍에 대해 들어오며, 순서는 정해져 있지 않다.

 

- 질문에 대한 답은, 질문하는 쪽이 그래프가 전체적으로 연결되어 있는지 아닌지 끝까지 알 수 없도록 해야 한다. 마지막 질문 후에 알 수 있어야 한다.

 

- Yes라고 대답하면 안 되는 경우는 아직 질문되지 않은 두 component간의 엣지가 있는 경우 두 component간 연결성을 확정지어버리는 경우이다.

 

- No라고 대답하면 안되는 경우는 No라 대답하였을 때 완전히 분리되는 그룹이 발생하는 경우이다.

 

- 아래의 코드가 답이 될 수 있다.

 

int c[N];

int query(int a, int b) {
	return ++c[a>b?a:b]==(a>b?a:b);
}

 

- 노드 i에 대해, i보다 작은 노드와 i에 대한 질문이 들어온 횟수를 세어 i번째에 연결한다.

 

- tree 구조가 된다.