반응형 분류 전체보기340 [알고리즘] 순회 - 그래프에서의 DFS 순회 - 그래프에서의 DFS 2번째 순회 알고리즘으로 DFS(Depth First Search)에 대해서 알아보도록 하자 참고로, 이진 트리의 inorder, preorder, postorder는 모두 DFS라고 할 수있다. 그래프의 인접한 노드를 방문해서, 다시 그 노드의 인접한 노드로 계속 들어가다가끝에 도달 했을 때 돌아오는것이 DFS이다. 즉, BFS와 마찬가지로 시작점 s가 있어야하며 현재 노드를 visited로 체크하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다.위의 연산을 계속 반복하며 끝이 도달하면 다시 돌아오게 된다.그리고 unvisited가 있다면 해당 노드로 들어가며 앞서 했던 연산을 또 반복하게 된다. 결국 모든 순회를 마칠 경우 시작 노드 s로 돌아오게 되.. 2017. 5. 10. [알고리즘] 순회 - 그래프에서의 BFS 순회 - 그래프에서의 BFS 그래프에 대한 첫번째 알고리즘으로 순회(Graph Traversal)에 대해 알아보도록 하겠다. 순회란 그래프의 모든 노드들을 방문하는 일을 말한다. 아주 유명하고 대표적인 방법으로 1) BFS(Breadth-First Search) - 너비우선탐색2) DFS(Depth-First Search) - 깊이우선탐색두 가지 방법이 있다. BFS 알고리즘이란 한마디로 말해서그래프에서 노드들을 동심원의 형태로 방문하는 것이라고 할수있다.먼저 순회를 위해서 출발점을 지정해야한다. 위의 그림에서 출발점을 S라고 할 때, S에 인접한 노드들을 먼저 방문한다.이때 인접한 노드들이란, 거리가 1인 노드를 뜻한다.그리고나서 거리가 2, 3, ... 인 노드들을 차례로 방문한다. 결과적으로 동심원.. 2017. 5. 10. [알고리즘] 그래프의 개념과 표현 그래프의 개념과 표현 이번 시간에는 그래프의 개념과 그래프를 표현 하는 방법에 대해 알아보자그래프는 G = (V,E) 로 표현되며V : Vertex, 노드 혹은 정점E : Edge, 노드쌍을 연결하는 엣지 혹은 링크위와 같이 V와 E 들의 집합으로 나타내어진다. 그래프는 개체들 간의 이진 관계를 나타낼 수 있다.위의 그림은 8개의 vertex와 11개의 Edge를 가지고 있다.특별한 언급이 없는 이상 노드의 개수를 n, 엣지의 개수를 m으로 표현한다. 그래프의 종류는 여러가지가 있는데첫째로, 방향을 고려하지 않는 무 방향 그래프가 있다. 둘째로, 방향을 고려한 방향 그래프가 있다.위의 그림은 방향 그래프이다. 마지막으로, 그래프의 모든 엣지가 가중치(weight)를 가지고 있는 가중치 그래프가 존재한다... 2017. 5. 10. [알고리즘] 해싱(Hashing) - 3 해싱(Hashing) - 3 그렇다면 좋은 해시 함수란 무엇일까현실에서 키 들은 랜덤 하지 않다. 따라서, 만약 키 들의 통계적 분포에 대해서 알고있다면 이를 이용해서 해시 함수를 고안 하는것이 가능하겠지만 현실적으로 어렵다.그러므로, 키 들의 어떤 특정한(가시적인) 패턴을 가지더라도 해시 함수의 값이 불규칙 적이 되도록하는것이 바람직하다.즉, 해시 함수의 값이 키의 특정 부분에 의해서만 결정되지 않도록 해야한다.그래서 대부분의 해시함수를 구현할때 사용하는 연산들이 위와 같은 목적을 가지고 이루어 지게된다. 전형적인 해시함수는 여러가지 방법으로 만들어 질수 있는데, 첫번째로 Division기법이있다.이는 키를 테이블 사이즈로 나누어서 나머지를 구하는 연산이다.h(k) = k mod m위와 같은 식이 나오.. 2017. 5. 10. 이전 1 ··· 46 47 48 49 50 51 52 ··· 85 다음 반응형
