* 직무의 이해

s직군에 대하여 삼성홈페이지 접속하여 조사하기


* Researcher & Developer 연구 개발자

- 혁신적인 기술을 바탕으로 한 제품 개발

(면접에서는 그 기술력을 잘 합쳐서 같이 협동할 수 있는 지를 본다.)

(혁신적인 기술을 얼마나 잘 하는 지 보다 같이 오래 할 수 있는 사람)

(시장과 고객의 needs를 파악한 합리적 가격의 제품 개발


* 요구되는 자질

- 소통 능력,  태도 ( 가장 주로 요구되는 것 소통능력)

- 책임감, 열정, 인내, 끈기

=> 이 두가지는 본인의 episode 로 이루어 지는것

=> 듣고 싶어 하는 대답을 잘 듣고, 잘 하는 것.

=> 성실함, 인상적인 부분은 보면 충분히 알 수 있다.

=> 이러한 episode 5개정도는 만들어 두는게 도움이 된다.


- 전문적인 지식과 기술력


* 자신의 가장 큰 강점은? 가장 잘하는 일을 말하라.

굉장히 잘했던 일 => 함께 무언가 잘했던 일을 말해라!

책임감이 가장 큰 강점인것 같습니다. => 함께 있을 때 빛나는 책임감을 말할 것.


* 동아리 활동이나 팀으로 일했던 경험은? 


* 팀 활동에서 성실하게 일하지 않은 사람은 없었는가?

책임감, 성실은 증명하기 어렵다.

=> 스토리라인을 위기를 극복한 것을 말하기

임원 보다는 팀원의 역할을 많이 해왔습니다. 너무 자기가 그러한 사람이다 라는 스토리는 별로.

위기를 극복한 episode를 정말 좋아한다. 증명이 불가능한 포인트는 위기극복 포인트로 말할 것.


        => 일단 한명을 죽여야 한다.? ㄴ ㄴ

팀으로 일하면서 이러한 상황이기 떄문에, 결국엔 극복 했습니다 로 가야한다.

가장 친한 친구를 말해 주세요.



인성 검사 강좌

300문항 + a

시간 : 50분



삼성그룹 면접 정공법


'자기계발과 잠재력개발' 카테고리의 다른 글

맛집탐방 북촌손만두  (3) 2018.08.01
면접 준비  (0) 2018.04.24

Array Doubling

* 우리는 계산할때 배열이 얼마나 필요한지 모른다.

* 새로운 원소를 삽입할때 room 이 필요하다면

- 두배의 길이 배열을할당한다.

- 새로운 배열로 값을 옮긴다


* t를 배열을 옮기는데 사용되는 cost 라고 하자.

- (n+1)을 삽입할때 doubling 이 발생한다고 하자.

-t*n의 시간이 걸린다  array-doubling 에

- t*n/2 + t*n/4 + t*n/8 + ... for previous array doubling

- 이것들은 t*n 보다 작다.

- total cost < 2t*n

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


<Minimum Path cover in DAG>


DAG(Directed Acyclic Graph)에서 모든 정점을 커버하는 겹치지 않는 최소의 경로의 수를 구하는 문제 


전체 정점의 수가 N 커버한 경로상의 간선이 X라면 N-X개의 경로로 커버할 수 있다.


만약에 간선으로 커버가 되지 않았다면, 각 정점 하나가 경로가 될 것이다.


따라서 최대한 간선을 많이 선택하면 된다.


따라서 X를 최대화 시켜야한다. 


간선을 고를 때 제약 조건은 한 정점이 선택 될 때 오직 하나의 indegree와 오직 하나의 outdegree가 선택되어야 한다는 점이다.


즉, indegree와 outdegree가 최대한으로 매칭되어야 한다.  


이를 이용하여 indegree를 상징하는 정점과 outdegree의 정점을 상징하는 정점으로 그래프를 구성하여 해당 그래프의 이분 매칭을 구함으로서 Minimum Path cover in DAG를 구할 수 있다.


참조: http://koosaga.com/entry/Path-Cover-of-DAG

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

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
codeforces)447b  (0) 2017.12.21

L-R flow


L-R flow란?


네트워크 플로우에서 각 간선에 흐를 수 있는 용량이 정해져 있듯이

무조건 흘러야 하는 하한이 정해지는 것이다.


이 하한을 어떻게 만족시켜야 할까? 

또는 하한을 만족시키면서 유량을 흘릴 수 있는지 어떻게 검사할까?



만약 a->b 간선을 e 라고 할 때, 이 간선에 흘러야 하는 하한을 l, 상한을 r이라고 하자.

또한 기존의 S,E 이외에 새로운 source 와 sink인 s,t 를 정의하자.




이떄 간선을 다음과 같이 구성하자


1. s -> b 로 cap = l 인 간선 (①에서 그래프에 하한인 l만 흐르게 하기 위함)

2. a -> t 로 cap = l 인 간선 (①에서 그래프에 하한인 l만 흐르게 하기 위함)

3. E -> S 로 cap = INF 인 간선 (①에서 S가 처음에 흘릴 유량에서 source가 아니기 때문에 무한한 유량을 제공하기 위함이다)

4. a -> b 로 cap = r-l 인 간선 (②에서 추가로 흐를 유량을 구하기 위함이다)





① 간선을 다음과 같이 구성한 후에 s에서 t로의 maxflow 를 구한다.

이 때의 maxflow == 간선 하한들의 합 과 같다면, 이 그래프는 하한을 만족하는 maxflow를 구할 수 있다는 것이다.



② 그 후에 한번 더 유량이 차있는 그래프 그대로 S에서 T로의 maxflow 를 구한다면, 하한을 만족한 후에 더 흘릴 수 있는 추가 유량을 구할 수 있다.



따라서 흐를 수 있는 유량은 maxflow(하한의 합)  + maxflow(추가 흐른양) 가 된다.

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

문자열 해싱  (0) 2018.03.31
Min Path Cover in DAG  (0) 2018.03.31
L-R flow : 하한이 있는 플로우  (0) 2018.03.31
유량 테크닉  (0) 2018.03.31
codeforces)447b  (0) 2017.12.21
알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수  (0) 2017.11.26

유량의 간선의 cap 1 증가 시켰을 때

말 그대로 하나만 1을 증가시켜서 dinic을 구한다. 

변화량이 많아봐야 1이다.

O(V+E) 


차있는 상태에서 한번 더 dinic 을 구하는 것.


유량 cap 1 감소시키는 것.

u->v 로 가는 간선에서, f == c 일때만 중요해.

u->v 에 풀 수 있다. (V+E) 

간선 우선순위를 정한다.



==> 응용하기


1,2,3,4 를 

mcmf 로 간선의 cost 2^1, 2^2, 2^3, 2^4 ...로 정해서  구한다.




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

Min Path Cover in DAG  (0) 2018.03.31
L-R flow : 하한이 있는 플로우  (0) 2018.03.31
유량 테크닉  (0) 2018.03.31
codeforces)447b  (0) 2017.12.21
알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수  (0) 2017.11.26
acm-cicpc 수학정복  (2) 2017.09.15

Intro to Estimote APIs


Estimote에서는 , physical world 를 위한 os를 만들었다.

이것의 의미는 ? os의 가장 중요한 역할은, apps API 가 하드웨어와 상호작용할 수 있다는 것이다.

예를들면, 마우스 클릭이나, 화면에 띄우는 것이다.


Physical world 를 위한 OS 는 다르지 않다. World 자체가 하드웨어라는것만 빼고,

우리는 사람들과 object 들의 이동을 관리하거나, displays 의 wireless 제어를 가능하게하는api를 제공한다.


Overview of the key APIs

* Proximity 란 근처에있는 ineterest 를 감지하는 앱이다. proximity beacon 은 근처에 있는 device 를 감지할 수 있다.


* Indoor Location 이란 GPS기술을 복사하여, indoors 에서도 활용할 수 있는 것이다. 공간 전체에 위치비콘을 배치하면, 우리는 자동적으로 바닥의 위치를 알 수있습니다.

UWB 전파와, estimate 기술에 따라서 바닥 좌표가 계산됩니다.

따라서 우리는 IOS app에서 indoor(x,y) 좌표를 얻을 수 있습니다.


* Nearables 란 자신의 상태나 존재를 블루투스를 통해서 알리는 smart object입니다. 당신의 key나 지갑이,당신의 스마트폰에게 신호를 보낸다고 생각해 보십시오. 

또는 커피머그잔이 온도가 낮아졌다고 말하는 것은요? 이것이  Nearable protocol and API.


또한 요즘엔, 대부분 object는 bluetooth 전파를 내장하지 않습니다. 이것이 우리가 Estimate Stickers를 만드는 이유입니다. 이것은 매우 작은 비콘으로 어떤object 에도 붙여서 nearable 할 수 있게 만들어 줍니다.


* Display(mirror) 는 근처의 디스플레이를 무선으로 조정할 수 있는 api입니다. 만약 공항에 들어갔을때, 공지사항이,뜨는 것을 생각해보세요, Mirror video-beacon 은 screen 의 HDMI나 USB 와 접속합니다. 


* Robotics 란, 우리의 최첨단기술인 indoor location 을 로봇을 위하여 만든 것입니다.



Estimote APIS at scale

physical world 와 소통하는 앱을 만드는 것이 중요합니다. 수천개의 장소에 비콘을 배치하는 것도 우리가, API를 가지고있는 한가지 이유입니다.


* Beacon Health Check란 비콘의 배터리량이나, 마지막이동했던 시간 같은 원격 측정 데이터를 Estimate Cloud로 전송합니다. 

이방법으로 우리는 당신에게 무언가를 알립니다.


* Remote Fleet Management. 만약 firmware를 업데이트 하거나 당신의 비콘 세팅이 필요할 때, Estate Cloud dashboard 나 API를 통해서, 바꿀 수 있습니다.

그들은 자동적으로 범위 안에있는 비콘들에 대하여 전파한다.


* Bulk Updater and deployment tools . 대용량의 비콘을 효율적으로 업데이트 해야하는 경우.


* Analytics . 어떤 지역과 object 가 가장 상호작용을 많이 했는지 감지한다.


ibeacon 과 Eddystone의 차이점. 

둘다 일단 bluetooth advertising protocols 이다. 이것은 bluetooth 를 통해서 전파한 데이터를 의미한다. 

'캡스톤' 카테고리의 다른 글

1. Intro to Estimote APIs  (0) 2018.03.30
elasticsearch 자료조사  (0) 2018.03.12
12.18 회의록  (0) 2017.12.20

1.    server - elastic search 연동방법


server python 경우 - Rest API(엘라스틱서치 내에 명령어) 사용하는 것은 불편하지만,  Python ES API 이용하면 elasticsearch 편하게 사용할 있다.


shell 에서 curl 출력결과는 단순 문자열이기 때문에 후처리를 하기가 어렵다. 따라서 python 이용하면 편리하다


python 이용하게 되면 doc 변수의 type string 아닌 map 형태이다.


링크 : http://jason-heo.github.io/elasticsearch/2016/07/16/elasticsearch-with-python.html


2. elastic search algorithm

엘라스틱서치는 기본적으로 Hash map 이용하기 때문에 amortized O(1) 시간복잡도로 검색이 가능하다.

우리가 사용하게될 매칭은 단순하게 키워드-시간 뿐이므로 어렵지 않을 .


엘라스틱서치는 역인덱싱(inverted index) 이용한다

역인덱싱이란 원본데이터가 id=1 문서와 , id=2 문서 안에 데이터 a,b,c 들어있다면 저장은 역인덱싱으로 데이터 a : 1,2 에서 등장,  b:  1,2 에서등장, c : 1,2 에서 등장  형태로 저장한다.


3. 인덱싱 설계(엘라스틱서치의 인덱싱이란 , db 데이터베이스)



* 인덱싱 테이블과 컬럼을 정한다.

* 원본 데이터를 어떤 형식으로 저장할 것인지 결정


document {

keyword : object,face

time : 

}


들어오게될 쿼리의 형태 : keyword-time

 

“query”:{

“bool” : {

“must”:[

{“match” : {“video1.keyword” : “keyword1”}}

}

]

}

}

최신순 정렬도 가능.

“sort”:[

{“video.time” : {“order”: “desc”}},

]



참조링크 : https://www.slideshare.net/xpressengine/xecon-phpfest2014elasticsearch


'캡스톤' 카테고리의 다른 글

1. Intro to Estimote APIs  (0) 2018.03.30
elasticsearch 자료조사  (0) 2018.03.12
12.18 회의록  (0) 2017.12.20

B번 문제인데 나름 까다로운 예외케이스가 존재한다.

n행, m열 이 주어질 때, n-1, m-1 개로 만들 수있는 모든 경우의수가 답이된다

이 때 짝수행, 홀수열 이나 홀수행, 짝수 열인 경우 -1 이 오게되면 답이 존재하지 않는다.


또한 범위가 10 의18승이므로 단순한 n*m 으로는  long long 조차 오버플로우가 난다.

따라서 리턴값에 함수를 한번더 사용하였다. 시간복잡도 O(log^2)



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
#include <cstdio>
#include <algorithm>
 
#include <vector>
 
using namespace std;
typedef long long ll;
ll n,m,k;
const ll mod = 1000000007;
 
ll mypow(ll a,ll b,ll c){
    ll ret = 1ll;
    while(b>0){
        if(b&1){
            ret = (ret * a) % c;
        }
        b /= 2;
        a = (a*a) %c;
 
    }
 
return ret;
}
int main(){
    freopen("input.txt","r",stdin);
scanf("%lld %lld %lld",&n,&m,&k);
 
if( k== -1){
    if(n%2 && !(m%2)){
        puts("0");
        return 0;
    }
    if(!(n%2&& m%2){
        puts("0");
        return 0;
    }
 
}
 
printf("%lld",mypow(mypow(2ll,m-1,mod),n-1,mod )) ;
 
 
 
 
 
}
cs


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

L-R flow : 하한이 있는 플로우  (0) 2018.03.31
유량 테크닉  (0) 2018.03.31
codeforces)447b  (0) 2017.12.21
알고리즘)(pow(A,B))mod C 를 logB 시간에 구하는 함수  (0) 2017.11.26
acm-cicpc 수학정복  (2) 2017.09.15
[BOJ1168] 조세퍼스 문제2  (0) 2017.01.22

+ Recent posts