본문 바로가기

ComputerScience/Algorithm

 (21)
floyd-warshall algorithm Floyd-Warshall 알고리즘은 all-to-all 알고리즘이다. 이전의 djikstra 알고리즘 같은 경우 one-to-one인 알고리즘이다. Notation d_k[i,j] : i 에서 j까지 {1,2,...,k}까지의 노드들만 지나서 가는 경로 d_0[i,j] = 0 if w[i,j] doesn't exist d_n[i,j] = 최단경로 ( 중간에 어떤 노드를 지나도 상관 없으므로) d_k[i,j] = min(d_k-1[i,j],d_k-1[i,k]+d_k-1[k,j])
dijkstra 알고리즘 최단경로를 찾는 알고리즘이다. 가정 1. 음수 가중치가 존재하지 않는다 2. 시작점 s로부터 최단 경로를 알아낸 노드들의 집합을 S 3. S에 속하지 않는 노드들 u에 대해, d[u]는 S의 노드들을 거쳐 u까지 오는 경로 중 최단 경로이다. Theorem. U에 속하는 모든 노드들 중 d[u]가 노드 u에 대해, d[u]는 s에서 u까지의 최단 경로이다. Proof) s에서 u까지 다른 최단 경로가 존재한다고 하자. 이 때, 가정 3에 의해, S에 속하지 않는 점 v를 지나게되는데, d[u] = d[v] + u(v,w)가 된다. 하지만 d[u]
최단경로 알고리즘 A . 최단경로 알고리즘의 특성을 정리해보면 1. 최단경로의 부분 경로는 부분경로에 해당하는 노드 간의 최단경로가 된다. 2. 최단 경로의 경우, 사이클이 존재하지 않는다. B. 최단 경로 알고리즘 Notation d[v] : start node에서 노드 v까지 최단 경로 estimate pi[v] : v까지의 최단경로 중 v의 직전 노드 C. Relaxation def relax(u,v,w): if d[v]>d[u]+w: d[v]=d[u]+v pi[v]=u D. Generic Algorithm 최단경로 알고리즘 문제는 , 노드와 에지들에 대해 어떤 순서로 얼마나 relaxation을 할 것이냐의 문제이다. E. Bellman-Ford Algorithm 최단 경로의 최대 에지 갯수는 n-1개 이므로 모든..
[javascript] MST-Kruskal 알고리즘 Minimum Spanning Tree를 구현하는 대표적인 방법 중 하나는 Kruskal 알고리즘이다. Def : Generic MST 어떤 mst의 부분집합 A에 대해서 A 합집합 Edge(u,v) 도 역시 어떤 MST의 부분집합이 될 경우, Edge(u,v)를 안전하다고 한다. A를 공집합에서 시작하여, 안전한 에지를 A의 원소의 갯수가 n-1이 될 때까지 반복한다. Th1 : A가 어떤 MST의 부분집합이고, (S,V-S)가 A를 Respect하는 컷 일 때, 이 컷을 Cross하는 에지들 중 가장 작은 가중치의 Edge(u,v)는 A에 대해서 안젆다. 밑에 Kruskal 알고리즘을 설명하며 이를 증명하였다. Kruskal Algorithm kruskal 알고리즘은 최소 가중치 순서대로 선택을 한다..
그래프 그래프 구현방법 1. 인접 행렬 - 인접 노드 탐색 시간 복잡도 : O(N) -> 한 행을 다 검색해야 한다 - 에지 탐색 시간 복잡도 : O(1) 2. 연결리스트 - 인접 노드 탐색 시간 복잡도 : O(degree(node)) - 에지 탐색 시간복잡도 : O(degree(node)) 위상정렬의 두가지 방법 1. indegree가 0인 애들을 찾는다. 그리고 outdegree 에지를 제거한 후 이 작업을 반복하면서 연결리스트 뒤에 추가한다. 2. DFS를 이용해 leaf child에 도달했을 때, leaf child를 제거하고 연결리스트 앞에 추가한다..
[프로그래머스] 점프와 순간이동 function solution(n) { var ans = 0; var end = n; var cost = 0; while(end!==0) { if(end%2===1) { end = (end-1)/2 cost++; } else{ end= end/2 } } return cost; } 이진수 변환 n.toString(2)을 활용하면 더 쉽다.
Hashing Hashing을 할 때 문제가 되는 것은 중복키이다. 2가지 해결 방법이 있는데 , chaining과 open addressing이다 1. Chaining 중복된 값일 경우, 각 칸을 연결리스트로 구현한다. 2. Open Addressing 중복된 값일 경우, 특정 규칙(linear,quadratic,double hashing 등)에 의해 빈칸이 나올 때까지 칸을 찾는 방법이다. linear probibg의 경우 clustering의 문제가 발생할 수 있기 때문에, quadratic, double hashing 등의 hashing 방벙이 있다. Hashing 성능 분석을 위한 가정 simle uniform hashing assumption 키값들이 확률적으로 Hashing 값에 동등하게 Mapping 된..
[프로그래머스] 소수만들기 function solution(nums) { var len = nums.length var answer =0; for(var i=0;i

티스토리툴바