Computer Science17 [Algorithm] Floyd-Warshall 플로이드-워셜 Floyd-Warshall 3중 for문 사용 -> N^3 N=1000 인 경우, 10억 결론: N이 작을수록 유리하다 각 점을 시작점으로 정하여 다익스트라의 최단 경로 알고리즘을 수행 1 -> 2 3 4 5 ..... N 2 -> 1 3 4 5 ..... N 정점 간의 최단경로 계산 시간 복잡도는 인접 행렬을 사용하면 O(n^3)이다. 단, n은 정점의 수 warshall은 그래프에서 모든 쌍의 경로 존재 여부(transitive-closure)를 찾아내는 동적 계획 알고리즘을 제안했고, floyd는 이를 변형하여 모든 쌍 최단 경로를 찾는 알고리즘을 고안 D[i][j] = 정점 i에서 j로의 최소 비용 for k in 1->n // 경유지 for i in 1->n (단, i!= k) // 출발지 fo.. 2020. 9. 24. [Network] HTTP & HTTPS HTTP(HyperText Transfer Protocol) 인터넷 상에서 클라이언트와 서버 간 자원을 주고 받을 때 쓰는 통신 규약 HTTP 문제점 HTTP는 텍스트로 교환이 이루어지기 때문에 누군가 네트워크 신호를 가로채면 내용이 노출될 수 있다(보안 문제) 이 문제를 해결한 것이 'HTTPS' 이다 HTTPS(HyperText Transfer Protocol Secure) 인터넷 상에서 정보 암호화 SSL 프로토콜을 사용해 클라이언트와 서버가 자원을 주고 받을 때 쓰는 통신 규약 공개키 암호화 방식을 사용해 텍스트를 암호화한다 HTTPS라고 무조건 안전한 것은 아니다(신뢰도 높은 CA 기업이 아닌 자체 인증서를 발급한 경우) 이때는 브라우저에서 주의 요함, 안전하지 않은 사이트 와 같은 알람을 띄운.. 2020. 9. 24. [Algorithm] 그래프(Prim, Kruscal) 그래프의 표현 정점 중심 - 인접 행렬, 인접 리스트 : Prim 간선 중심 - 간선 리스트 : Kruscal Kruscal 간선을 비용기준 오름차순 정렬 비용이 가장 작은 간선(두 서로소 집합) 선택하여 신장 트리 처리(union처리) union의 성공을 사이클링의 여부로 볼 수 있다 정점이 N인 무향 그래프에서 최대로 가질 수 있는 간선의 개수 : N*(N-1)/2 2020. 9. 3. [Algorithm] 서로소집합 & MST(최소신장트리) 서로소 집합(disjoint sets) 하나의 집합을 하나의 트리로 표현 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다 Find_Set(x) : x를 포함하는 집합을 찾는 연산 집합: 집합의 구분자(ID), 대표자 MST 모든 정점을 연결하는 간선들의 가중치의 합이 최소!!! 두 정점 사이의 최소비용의 경로 찾기 신장트리 n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 최소 신장 트리 무향 가중치 그래프에서 신장 트리를 구성하는 가충치의 합이 최소인 신장트리 Kruscal(크루스칼) 1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬 2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 - 사이클이 존재하면 다음으로 가중치가 낮은 간선 .. 2020. 8. 11. 이전 1 2 3 4 5 다음
