익숙하게 암기해야하는 소소한 코드들

<목차>

1. 에라토스테네스의 체

2. power(a,e)

3. DFS-재귀버전, BFS-큐버전

4. 다익스트라, 벨만포트

6. 머지소트, 퀵소트

7. GCD, 약수 구하기

8. 사선공식, 라인교차, convex hull

9. disjoint set

10. 반올림

--------------------

1. 에라토스테네스의 체

    //1~100000까지의 소수를 구한다. i=소수 when p[i]=0 

    int p[10001];

 

        p[1] = 1;

        for (int i = 2; i * i <= 10000; i++) { //i*i가 int 범위를 벗어날 위험이 있을 때는 i+i로.

               if (p[i] == 0) {

                       for (int j = i * i; j <= 10000; j += i) {

                              p[j] = 1;

                       }

               }

        }

2. power(a,e)

long long power(long long a, int e){

         long long y = 1;

        

         while (e){

                  if (e & 1) y *= a;

                  a *= a;

                  e >>= 1;

         }

         return y;

}

요령: 

  - 지수가 홀수이면 밑수 a를 한번 더 곱하고, 짝수이면 그냥 밑수의 제곱

  - a=2 e=(110)인 경우를 시뮬해보면 됨. 

    e       y         a

    110    1         2*2

    11     4          8

    1      32         16 

3. DFS-재귀버전, BFS-큐버전

//방문하지 않은 노드에서 대해서 재귀호출

void dfs(int u){ 

         visited[u] = 1;

         //do find action

         //do visit action

 

         for (int i = 0; i < g[u].size(); i++){

                  int v = g[u][i];

if (visited[v]) continue; 

                  dfs(v); //방문하지 않은 노드에 대해서 계속해서 재귀호출

         }

}

//방문하지 않은 노드를 큐에 push

void bfs(int s){

         queue<int> q;

 

         q.push(s);

         visited[s] = 1;

         dist[s]=0;

         while (!q.empty()){

                  int u = q.front(); q.pop();

                  //do visit action

                  for (int i = 0; i < g[u].size(); ++i){

                           int v = g[u][i];

if (visited[v]) continue;                                                  

                           visited[v] = 1;

                           dist[v]=dist[u]+1;

                           //do find action

                           q.push(v);                          

                  }

         }

}

4. 다익스트라, 벨만포트

//1. dist를 무한대로 초기화 하고, min_queue에 초기노드 push

//2. 큐가 빌 때까지 루프돌면서, 자식노드 v에 대해 relaxation(더 가까운 거리값으로 대체)

ll dijk(int s, int tgt){

         vector<int> dist(N+1,INF);

         dist[s] = 0;

         priority_queue<pli, vector<pli>, greater<pli> > q;

         q.push(make_pair(0,s));

 

         while (!q.empty()){

                  int u = q.top().second;

                  if (u == tgt) return dist[u];

                  ll uVal = q.top().first;

                  q.pop();

 

                  if (dist[u] < uVal) continue; //주의

                  for (int i = 0; i < adj[u].size(); ++i){

                           int v = adj[u][i].second;

                           ll newVal = uVal + adj[u][i].first;

                           if (newVal < dist[v]) {

                                   dist[v] = newVal;

                                   q.push(make_pair(newVal, v));

                           }

                  }

         }

 

         return -1;

}

6. 머지소트, 퀵소트

6.1 머지 소트

  - 1)왼쪽에 대해, 오른쪽에 대해 merge_sort한 후, 2)merge하고  3)merge한 부분 만큼의 배열부분을 update

  - 머지할 때 O(n)으로 처리하는 게 핵심

void merge(int s, int m, int e){

    int i,j,k;

    i=s; j=m+1;

    for(k=s;k<=e;++k){

        buf[k] = (i<=m && (j>e || a[i]<=a[j])) ? a[i++] : a[j++];

    }

}

 

void m_sort(int s, int e){

    if(s>=e) return;

    int m = (s+e)/2;

    m_sort(s,m);

    m_sort(m+1,e);

    merge(s,m,e);

    memcpy(a+s,buf+s,sizeof(int) * (e-s+1));

}

6.2 퀵 소트

- random p를 구하고, a[p]를 배열의 맨 끝값으로 교환

- i,j값을 배열의 맨 처음으로 놓고, j를 증가시키면서 a[j]와 a[e]값을 비교해서, 만약 큰 값이면 a[i++]과 교환

- 이렇게 j<e 까지 진행 키면, i번째를 기준으로 해서 왼쪽은 a[e]보다 작은, 오른쪽은 큰값이 놓이게 됨.

- 이제 a[i]와 a[e]값을 교환하고, i기준 왼쪽 부분과 오른쪽 부분에 대해 q_sort를 재귀호출하면 됨

time_t t;

srand((unsigned int)time(&t)); 

q_sort(1,N);

void q_sort(int s, int e){

    int i,j,p; 

    if(s<e){    

        p = s+rand()%(e-s+1);          

        swap(a[p],a[e]);       

        i=s;

        for(j=s;j<e;++j) if(a[j]<=a[e]) swap(a[i++],a[j]);    

        swap(a[i],a[e]);

         

        q_sort(s,i-1);

        q_sort(i+1,e);

    }  

}

7. GCD, 약수 구하기

//gcd(a,b) = gcd(b,a%b)임을 이용

int gcd(int a, int b){

         int t;

         while (!b){

                  t = b;

                  b = a%b;

                  a = t;

         }

         return a;

}

약수 구하기

vector<int> get_aliquot(n){

vector<int> v;

for(i=1;i*i<n;++i){

if(n%i==0){

v.push_back(i);

v.push_back(n/i);

}

}

if(i*i==n) v.push_back(i);

return v;

}

8. 반올림하기

- floor(x+0.5)

- 소숫점 세째 자리에서 반올림: floor(x * 100 +0.5)/100

- #define banollim(x,dig) (floor((x)*pow(10,dig)+0.5)/pow(10,dig))

-끝-