대부분 기본적으로 포인터가 무엇인지

포인터를 어떻게 사용해야 하는지 알고 있습니다.

 

int a = 3;

int* p = &a;

int** pp = &p;

 

다음과 같이 어떤 변수의 주소를 나타낸다는 것.

여기까지는 쉽게 알 수 있는 내용입니다.

 

그런데 잘 알고 있다고 생각한 포인터를

사용할 때 가끔 헷갈리는 경우가 있습니다.

 

뭐 문법 이것저것 Visual Studio에서 써보면 알 수 있겠지만

이렇게 시도해보는 것 자체가 시간을 잡아먹는 요인이 됩니다.

 

따라서 이번 포스팅에서는 헷갈릴 수 있을만한

포인터 문법에 대하여 알아보도록 하겠습니다.

 

 

1. 다차원 배열의 등장

 

int arr[4][5];

 

다음과 같은 배열을 선언했을 때 포인터로 어떻게 가리킬까요?

생소하실 수도 있겠지만 문법은 다음과 같습니다.

 

int (*ptr)[5];

 

아! 참고로 이것과 다릅니다 -> int* arr[4];

 

1) int (*ptr)[5] : 열이 5개인 int형 2차원 배열을 가리키는 포인터 변수입니다.

2) int* arr[4] : int형 포인터로 이루어진 배열

 

따라서 위 내용을 헷갈리시면 안 됩니다.

2차원 배열의 주소를 함수로 전달할 때는?

 

void func(int arr[5]);

void func(int (*arr)[5]);

 

좀 더 응용해서 3차원 배열이라면 어떻게 표현할까요?

int arr[3][4][5];

 

이 경우는 다음과 같이 표현합니다.

int (*ptr)[4][5];

 

다음 4차원, 5차원 등은 위 내용을 응용하실 수 있겠죠?

Parallel Binary Search




연습문제로는 8217) 유성 이 있다.



안녕하세요? ryul입니다.


오늘은 이항계수를 빠르게 구하는 알고리즘에 대해서 공부해보겠습니다.


알고나면 매우 쉽습니다.


먼저 이항계수란?


고등학교 때 배웠던 조합이랑 같은 거라고 생각하시면 됩니다. 

N개의 공 에서 K개의 공을 뽑는 경우의수 를 의미하죠~


기호로는 어떻게 표시할까요?


nCk 

이렇게~


자! 먼저 가장 나이브한 방법으로 nCk 를 구한다면?




Phase 1 나이브



nCk = n! / (k!(n-k)!) 을 직접 계산으로 구하게 됩니다.


이 때 n이 커지게되면 nCk의 값은 분명 기하급수적으로 커지게 되므로 n이 클 경우 분명 문제에서 값을 p로 나눈 나머지를 구하라는 요구를 할 것입니다.




따라서 nCk mod p 의 값을 구해야 하는 것인데, 

단순히 (분모 mod p) / (분자 mod p) 의 값은 우리가 구하고자 하는 값이 아닙니다.



왜냐하면 우리는 나누어 떨어지는 경우 분자와 분모를 약분해야 하는데 단순히 n! mod p 를 구한 후에 하는 계산은 의미가 없습니다.




따라서 일일히 나누어 떨어지는 것부터 계산하게 될 경우 시간이 많이 걸리게 됩니다.




Phase 2 DP




n+1Ck+1 = nCk + nCk+1 이라는 식이 성립하는 것을 알 수 있습니다.

(직접 계산해보면 납득하실 거에요!)




따라서 메모이제이션을 이용하여 dp[n][k] 의 배열을 잡고 동적으로 계산해나간다면 O(n^2)의 시간복잡도로 이항계수를 구할 수 있습니다!




하지만 n이 너무커서 dp로도 되지 않는다면??




phase 3 페르마의 소정리




페르마의 소정리를 이용하겠습니다.


페르마는 말했습니다.

" p를 소수라고할 때 a^(p-1) = 1 (mod p) 이다."




따라서 a * a^(p-2) = 1 (mod p) 라는 것을 알 수 있기 떄문에 우리는 a의 역원이 a^(p-2)라는 것을 알 수 있게됩니다!




즉, 1/a mod p == a^(p-2) 가 되는 것이죠.




따라서 우리가 구하고자 했던 nCk = n! /(k! * (n-k)!) 에서 1 / (k! * (n-k)!) mod p 은 (k! * (n-k)!)^(p-2) mod p 라는 것을 알 수 있죠!!




자! 그렇다면 nCk mod p = ( n! mod p) * ( (k! * (n-k)!)^(p-2) mod p )  입니다.





식이 너무 더러우신가요? 자세히보면 충분히 이해할 수 있습니다.




Phase 4 전처리 후 O(1) 에 사용




n * inverse(n!) = inverse((n-1)!) 라는 식이 성립합니다. 

( 왜 성립하는 지는 식을 계산해보시면 알 수 있습니다!)



따라서 n! 의 inverse 만 분할정복을 통하여 O(log p) 의 시간에 한 번 구해준다면?

메모이제이션을 통하여 n!의 inverse 를 O(n) 의 구할 수 있습니다!





따라서 O(n + logp) 시간 복잡도로 이항 계수 전처리가 수행됩니다.

그 후에는 O(1)의 시간복잡도로 모든 nCk 를 구할 수 있게됩니다.





Phase4 까지 완료한 코드는 다음과 같습니다.


#include <cstdio>
#include <algorithm>
#define P 1000000007LL
typedef long long ll;
using namespace std;
ll fac[4000001], n, k, inv[4000001];//inv[x]의 정의는 x의inverse가 아닌 x!의 inverse
ll power(ll x, ll y) { //분할 정복을 이용하여 x^y 구하기
ll ret = 1;
while (y > 0) {
if (y % 2) {
ret *= x;
ret %= P;
}
x *= x;
x %= P;
y /= 2;
}
return ret;
}
int main() {
fac[1] = 1;
for (int i = 1; i <= 4000000; i++)
fac[i] = (fac[i - 1] * i) % P; //factorial 전처리
inv[4000000] = power(fac[4000000], P - 2); //페르마의 소정리를 이용하여 fac(400만)의 inverse를 구함(이때 분할 정복을 이용하여 logP의 시간에 처리)
for (int i = 4000000 - 1; i >= 0; i--)
inv[i] = (inv[i + 1] * (i + 1)) % P; //inverse(fac(i))=inverse(fac(i+1))*(i+1)이라는 수식을 이용하여 전처리
//총 O(N+logP)시간에 전처리를 끝냄
//전처리가 끝났기 때문에 어떤 쿼리가 들어와도 상수시간에 이항 계수를 계산 가능
scanf("%lld%lld", &n, &k);
if (n == k || !k) {
puts("1");
return 0;
}
ll r = (fac[n] * inv[n - k]) % P;
r = (r*inv[k]) % P;
printf("%lld\n", r);
return 0;
}
출처:[ACM-ICPC 상 탈 사람]


이상 이항계수를 빨리 구하는 법에 대해서 알아봤습니다.


이제 경우의수 식을 잘 세우는 테크닉만 키우면 이 코드를 잘 이용해서 문제를 해결할 수 있습니다!


이상~




'알고리즘' 카테고리의 다른 글

Parallel Binary Search  (0) 2018.08.15
boj2319)사수아탕  (0) 2018.08.15
이항계수를 빠르게 구하는 알고리즘  (3) 2018.07.05
Usaco Gold) Fair Photography  (0) 2018.06.03
[기하] 다각형의 내부 외부 판별  (0) 2018.05.13
BOJ 6171) 땅따먹기  (0) 2018.05.13
  1. 자손9319 2018.07.05 01:57 신고

    아니 이 분 허락도 없이 불펌하시네

Problem


1부터 10억까지 좌표중에, N개의 값을 넣는다. 해당 값은 1~8사이 이다.

이 중 두가지 조건을 만족하는 가장 긴 길이의 범위는?

- 서로다른 K개의 이상의 값이 존재해야한다.

- 각 값들의 갯수는 같아야 한다.



논리 과정


T(b,p) 를 p보다 왼쪽에있는 b의 갯수라고 하자.

- T(b,R) = T(b,L) + c 만약 이 사이에 b 가 존재한다면.

- T(b,R) = T(b,L) 이다 만약 b가 존재하지 않는다면.



따라서 집합 A 와 기준점 p 가 주어지면 우리는 signature S(A,p) 를 만들 수 있다.

- T(b,p) - T(b0,p)  이 때  b0 는 A 안에 첫번쨰 원소이다.

- T(b,p) 는 존재하지 않는것에 대하여.


만약 S(A,L) = S(A,R) 이고 L<R이라면 L-R 은 유효하다.

S는 각 원소들의 차이값이다.


모든 S(A,L) 값을 전처리 한 후 A,R을 고정시키고, 그 와 매칭하는 가장 작은 L을 구해주면 된다.

이 과정에서 MAP 을 이용한다.


K개의 이상의 원소를 포함하는 조건을 만족시키기 위해서 인덱스를 추가한것.


따라서 차이값을 이용해서 map(vector, int) 로 문제를 해결한다. 벡터해쉬


'알고리즘' 카테고리의 다른 글

boj2319)사수아탕  (0) 2018.08.15
이항계수를 빠르게 구하는 알고리즘  (3) 2018.07.05
Usaco Gold) Fair Photography  (0) 2018.06.03
[기하] 다각형의 내부 외부 판별  (0) 2018.05.13
BOJ 6171) 땅따먹기  (0) 2018.05.13
DP최적화 - Convex Hull Trick  (0) 2018.05.06

다각형의 내부 외부 판별이란?



그림1 에는 다각형과 두개의 점 A,B 가 있습니다. 이 그림에서 눈으로 확인했을 때 각 점이 다각형 내부에 있는지, 외부에 있는 지 판별하는 것은 쉽습니다.

이렇게 주어진 점이 다각형 내부에 있는 지 외부에 있는 지 판별하는 것을 다각형의 내부 외부 판이라고 합니다.





아이디어


다각형의 내부에 위치하는 점의 특성


컴퓨터가 특정 점이 다각형 내부에 있는지 어떻게 판별할까요? 

오른쪽으로 반 직선을 그었을 때 다각형과 만나는 점의 개수가 홀수 개라면 내부에 있는 점입니다.



그림2를 보고 이 특징이 맞는지 확인해봅시다. 다각형 외부에 있는점  A는 다각형과의 교점 개수가 2개 즉 짝수개 입니다.

다각형 내부에 있는점 B는 오른쪽으로 그은 반직선과 다각형과의 교점 개수가 3개 즉 홀수 개 입니다. 


이 원칙은 눈으로 도저히 확인할 수 없을 만큼 복잡한 꼭지점이 백만 개 다각형에서도 내부 외부를 판별하는데 적용할 수 있는 강력한 규칙입니다.





구현


어떻게 반 직선과 다각형의 교점 개수를 구하지?


다각형의 내부 외부 판별 규칙은 간단하지만 반직선과 다각형의 교점의 개수를 구하는 것은 쉽지않아보입니다.


반직선과 다각형의 선분과의 교차점을 구한 후에 이 교차점이 선분 위에 있는지 조사하는 방법을 사용해야 할까요?

다행히 반직선은 x축에 항상 평행한 수평선이기 떄문에 비교적 간단하게 다각형의 선분과의 교차점을 구할 수 있습니다.


다각형의 모든 선분들에 대해 반직선과 교점이 존재하는지를 검사합니다. 

반직선과 선분 사이에 교점이 존재하기 위한 조건은 2가지 입니다.


- 점  B 의 y좌표가 두 선분 꼭지점의 y좌표 사이에 있다.

- 점  B를 지나는 수평선과 선분 사이의 교점의 x좌표가 점B의 x좌표보다 크다.




조건1을 만족하는 점B를 지나는 수평 직선과 선분 사이에 반드시 교점이 존재한다.

이 때 오른쪽 반직선과의 교점만 세야하므로 조건2를 추가로 만족해야 반직선과 선분 사이의 교점 존재여부를 올바르게 판별할 수 있습니다.





이제 그림 3과 같은 다각형이 주어졌을 때 점 B의 반직선과 다각형의 교점의 개수를 찾는 과정을 진행해봅시다.

다각형의 10개의 꼭지점은 p[0], p[1] ... p[9] 으로 주어졌습니다.





먼저 그림4처럼 꼭지점 p[0], p[1]을 연결하는 선분과 반직선과의 교차여부를 생각합시다.

 점 B는 선분 (p[0],p[1] ) 의 y좌표 사이에 있고 교점의 x좌표가 점 B보다 크기 떄문에 교차한다고 판단할 수 있습니다.






그림 5와같은 경우에는 조건2를 만족하지 않기 때문에, 교차하지 않는다고 판단해야합니다.



그림 6처럼 꼭지점 p[3],[4] 를 연결하는 선분과의 교차여부를 생각해봅시다. 

선분 (p[3],p[4])의 y좌표 사이에 있지 않기 때문에 교차하지 않는다고 판단합니다.





소스코드


1
2
3
4
5
6
7
/* 점을 구조체로 정의 함 */
strcut vector2{
int x, y;
}
/* STL vector를 이용해서 다각형 자료형을 정의 함 */
typedef vector<vector2> polygon;
 


cs

이제 점 B가 다각형 p 내부에 있는지를 반환하는 함수 isinside 를 정의합니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool isInside(vector2 B, const polygon& p){
//crosses는 점q와 오른쪽 반직선과 다각형과의 교점의 개수
int crosses = 0;
for(int i = 0 ; i < p.size() ; i++){
int j = (i+1)%p.size();
//점 B가 선분 (p[i], p[j])의 y좌표 사이에 있음
if((p[i].y > B.y) != (p[j].y > B.y) ){
//atX는 점 B를 지나는 수평선과 선분 (p[i], p[j])의 교점
double atX = (p[j].x- p[i].x)*(B.y-p[i].y)/(p[j].y-p[i].y)+p[i].x;
//atX가 오른쪽 반직선과의 교점이 맞으면 교점의 개수를 증가시킨다.
if(B.x < atX)
crosses++;
}
}
return crosses % 2 > 0;
}
cs


어떤 땅의 i 의 너비 Wi 와 Hi 가 주어진다.

이 때 가격은 Wi * Hi 이다.


- 한번에 여러개  된다면, (해당 땅 중 Wi의 최댓값 ) * (해당 땅 중 Hi의 최댓값)  으로 가격을 매긴다.


따라서 땅을 최소 비용으로 묶어서 살 경우 최소 비용은 ?


일단 무조건 wi를 기준으로 정렬을 시킨다.

이 때 만약 Wi 와 Hi 가 Wj , Hj보다 더 크다면 무조건 묶는게 이득이다. 

따라서 O(n) 시간으로 탐색하면서 더 큰 애들을 지워나간다.


그렇게 되면 현재 Wi 는 오름차순, Hi 는 내림차순으로 정렬된다.

 

그러고 DP를 생각해보자!


DP[i] = min (DP[j-1] + b[j] * a[i]) 의 식이 성립한다. ( b 는 내림차순)


그러므로 Convex Hull Trick 을 사용하면 된다.


이 때 순차적으로 DP[i] 값을 모두 구해나가야 한다.

따라서 O(n* logn) 의 시간복잡도를 지닌다.



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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
 
using namespace std;
typedef long long ll;
 
struct convex{
    vector<ll> M;//기울기을 의미한다.
    vector<ll> B;//y절편의 값들
    //결국 조심해야될것은 이게 getval이나 bad가 long long 범위를 넘어서는지에 대한 거다
    bool bad(int l1,int l2,int l3){
        return (B[l3]-B[l1]*(M[l1]-M[l2]) < (B[l2]-B[l1])*(M[l1]-M[l3]));
    }
 
    double Cross(int a, int b) {
        return (double)(B[b] - B[a]) / (M[a] - M[b]);
    }
 
    void add(ll m,ll b){
        if(M.size()>0){
            if(M[M.size()-1]== m){
                B[M.size()-1]= min(B[M.size()-1],b);
            }
            else{
                M.push_back(m);
                B.push_back(b);
            }
        }
        else{
            M.push_back(m);
            B.push_back(b);
        }
 
        while(M.size()>=3 && Cross(M.size()-3,M.size()-2)> Cross(M.size()-2,M.size()-1) )
        {
            M.erase(M.end()-2);
            B.erase(B.end()-2);
        }
    }
 
    ll getval(ll x,int id){
        return B[id] + x*M[id];
    }
    ll query(ll x){
        int l = 0,r = M.size()-1,mid;
 
        while(l<r){
            mid = (l+r)/2;
            if(Cross(mid,mid+1)>=x)
                r = mid;
            else
                l = mid+1;
        }
        return getval(x,l);
    }
};
 
 
 
 
ll n;
pair<ll,ll> arr[50500];
 
 
int main(){
 
freopen("input.txt","r",stdin);
 
scanf("%lld",&n);
 
for(int i = 0 ; i < n ; i++){
    scanf("%lld %lld",&arr[i].first,&arr[i].second);
}
 
convex cv;
 
sort(arr,arr+n);
reverse(arr,arr+n);
 
ll now = -1;
ll prev = 0;
 
for(int i =0 ; i < n ; i++){
    if(now >= arr[i].second)    
        continue;
    now = arr[i].second;
    cv.add(arr[i].first,prev);
    prev = cv.query(arr[i].second);
}
 
 
printf("%lld",prev);
 
 
}
cs


'알고리즘' 카테고리의 다른 글

Usaco Gold) Fair Photography  (0) 2018.06.03
[기하] 다각형의 내부 외부 판별  (0) 2018.05.13
BOJ 6171) 땅따먹기  (0) 2018.05.13
DP최적화 - Convex Hull Trick  (0) 2018.05.06
Sqrt Decompositon(평방분할) & Mo's Algorithm  (0) 2018.04.05
문자열 해싱  (0) 2018.03.31

* 필요한 상황 

dp[i] = min( dp[j] + b[j]*a[i] ) 를 찾는건데 여기서 b[i] > b[i+1] ( b는 내림차순) 을 반드시 만족한다. (j < i 인 정수)


만약 오름차순이라면 굳이 계산할 필요가 없고, 내림차순이라면 binary search 로 찾을 수 있다.



이런 식이 나온다면 바로 CHT 를 쓸 수 있다.


여기서 문제가 되는 것은 바로 조건에 맞지 않는 직선들을 제거해주는 것이다.



* 업데이트

현재 line1이 새로 추가될 것이라고 생각하자.

그렇다면 line3 , line2 를 현재 저장된 라인들 중 가장 뒤에 있는 라인이라고 하자.


intersect - x(line3,line1) = x1

intersect - x(line3,line2) = x2 라고 해보자.


만약 x1 < x2 라고 한다면 이 직선은 이제 필요없다.


왜냐하면 이미 line3 다음에 line2가 그 다음으로 작아지기 시작하는건데

line3 다음에 이미 line1 이 더 작아졌으므로 애초에 line2는 들어올 필요가 없다.



그리고 라인 업데이트 같은 경우는 사실 이진탐색을 통해서 어디를 없애야하는 지 바로 알 수 있는 방법도 있다.

어차피 식을 보면 binary search를 통해서 충분히 찾을 수 있을 것으로 해석된다.

그런데 보통의 경우는 그렇게 사용되지 않고 O(1) amortized 시간복잡도를 갖게 된다.


* 쿼리 구하기


이제 직선들의 모임에서 x좌표가 어떤 직선에서 가장 최소값이 되는 지를 알아야 한다.


mid, mid+1 의 교점보다 x좌표가 더 작다면 mid 이하의 직선에서 최소값이 등장할 것이고

아니라면 mid+1 이상의 직선에서 최소값이 등장할 것이다.


line 별로 자기만의 최소값 구간이 있다고 보면 조금 편하다.

그렇다면 교점보다 x좌표가 더 작다면 최소값은 mid 이하의 점에서 나올것이 분명하다.


왜냐하면 이 친구의 mid+1 최소값 범위에는 x가 들어오지 않기 때문이다.


굉장히 쉽게 문제를 풀 수 있다.



* 예시문제 


https://www.acmicpc.net/problem/5498


https://www.acmicpc.net/problem/3319


http://www.spoj.com/problems/NKLEAVES/


http://codeforces.com/contest/311/problem/B


https://www.acmicpc.net/problem/4008


https://www.acmicpc.net/problem/2192


http://codeforces.com/contest/311/problem/B


http://codeforces.com/problemset/problem/377/E



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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
어떤 경우에서도 항상 통하는 방법.
#define ll long long
 
struct convex{
    vector<ll> M;//기울기을 의미한다.
    vector<ll> B;//y절편의 값들
    //결국 조심해야될것은 이게 getval이나 bad가 long long 범위를 넘어서는지에 대한 거다
    bool bad(int l1,int l2,int l3){
        return (B[l3]-B[l1]*(M[l1]-M[l2]) < (B[l2]-B[l1])*(M[l1]-M[l3]));
    }
 
    double Cross(int a, int b) {
        return (double)(B[b] - B[a]) / (M[a] - M[b]);
    }
 
    void add(ll m,ll b){
        if(M.size()>0){
            if(M[M.size()-1]== m){
                B[M.size()-1]= min(B[M.size()-1],b);
            }
            else{
                M.push_back(m);
                B.push_back(b);
            }
        }
        else{
            M.push_back(m);
            B.push_back(b);
        }
 
        while(M.size()>=3 && Cross(M.size()-3,M.size()-2)> Cross(M.size()-2,M.size()-1) )
        {
            M.erase(M.end()-2);
            B.erase(B.end()-2);
        }
    }
 
    ll getval(ll x,int id){
        return B[id] + x*M[id];
    }
    ll query(ll x){
        int l = 0,r = M.size()-1,mid;
 
        while(l<r){
 
            mid = (l+r)/2;
            if(Cross(mid,mid+1)>=x)
                r = mid;
            else
                l = mid+1;
        }
        return getval(x,l);
    }
};
 
 
 
2. X가 증가형태로 주어지는 경우. O(1)으로 해결하는 방법.
 
struct convex{
    ll M[N],B[N];
    int sz,pos;
    double Cross(int a, int b) {
        return (double)(B[b] - B[a]) / (M[a] - M[b]);
    }
 
    void add(ll m,ll b){    
        M[sz] = m;
        B[sz++]= b;
 
        while(sz-pos>2&& Cross(sz-3,sz-2)> Cross(sz-2,sz-1) ){
            M[sz-2]= M[sz-1];
            B[sz-2]= B[sz-1];
            —sz;
        }
    }
 
    ll getval(ll x,int id){
        return B[id] + x*M[id];
    }
    ll query(ll x){
 
        while(pos+1<sz){
            if(Cross(pos,pos+1)<=x)++pos;
            else
                break;
        }
        return getval(x,pos);
    }
};
cs


'알고리즘' 카테고리의 다른 글

[기하] 다각형의 내부 외부 판별  (0) 2018.05.13
BOJ 6171) 땅따먹기  (0) 2018.05.13
DP최적화 - Convex Hull Trick  (0) 2018.05.06
Sqrt Decompositon(평방분할) & Mo's Algorithm  (0) 2018.04.05
문자열 해싱  (0) 2018.03.31
Min Path Cover in DAG  (0) 2018.03.31

BOJ8462) 배열의힘



먼저 이 문제를 살펴보자


n개의 원소가 존재하고, [L,R] quer가 들어올 때 마다 부분 배열의 힘을 구하는 것이다.


* 여기서 Ks라 하면 자연수 s의 개수를 뜻하는데, 부분배열에서 이 모든 자연수 s에 대해 Ks * Ks * s 를 구하는 것이다.



=> 나이브하게 모든 query에 대하여 다 훑어본다면 O(N^2)의 시간복잡도를 갖는다.




이 때 Sqrt decompostion을 적용해보자.


Sqrt Decomposion이란?


* 간단하게 N개의 집합을 sqrt(N)개의 집합으로 나누어 값을 다룬다고 생각하면 되는데,

 이 문제에서는 query 에 적용하는 Query Sqrt Decompostion을 사용할 것이다.


또한 query에 대하여 분할 하는 것을 Mo's algorithm이라고 한다,


각각 query[L,R]에 대해서 L/sqrt(N)으로 정렬한다. 만약에 값이 같은경우, R 값을 그다음 키값으로 정렬한다. (오름차순)


정렬을 하게 되면 query의 순서가 뒤바뀌기 때문에 따로 index값을 저장해주어야 한다.

값을 변경하는 query (update query) 가 존재하는경우 이 알고리즘을 적용할 수 없다. 



대신, 구간의 특정 수의 개수를 구하는 거 같은 특수한 형태의 문제에는 아주 잘 적용된다.




결론적으로, N개의 원소가 존재하고 quert[L,R] 이 존재할 때, L/sqrt(N)과 R우선순위로 정렬 하게 된다면


theorem

1. N/sqrt(N) == sqrt(N)개의 집합이 형성된다.

2. 하나의 Block 내에서 query(L,R] -> [L',R']의 변화가 있다면,L'-L <= sqrt(N)이고 R <= R' 이다. 

3. 동일 Block내에서 R의 변화는 최대 N까지이므로, 최종적으로 모든 query에서의 R은 O(N^3/2) 시간복잡도 내에 변화한다.

4. 한 Block내에서 L의 range는 sqrt(N)이므로 최종적으로 모든 query에 대해서 L은 O(Q*sqrt(N)) 시간복잡도내에서 변화한다.

5. 그렇기 때문에 Mo's algorithm은 O((N+Q)*sqrt(N)*F) 의 시간 복잡도를 갖는다. (F는 L,R의 변화할 때마다 값을 처리해주는 함수를 만들었을 때, 그 함수의 처리 시간이다.)




이렇게 window size 로 정렬을 해주고.

현재의 알고있는 l값과 r값을 이용하여 꿈틀꿈틀 조정하게 되는데, 이 꿈틀꿈틀의 시간복잡도가 O(n*sqrt(n)) 인 것이다.


그러므로 구간합 구하기, 최대값 구하기 같은 유형의 문제들을 굳이 segment tree나 fenwick tree를 구현하지 않아도, 최초의 [L,R]을 설정해놓고 정렬된 query를 훑으면서 [L,R] ->[L',R']로의 query range를 확장,축소 해나가면 해결이 가능하다.


8462배열의힘 solution code


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
55
56
57
58
59
60
61
62
63
64
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
 
ll h;
struct dot{
    ll l,r,id;
 
    bool operator < (const dot& A) const{
        return l/== A.l/h ? r < A.r : l/< A.l<h;
    }
};
 
dot query[101000];
ll res[101000];
ll cnt[101000];
 
ll move(ll flag,ll val){
    cnt[val] += flag;
    return (2ll * flag *cnt[val] - 1)*val;
}
ll n,k,l,r;
ll sum;
int main(){
    scanf("%lld %lld",&n,&k);
 
    h = sqrt(n);
 
    vector<ll> a(n+1,0);
 
    for(int i = 1; i <= n ; i++)
        scanf("%lld",&a[i]);
 
    for(int i = 0 ; i < k; i++){
        scanf("%lld %lld",&query[i].l,&query[i].r);
        query[i].id = i;
    }
 
    sort(query,query+k);
 
    l = query[0].l;
    r = query[0].r;
    for(int i = l; i<= r; i++){
        sum += move(1,a[i]);
    }
 
    
    res[query[0].id] = sum;
 
    for(int i = 1; i < k ; i++){
        while(l > query[i].l) sum += move(1,a[--l]);
        while(l < query[i].l) sum += move(-1,a[l++]);
        while(r > query[i].r) sum += move(-1,a[r--]);
        while(r < query[i].r) sum += move(1,a[++r]);
        res[query[i].id] = sum;
    }
 
    for(int i = 0 ; i < k ; i++){
        printf("%lld\n",res[i]);
    }
}
cs



'알고리즘' 카테고리의 다른 글

BOJ 6171) 땅따먹기  (0) 2018.05.13
DP최적화 - Convex Hull Trick  (0) 2018.05.06
Sqrt Decompositon(평방분할) & Mo's Algorithm  (0) 2018.04.05
문자열 해싱  (0) 2018.03.31
Min Path Cover in DAG  (0) 2018.03.31
L-R flow : 하한이 있는 플로우  (0) 2018.03.31

String hash 함수

일반적인 자료구조로서의 해쉬, 그중에서도 문자열을 어떤 양의 정수값으로 변환하는 해시 함수이다.



(1) 좋은 해쉬함수의 조건

- Determinism : 같은 수를 넣을 경우 해시함수는 항상 같은 값을 리턴해야 함. 즉 외부상황에 따라 값이 달라지지 않고, 순수 내부 로직으로 작동


- Uniformity : input을 집어 넣었을 때, 어떤 output이 나오는 해시 함수가 있다고 하자.

 이 때 output range에 있는 각각의 값들이 나올 확률은 서로 대략적(roughly)으로 같아야 한다.

 이것은 해시의 충돌 확률을 낮추기 위해서다.

 충돌이 안 일어날 수록 좋은 해쉬 함수.


- 결과값이 Bucket Size를 넘지 않도록 범위를 조정할 것.


(2) String hash 함수의 알고리즘


일반적인 문자열 해시의 구현방법을 검색해 보았다.

그 결과 h = s[0]*k^(n-1) + s[1]*k^(n-2) ... 의 방식으로 구현한다.

또한 기존의 일부 string 해시함수 에서도 위 로직을 사용하고 있다.


왜 이런 형태로 구현할까? 이 구현 방식은 hashing에 사용하는 주요 알고리즘 중 하나인 Additive and Multiple Hashing이다.

이 방법은 해싱 처리할 대상 데이터를 순회하며, 데이터 요소 하나하나에 어떤 연산을 하고, 그 결과값을 초기 hash value에 더해 나간다.

데이터를 순회하면 hash value의 총 결과값이 완성되고 이것이 해쉬 코드가 된다.


문자열 해쉬 코드는, 각 문자의 배열 순서와 문자 요소의 값을 해쉬코드에 반영하여 하나의코드값을 만들어야 하므로, 위와 같은 알고리즘은 괜찮은 방법인 것 같다.



(3) h = s[0]*k^(n-1) + s[1]*k^(n-2) ...


이 알고리즘은 유사 난수(pseudo random number)를 발생시키는 수학 공식 중 하나인 lehmer의 multiplicative congruential algorithm과 형태가 닮았다.


k+1번째 난수 = {a*(k번째 난수) + c} mod N


이렇게 만들면 0~N의 범위 수에 대하여 난수 수열을 얻어낼 수 있다.

( a : 곱하는 상수, c : 더하는 상수, N : 최대 max 값.)


공식에서 a,c,N은 자기가 임의로 정하면 된다. 그러면 0~N 까지 난수 k의 수열을 얻을 수 있다.

 단 동일 범위에 대해 최대한 많은 난수를 뽑아내려면 어떤 세가지 조건을 만족해야 한다.

여기에서는 설명을 생략한다.


a와 N이 서로다른 소수라면 이 세가지 조건을 모두 만족한다고 한다.


위키에서 언급한 좋은 hash function의 요건과 위 수학공식을 비교해보니 적합하다는 생각이 들었다. 

좋은 해쉬함수의 요건 중 하나인 uniformity distribution 을 만족하기 때문이다. (정확한 수학적 원리는 생략한다)


또한 mod N 연산으로 0~N까지 확실한 범위에서 난수를 뽑아 주므로, 정해진 bucket index까지 수를 뽑기에도 좋다.


(4) 알고리즘 상수 정하기(a,c,N)


1. c는 문자열을 순회하며 만난 요소 (=한 문자)의 아스키 값으로 정했다. 

이에 따라 각 문자열을 해싱할 때, 구성하는 문자의 고유한 값이 반영될 것이다.


2.a는 처음에는 크게 상관없다고 생각했으나, 기존 코드 및 인터넷 검색을 해보니 대체로소수 (31) 을 사용하고 있었다. 

31 을 사용하는 이유는 32-1 , 즉 val을 bit-shift 5칸 한 것에서 val을 한 번 빼주면 되어서, 컴퓨터가 더 빠른 연산을 한다.


버킷 테이블의 개수인 N 또한, 소수로 만든다.

우린 1e9+9 를 사용할 것이다.



자 그럼 코딩 해보자.


 BOJ13713) 문자열과 쿼리


가장 긴 공통접미사를 비교하는 과정에서, 문자열 해싱을 통하여 비교연산을 O(1) 의 수행하였다.


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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
#include <string>
 
using namespace std;
typedef long long ll;
ll a = 31;
ll mod = 1e9+9;
 
 
 
string str2;
ll m;
ll tmp;
ll h[1001000];
ll len;
ll apow[1001000];
char str[1001000];
ll val(ll le,ll ri){
    ll ret = h[ri] - h[le-1]+mod;
    ret %= mod;
    return (ret*apow[le-1])%mod;
}
 
bool isequal(ll le,ll ri){
    return val(le,ri)==val(len -(ri-le) ,len);
}
 
ll func(ll pos){
    ll lo = 1;
    ll hi = pos;
    while(lo < hi){
        ll mid = (lo+hi)>>1;
        if(isequal(mid,pos)){
 
            hi = mid;
        }
        else{
            lo = mid+1;
        }
    }
    if(isequal(lo,pos))
         return pos-lo+1;
    return pos-lo;
}
int main(){
    freopen("input.txt","r",stdin);
    cin>>str2;
    len = str2.length();
    for(int i = 1; i <= len; i++){
        str[i] = str2[i-1];
    }
    
    scanf("%lld",&m);
 
    apow[0= 1;
    for(ll i = 1 ; i <= len;i++){
        apow[i] = (apow[i-1]*a)%mod;
    }
 
    for(ll i =1 ; i <= len;i++){
        h[i] = (apow[len-i]*(str[i]-'a'+h[i-1])%mod;
    }
 
    for(ll i =0 ; i  < m ; i++){
        scanf("%lld",&tmp);
        printf("%lld\n",func(tmp));
    }
 
 
 
}
cs



'알고리즘' 카테고리의 다른 글

DP최적화 - Convex Hull Trick  (0) 2018.05.06
Sqrt Decompositon(평방분할) & Mo's Algorithm  (0) 2018.04.05
문자열 해싱  (0) 2018.03.31
Min Path Cover in DAG  (0) 2018.03.31
L-R flow : 하한이 있는 플로우  (0) 2018.03.31
유량 테크닉  (0) 2018.03.31

+ Recent posts