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) ::= 우선순..

균형 이진 탐색 트리 이진 탐색 ve 이진 탐색 트리 이진 탐색 = 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 힘듦.(즉, 자료 삽입, 삭제시 앞 뒤의 원소를 이동시켜야함) 이진 탐색 트리 = 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조 이진 탐색 트리에서는 균형을 유지하는 트리라면 탐색 연산은 O(logn)의 시간복잡도를 가지지만, 균형 트리가 아닐 경우에는 O(n)로 시간복잡도가 높아지게 됨 이진 탐색 트리에서 균형을 유지하는 것이 중요함 -> 스스로 균형 트리를 만드는 AVL 트리가 존재함(상당히 복잡하므로 주제 전체를 다루지 않음) 1) AVL 트리 AVL 트리: Adelson-Velskii와 Landis에 의해 제안된 트리로서 각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브..

이진 탐색 트리 이진 탐색 트리(binary search tree) : 이진 트리 기반의 탐색을 위한 자료 구조 탐색(search) : 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미 레코드(record) : 하나 이상의 필드(field)로 구성 테이블(table) : 레코드(record)들의 집합 주요 키(primary key) : 각각의 레코드를 구별할 수 있는 키 탐색 작업을 할 때 주요 키가 입력이 되어 특정한 키를 가진 레코드를 찾게 됨 이진 탐색 트리는 이러한 탐색 작업을 효율적으로 하기 위한 자료구조 - 이진 탐색 트리의 정의 이진 탐색 트리: 이진 탐색 트리의 성질을 만족하는 이진 트리 이진 탐색 트리 - 모든 노드 키는 유일함 - 왼쪽 서브 트리의 키들은 루트의 키보..

깊이 우선 탐색과 너비 우선 탐색 스택을 사용하는 것 : 깊이 우선 탐색 (DFS. Depth First Search) 전략 => 최대한 갈 수 있는데 까지 가보고 막히면 다시 다른 길을 찾는 방식 이웃의 탐색 순서는 그림과 같이 상-하-좌-우 순으로 진행 현재 위치에서 생쥐는 항상 상-하-좌-우를 검사하여 갈 수 있는 위치이면 스택에 저장 다음으로 스택에서 꺼내지는 것은 항상 가장 최근에 저장된 위치 그림은 생쥐가 깊이우선으로 탐색하는 순서를 표시하고 스택의 변화를 보여주고 있음 큐를 사용하는 것 : 너비 우선 탐색 (BFS, Breadth First Search) 전략 => 탐색 순서에서 깊이보다는 폭을 우선으로 취함 이 방법에서도 마찬가지로 생쥐는 현재 위치에서 상-하-좌-우 순서로 인접 위치를 검..