개발 및 일상 블로그 개발 및 일상 블로그

너비 우선 탐색(BFS)은 그래프를 순회하는 일반적인 기술이다. 그래프 G의 BFS 순회 - G의 모든 정점과 간선을 방문한다. - G가 연결되었는지 여부를 결정한다. - G와 연결된 컴포넌트를 계산한다. - G의 스패닝 포레스트를 계산한다. - n개의 정점과 m개의 간선이 있는 그래프의 BFS는 O(n+m) 시간이 걸린다. (최단 경로를 찾는 다익스트라 알고리즘은 리니어 타임에 해결이 불가능하다) - 주어진 두 정점 사이에 최소 간선을 가진 경로를 찾고 보고할수 있다. (DFS는 불가능한 핵심 요소) BFS 알고리즘 - DFS와 마찬가지로 정점과 간선의 label을 설정하고 확인하는 메커니즘으로 사용된다. Algorithm BFS(G) Input Graph G Output labeling of the ..

Subgraph(부분그래프) 그래프 G의 부분 그래프 S가 있다고 가정하자. 이 때, - S의 정점은 G의 정점의 부분집합이다. - S의 간선은 G의 간선의 부분집합이다. Spanning subgraph - G의 스패닝 서브그래프는 G의 모든 정점은 포함하지만, 모든 간선은 포함하지 않는 서브 그래프이다. Connectivity(연결성) - 모든 정점 쌍 사이에 경로가 있는 경우 그래프가 연결된다. - 그래프 G의 연결된 구성 요소는 G의 최대 연결 부분 그래프이다. - 정점을 추가해도 connective 그래프가 된다면, connected component가 아니다. Tree & Forest 트리는 다음 속성을 가지는 undirected 그래프이다. - 트리 T는 연결되어있다. - 트리 T는 사이클이 ..

그래프는 (Vertex, Edge)로 이루어진 쌍이다. - V는 정점이라고 하는 노드 집합이다. (Vertex 라고 부름) - E는 정점 쌍들의 집합으로, Edge(간선)라고 부른다. - 정점과 간선은 위치 및 저장 요소이다. Edge Types(간선 종류) 1. Directed Edge - 순서 있는 정점 쌍 (u,v) [ (u,v)와 (v,u)는 다름. 방향성이 존재하기 때문 ] - 첫번째 정점 u는 원점이다. - 두번째 정점 v는 목적지이다. 2. Undirected Edge - 순서 없는 정점 쌍 (u,v) [ (u,v)와 (v,u(는 같음. 방향성이 존재하지 않기 때문] 3. Directed Graph - 모든 간선이 directed인 경우. 4. Undirected Graph - 모든 간선이 ..

Dictionary ADT - 딕셔너리 ADT는 검색 가능한 키 entry들을 모델링한다. - 딕셔너리의 주요 작업은 항목 검색 , 삽입 및 삭제이다. - 응용 프로그램에는 단어-정의 쌍 / 신용 카드 인증 / 호스트 이름을 인터넷 IP 주소에 대한 DNS 매핑 등이 있다. find(k) - 키가 k인 항목이 존재한다면, iterator를 반환하고 그렇지 않다면 iterator의 끝을 반환한다. put(k,o) - iterator를 삽입하고 반환한다. erase(k) - 키가 k인 엔트리를 제거한다. size() , empty() A List-Based Dictionary 로그 파일, 또는 audit trail은 정렬되지 않은 시퀀스를 사용하여 구현된 딕셔너리이다. 딕셔너리의 항목은(더블 링크드 리스트 ..

이진 탐색 트리는 내부 노드에 키를 저장하고, 특정 속성을 만족시키는 이진 트리이다. - u,v,w 노드중 u가 v의 왼쪽 하위 트리에 있고, w가 v의 오른쪽 하위 트리에 있도록 한다. - key(u) v.key() } return TreeSearch(k,v.right()) Insert - put(k,o) 연산을 수행하기 위해 TreeSearch를 사용하여 키 k를 검색한다. - k가 트리에 아직 없다고 가정하고, w는 탐색을 통해 도달한 leaf 노드가 된다. - 노드 w에 키 k를 삽입하고 내부 노드로 확장한다. Delete - erase(k) 연산을 수행하기 위해 키 k를 검색한다. - 키 k가 트리에 있다고 가정하고, v를 k를 저장하는 노드라고 가정한다. - 노드 v에 leaf child w가..

힙은 노드에 키를 저장하고 특정 속성을 만족시키는 이진 트리(binary Tree)이다. - Heap Order : 모든 내부 노드 V에 대해 root 노드보다 key(V) >= key(parent(V)) - Complete Binary Tree(완전 이진 트리) : h를 힙의 높이라고 할때, i=0,1, ... , h-1 이면 깊이 i에 대해 2^i개의 노드가 존재 h-1 깊이에서 내부 노드는 외부 노드의 왼쪽에 위치한다. - 힙의 마지막 노드는 제일 깊은 위치에서 가장 오른쪽 노드이다. - n의 키를 저장하는 힙은 O(log n)의 높이를 가진다. 힙과 우선순위 큐 - 힙을 구현하기 위해 우선순위 큐를 사용할 수 있다. - 각 내부 노드에 (key, element) 항목을 저장한다. - 마지막 노드의..

우선 순위 큐는 엔트리의 집합을 저장한다. 일반적으로, 엔트리는 (Key , Value)의 쌍으로 구성되며, key가 우선순위를 가르킨다. Priority Queue ADT Main Method -insert(e) : 엔트리 e 삽입 -removeMin() : 가장 작은 키에 해당하는 엔트리 제거 Additional Method -min() : 가장 작은 키에 해당하는 엔트리 리턴(삭제하지않음) -size() : 사이즈 리턴 -empty() : 큐가 비었는지 판단 우선 순위 큐 정렬 슈도 코드 Algorithm PQ_Sort(S,C) input sequence S, comparator C for the elements of S Output sequence S sorted in increasing orde..

컴퓨터 과학에서 트리란, 계층 구조의 추상적 모델이다. 부모 / 자식의 노드로 구성되어 있으며 조직도, 파일시스템, 프로그래밍 환경 등에서 응용된다. 트리 용어 Root : 부모가 존재하지 않는 최상위노드 Internal node(내부 노드) : 최소 한개의 자식을 갖는 노드 External node(외부 노드) : 자식이 없는 노드 Ancestors of a node(조상 노드) : parent,grandparent,great-grandparent etc.. Depth(깊이) : 조상의 개수의 수. 즉 , 노드에 도착하기 위해 거쳐야 하는 간선의 수. Height(높이) : 가장 깊이 있는 노드의 깊이 Subtree(서브 트리) : 트리 내에서 노드와 자손들로 구성된 다른 트리 Tree ADT Gene..