주요 알고리즘 정리

 

* 다익스트라

static int Dijkstra(int s, int e) {
   PriorityQueue<Node> pq = new PriorityQueye<>();
   Arrays.fill(D, Integer.MAX_VALUE);
   Node cu = new Node(s, 0);
   pq.add(cu);
   while(!pq.isEmpty()){
      cu = pq.poll;
      
      if(cu.e == e) return cu.c;
      
      for(Node nd : list[cu.e]) {
         if(D[nd.e] > cu.c + nd.c) {
            D[nd.e] = cu.c + nd.c;
            pq.add(new Node(nd.e, (cu.c+nd.c) );
         }
      }
  }
  return -1;
}

 

* 조합 (nCr)

static int nCr(int n, int k) {
   if(BI[n][k]>0) return BI[n][k];
   else if (k==0 || n==k) return BI[n][k] = 1;
   else BI[n][k] = (int)((long)nCr(n-1, k-1) + nCr(n-1, k)) % MOD;
}

 

* 유클리드호제법(최대공약수)

static int GCD(int a, int b) {
   return (b==0)? a: GCD(b, a%b);
}

static int LCM(int a, int b) {
   return a*b / GCD(a, b);
}

 

* 플로이드워셜 (Floyd-Warshall) 

static void floydwarshall() {
  for(int k==1 ; k<= N ; k++) {
    for(int i==1 ; i<= N ; i++) {
      for(int j==1 ; j<=N ; j++) {
        D[i][j]= Math.min(D[i][j], D[i][k]+D[k][j]);
      }
    }
  }
}
      

 

* Union-Find (Dis-Joint Set)

static class DJS {
    int[] mom;
    DJS(int n){
      mom = new int[n+1];
      for(int i=1; i<=N ; i++) mom[i] = i;
    }
    public int find(int n) {
      return (mom[n]==n)? n : mom[n] = find(mom[n]);
    }
    public boolean union(int a, int b) {
      a = find(a);
      b = find(b);
      if(a==b) return false;
      mom[b] = a;
      return true;
    }
}

 

* Belman-Ford(벨만포드)

static boolean belman(int start){
  Arrays.fill(D, Integer.MAX_VALUE);
  boolean updated = false;
  D[start] = 0;
  D[N]=0;
  for(int i=1 ; i<=N ; i++){
     updated= false;
     // 모든간선 검사
     for(Node nd : list) {
        if(D[nd.s]==Integer.MAX_VALUE) continue;
        if(D[nd.e] > D[nd.s] + nd.c) {
           D[nd.e] = D[nd.s] + nd.c;
           updated = true;
        }
     }
     if(!updated) break;
  }
  
  if(updated) return true; // 음의 싸이클.. 존재
  else return false;
}

 

* 위상정렬 (DFS)

static int DFS(int here){
  visit[here] = true;
  for(Node nd : list[here]){
    if(!visit[nd.e]) 
       dfs(nd.e);
  }
  stack.push(here);
}

 

* LIS 

static int LIS_size(int[] V){
  ArrayList<Integer> list = new ArrayList<>();
  int tmp = 0;
  list.add(tmp);
  for(int i = 1; i<=N ; i++) {
     if(list.get(list.size()-1) < V[i]){
        list.add(V[i]);
        continue;
     }
     tmp = Collections.binarySearch(list, V[i]);
     if(tmp < 0) list.set(-tmp-1, V[i]);
  }
  return list.size()-1;
}

 

* ACL(최저 공통조상)

// 부모 관계 초기화
static void bfs(int here) {
  Queue<Node> qu = new ArrayDeque<>();
  Node cu = new Node(here, 0);
  qu.add(cu);
  while(!qu.isEmpty()){
     cu = qu.poll;
     if(visited[cu.e]) continue;
     vistied[cu.e] = true;
     Dep[cu.e] = cu.c;
     
     for(int nd : VT[cu.e]){
       if(!visite[nd]){
          Par[nd][0] = cu.e;
          qu.add(new Node(nd, cu.c+1);
       }
     }
  }
}

static void find() {
   for(int j=1 ; j<21 ; j++) {
      for(int i==1 ; i<= N ; i++) {
         Par[i][j] = Par[Par[i][j-1]][j-1];
      }
   }
}

static int LCA(int x, int y) {
  if (Dep[x] > Dep[y]) {
     int tmp = y;
     y = x;
     x = tmp;
  }
  
  for(int i = 20 ; i >= 0 ; i--) {
    if(Dep[y] - Dep[x] >= (1 << i))
        y = Par[y][i];
  }
  
  if(x==y) return x;
  for(int i=20 ; i>= 0 ; i--) {
    if(Par[x][i]!=Par[y][i]){
       x = Par[x][i];
       y = Par[y][i];
    }
  }
  return Par[x][0];
}
      

 

* Index Search

// Tree Depth size == Array 중간값
static int starIdx() {
  int ret = 1;
  for(ret=1 ; ret<=N ; ret*=2) ;
  return ret;
}

static void treeInit(int startIdx) {
  for(int i=startIdx ; i > 0 ; i--){
    Tree[i] = Tree[2*i] + Tree[2*i+1];
  }
}

static void update(int h, int v) {  // h 는 startIdx가 더해진 값. 
   Tree[h] = v;
   
   h/=2;
   for(int i=h ; i>0 ; i--) {
     Tree[i] = Tree[2*i] + Tree[2*i+1];
   }
}

static int query(int a, int b) {
  int result = 0;
  while(a<=b){
     // 시작하는 부분이 홀수인지 판단합니다.
     if ((a & 1) == 1) {
     	sum += Tree[a];
     	a++;
     }
     // 끝나는 부분이 짝수인지 판단합니다.
     if ((b & 1) == 0) {
     	sum += tree[b];
     	b--;
     }
     a /= 2;
     b /= 2;
  }
  // 밑에서부터 시작과 끝이 올라와서 만나게 된다면 그 구간은 현재 노드가 같은 부모인 것이고,
  // 현재 노드는 하위 모든 노드들의 합을 나타내는 것입니다.
  if (a == b)
     sum += tree[a];
  return sum;
}

 

*Prime (소수)

static void Prime() {
  for(int i=1 ; i <= 1000000 ; i++} {
     Prime[i] = true;
     for(int j=2 ; j*j <= i ; j++) {
       if(i%j == 0)
          Prime[i] = false;
          break;
     }
  }
}

 

* 단절점

static int DFS(int here, int dep, boolean root){
   D[here] = dep;
   int ret = D[here];
   int child = 0;
   for(int next : VT[here]) {
      if(D[next] == 0) {
         child++;
         int df = DFS(next, dep+1, false);
         if(!root && df >= D[here] ) C[here]=false;
         ret = Math.min(ret, df);
      } else {
        ret = Math.min(ret, D[next]);
      }
   }
   if(root && child >= 2) C[here] = true;
   return ret;
 }

 

* 누적합(펜윅트리)

static void update(int h, int v) {
  for(int i=h ; i <= N ; i+=(i&-1)) PT[i] += v;
}

static long query(int h) {
  long result = 0;
  for(int i=h ; i > 0 ; i-=(i&-i)) result+=PV[i];
  return result;
}