본문 바로가기

전체 글42

[graph]위상정렬 위상 정렬이란?DAG(Directed Acyclic Graph), 즉 방향 사이클이 없는 방향그래프에서 노드들의 순서화를 진행하는 것을 말한다. 즉 노드들간의 순서를 정렬한다는 의미이다. 위상정렬 알고리즘첫번째TopologicalSort(G) {for 1 to n{indegree가 0인 임의의 정점 u를 선택A[i] 2017. 7. 25.
[graph] BFS,DFS graph를 나타내는 2가지 방식인접 행렬(Adjacency matrix)nxn 형태의 행렬로 나타냄. M(i,j)는 정점 i와 j를 연결하는 간선이 존재한다는 의미가 된다. 무방향그래프라면 i와 j가 서로 연결된 상태이며 M(i,j)=M(j,i)인 상태이다.저장공간은 O(n^2)이며, 어떤 노드 v에 인접한 모든 노드를 찾는것은 행렬의 한 row를 전부 탐색하는 것과 같기 때문에 O(n)이고, 어떤 간선 E(u,v)가 존재하는지 확인하는 것은 M(i,j)를 확인하면 되므로 O(1)이다.인접 리스트(Adjacency list)정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트이다. 예를 들면 간선 E(1,2), E(1,5), E(5, 4)가 존재한다고 할 때 정점의 배열의 원소 중.. 2017. 7. 23.
R과 JDBC 연동 oracle 연동..driver drv 2017. 7. 17.
[DP]행렬곱 1번째부터 n번째의 모든 행의 곱인을 구하기 위해서는 여러가지 방법이 있다. 우선 첫번째 행렬이 pxq인 행렬이고 두번째 행렬이 qxr인 행렬인 경우 결과값으로 나오는 행렬은 pxr인 행렬이라는 것은 고등학교 수학 수업중 배웠을 것이다. 또 간단한 행렬에 대하여 곱을 수행해보면 총 연산 횟수는 pxqxr이라는 것을 알게 될 것이다. 그렇다면 이러한 여러 행렬의 곱연산은 어떨까? 행렬은 일단 교환법칙이 성립되지 않기 때문에 서로 자리를 바꾸게 되면 결과가 바뀌게 된다. 하지만 결합법칙은 성립하여 이 두가지의 결과는 같다. 하지만 결과는 같을지라도 결합의 방식에 따라서 계산 횟수가 달라지게 된다. 예를 들면 행렬 A를 10x100, B는 100x5, C는 5x50이라고 할 때 새 행렬 ABC는 10x50의 .. 2017. 7. 16.

티스토리툴바