알고리즘/자료구조 (4) 썸네일형 리스트형 [자료구조]그래프 그래프란? 연결돼있는 객체 간 관계를 표현하는 자료구조 ex) 트리, 지하철 노선도 , 노드와 노드 사이를 연결선으로 표현할 수 있으면 그래프 오일러문제다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제 위치 : 정점다리 : 간선오일러 정리 : 모든 정점에 연결된 간선의 수가 짝수면 오일러 경로가 존재한다. ( 처음 출발한 장소로 돌아올 수 있다. ) 그래프 정의그래프 G = (V, E)- 정점(노드, vertex) : 여러가지 특성을 가질 수 있는 객체 의미, V(G) 그래프 G의 정점들의 집합, 공백 x- 간선(링크, edge) : 정점들 간의 관계 의미 , E(G) 그래프 G의 간선들의 집함, 공집합 0 *엣지가 하나도 없어도 그래프 될 수 있다. 동일한 그래프? - 그래프는 오직 정점과.. [자료구조] 우선순위큐 큐를 사용하는 예시가 뭐가 있을까 ? - cpu 의 round Robin 스케쥴링 : cpu 1 개로 여러가지 작업을 한다. 작은 시간을 쪼개면서 큐의 맨 앞에 있는 프로세스를 꺼내고 시간이 끝나면 큐의 마지막을 enque 시켜준다. * 이때 priority 우선순위가 높은 프로세스는 새치기가 가능하게 구현할 수 있다. -task 스케쥴링 : task 의 우선순위가 정해져 있다. 우선순위큐 priority queue- 우선순위를 가진 항목들을 저장하는 큐 - 우선순위가 높은 데이터가 먼저 나가게 된다.(우선순위 값이 미리 정해져 있다. 일반적인 큐가 아니지만 일반적인 큐로 구현은 가능하다.)- 스택이나 큐를 우선순위 큐로 구현할 수 있다. (늦게들어오면 높은 우선순위 (스택) , 빨리들어오면 높.. [자료구조] 이진탐색트리 탐색은 가장 중요한 컴퓨터 응용의 하나이다. 이때 바이너리 서치를 쓴다면 서치가 빨라진다. 이진탐색 트리 (BST binary search Tree) - 이진트리 기반의 탐색을 위한 자료구조- 효율적인 탐색 작업을 위한 자료구조 이다. *일종의 sorting 된 형태로 저장됌 탐색 관련 용어레코드, 필드, 테이블, 키, 주요키 데이터베이스라고 생각해도 된다. 이진 탐색 트리 임의의 키를 자긴 원소를 삽입, 삭제, 컴색하는데 효율적인 자료구조 즉 원하는 노드를 삽입, 삭제, 검색 하는것이라 볼 수 있다. 검색 속도가 빠르며 모든 연산은 키값을 기초로 실행한다. 여기서 키값은 노드의 데이터 이다. -이진트리이다.-공백이 가능하다. (empty 트리 가능) -모든 원소를 상이한 키를 갖는다. ( 모든 .. [자료구조] 트리 트리란 ? 계층적 구조를 나타내는 자료구조이며 주로 탐색을 위해 사용된다.*계층적 구조 : 하나의 자료 뒤에 여러자료가 연결되는 형태이다. db를 예로 들자면 1:n 관계라 할 수 있겠다. 선형적 구조 : 하나의 자료 뒤에 하나의 자료만 오는 구조이다. 배열이 대표적인 선형구조를 가지는 자료구조이다. 트리에 대한 설명 전 용어 정리부터 해보자. 트리의 용어 - 노드 : 트리의 구성요소 - 루트 : 부모가 없는 노트 - 서브트리 : 하나의 노드와 자손들로 이루어짐 - 단말노드 : 자식이 없는 노드 (leaf 노드)- 비단말노드 : 자식을 가지는 노드 - 자식, 부모 형제, 조상 , 자손 노드- 레벨(level) : 트리 각층의 번호- 높이 , 깊이(height, depth) : 트리의 최대 레벨- 차.. 이전 1 다음
