본문 바로가기

컴퓨터과학/자료구조9

[자료구조] 9주차 - 그래프 탐색 (Graph search) Graph Search - DFS, BFS 그래프의 탐색 문제 : 그래프의 모든 vertex를 방문하는 문제 탐색하는 과정에서 중요한 요소 탐색 과정에서 이미 방문한 노드를 기록 visit을 저장하는 배열 탐색 과정에서 노드를 방문하는 순서를 기억 stack or queue 깊이 우선 탐색(DFS) 각 vertex V에서 V를 방문한 것으로 표시 (visit[V] = 1) v에 연결된 vertex w 중에서 아직 방문하지 않은 w를 방문 더 이상 방문할 vertex가 없으면 return 방문 순서를 stack을 이용해서 저장 void dfs(vertex u){ visit[u] = TRUE; for(w = graph[u]; w != NULL; w = w->link){ if(!visit[w]) dfs(w);.. 2021. 2. 4.
[자료구조] 8주차 - 그래프 (Graph) Graph node(vertex), edge(link), graph 쾨니히스베르크(Konigsberg) 다리 문제 홀수 개의 edge에 연결된 vertex의 수가 4개 이상이면 한 붓 그리기가 불가능 그래프의 개념 정의 개체들 사이의 일대일 관계를 시각적으로 표현한 수학적 모델 그래프는 vertex(꼭짓점, 정점)와 edge(간선)의 집합 G = (V, E) 그래프의 표현 그래프의 수학적 표현 V = {0,1,2,3} E = {(0,2), (0,3), (1,2), (1,3)} 그래프의 시각적 표현 Edge리스트를 이용한 표현 4, 4 : V의 수, E의 수 (Vertex : 0~3) 0, 2 : Edge 0, 3 : Edge 1, 2 : Edge 1, 3 : Edge 그래프의 종류 무방향 그래프, 방향 .. 2021. 2. 3.
[자료구조] 7주차 - 해시 (Hash) Hash 해시란 자료의 크기에 상관없이 실시간에 탐색이 수행되어야 하는 경우 O(1)의 탐색 시간을 추구하는 자료구조 및 알고리즘 정의 : 모든 키의 레코드를 산술 연산에 의해 한 번에 접근할 수 있는 기법 해시 함수(Hash function) 해시 인덱스(Hash index) 해시 테이블(Hash table) 충돌(Colision) & 충돌 해소(Collision resolution) 해시 함수 자릿수 선택 (digit selection) 키의 값 중에서 일부 자릿수만 골라내 인덱스를 생성하는 함수 h(8812152) = 8112 자릿수 접기 (digit folding) 키의 각각의 자릿수를 더해서 인덱스를 생성하는 함수 h(8812152) = 8+8+1+2+1+5+2 = 27 모듈로 연산 (modul.. 2021. 2. 2.
[자료구조] 6주차 - 트리 (Tree) Tree 선형 자료구조의 한계 2개 이상의 관계를 표현할 수 없음 계층적 구조 하나의 근원(root)으로부터 파생됨 한 노드가 여러 개의 노드로 전파됨 순환하는 경로(cycle path)가 없음 트리 루트(root)라고 불리는 특별한 노드가 있음 연결된 모든 노드의 쌍은 재귀적으로 부모자식관계(parent-child relation)을 맺음 순환하는 경로(cycle path)가 없음 용어 node (vertex) Root node, Leaf node, Internal node 부모 노드(Parent node), 자식 노드(Child node), 형제 노드(Sibling node) 조상 노드(Ancesor node), 후손 노드(Descendent node) 부분 트리 (subtree) Degree of .. 2021. 2. 1.

티스토리툴바