자료구조와 알고리즘 ft. 수업/자료구조 정리
그래프 II
10.5 연결 성분 연결 성분(connected component): 최대로 연결된 부분 그래프 1. 그래프 상의 임의의 정점을 선택해 깊이 우선 탐색이나 너비 우선 탐색을 시작하면 시작 정점으로부터 도달 가능한 모든 정점들이 하나의 연결 성분이 됨 2. 다음에 방문 안된 정점을 선택해서 다시 탐색을 실행하면 그 정점을 포함하는 연결 성분이 구해짐 3. 그래프 상의 모든 정점이 방문될 때가지 이 과정을 되풀이하면 그래프에 존재하는 모든 연결 성분들을 찾을 수 있음 연결 성분 프로그램 void find_connected_component(GraphType *g){ count = 0; for(int i=0; in;i++){ if(!visited[i]){ // 방문되지 않았으면 count++; dfs_mat(..
그래프 I
10.1 그래프란? 그래프 소개 그래프(graph): 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프의 역사 수학자 오일러(Euler)는 "모든 다리를 한 번만 건너서 출발했던 장소로 돌아올 수 있는가?" 라는 문제에 대한 답을 그래프 이론을 이용해서 증명했음 -> 그래프의 모든 정점에 연결된 간선의 개수가 짝수일 때만 경로만 존재함 정점(vertex): 위치 간선(edge): 위치 간의 관계 오일러 경로(Eulerian tour): 그래프에 존재하는 모든 간선을 한 번만 통과하면서 처음 정점으로 되돌아오는 경로 그래프로 표현할 수 있는 것들 도로 영역 간 인접 관계 선수 과목 그래프의 용어 그래프: 정점(vertex)와 간선(edge)들의 집합, G=(V, E) V(G): 그래프 G의 ..
힙
8.3 힙 8.3.1 힙의 개념 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말함 힙 트리는 중복된 값을 허용함에 유리(이진 탐색 트리는 중복된 값을 허용하지 않음) 힙 안의 데이터들은 느슨한 정렬 상태를 유지 -> 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 힙의 목적: 삭제 연산이 수행될 때마다 가장 큰 값을 찾아 내기만 하면 되는 것이므로(가장 큰 값은 루트노드에 있음) 전체를 정렬할 필요는 없음 힙의 종료: 최대 힙(max heap), 최소 힙(min heap) 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리:..
우선순위 큐
8.1 우선순위 큐 추상 자료형 우선순위 큐의 소개 우선순위 큐(priority queue): 데이터들이 우선순뤼를 가지고 있고, 우선순위가 높은 데이터가 먼저 나가게 됨 자료구조삭제되는 요소 스택 가장 최근에 들어온 데이터 큐 가장 먼저 들어온 데이터 우선순위 큐 가장 우선순위가 높은 데이터 우선순위 큐의 추상 자료형 우선순위 큐 객체: n개의 element 형의 우선순위를 가진 요소들의 모임 연산: create() ::= 우선순위 큐를 생성 init(q) ::= 우선순위 큐 q를 초기화 is_empty(q) ::= 우선순위 큐 q가 비어있는지 검사 is_full(q) ::= 우선순위 큐 q가 가득찼는지 검사 insert(q,x) ::= 우선순위 큐 q에 요소 x를 추가 delete(q) ::= 우선순..
2. 균형 이진 탐색 트리
균형 이진 탐색 트리 이진 탐색 ve 이진 탐색 트리 이진 탐색 = 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 힘듦.(즉, 자료 삽입, 삭제시 앞 뒤의 원소를 이동시켜야함) 이진 탐색 트리 = 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조 이진 탐색 트리에서는 균형을 유지하는 트리라면 탐색 연산은 O(logn)의 시간복잡도를 가지지만, 균형 트리가 아닐 경우에는 O(n)로 시간복잡도가 높아지게 됨 이진 탐색 트리에서 균형을 유지하는 것이 중요함 -> 스스로 균형 트리를 만드는 AVL 트리가 존재함(상당히 복잡하므로 주제 전체를 다루지 않음) 1) AVL 트리 AVL 트리: Adelson-Velskii와 Landis에 의해 제안된 트리로서 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브..