Computer Science/Data Structure (10) 썸네일형 리스트형 Ⅹ 그래프 Chapter 10 그래프 1. 그래프란? ① 그래프의 소개 그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료구조다. 그래프의 대표적인 예는 지도이다. 지하철 노선도는 여러 개의 역들이 어떻게 연결었는지를 보여준다. 지도를 그래프로 표현하면 지하철의 특정한 역에서 다른 역으로 가는 최단 경로를 쉽게 프로그래밍해서 찾을 수 있다. 또한 전기 소자를 그래프로 표현하게 되면 전기 회로의 소자들이 어떻게 연결되어 있는지를 표현해야 회로가 제대로 동작하는지 분석할 수 있으며, 운영체제에서는 프로세스와 자원들이 어떻게 연관되는지를 그래프로 분석하여 시스템의 효율이나 교착상태 유무 등을 알아낼 수 있다. 이러한 많은 문제들은 공통적으로 도시, 소자, 자원, 프로젝트 등의 객체들이 서로 연결되어 있는.. Ⅸ 우선순위 큐와 히프 Chapter 09 우선순위 큐 1. 우선순위 큐 ① 우선순위 큐란? 우선순위 큐 (Priority Queue): 우선 순위의 개념을 큐에 도입한 자료구조 - 보통의 큐는 선입선출(FIFO)의 원칙에 의해 먼저 들어온 데이터가 먼저 나가게 된다. 그러나 우선순위 큐에서는 데이터들이 우선순위를 가지고 있고, 우선 순위가 높은 데이터가 먼저 나가게 된다. - 우선순위 큐는 다양한 응용 분야에서 유용하게 사용된다. 예를 들어, 다익스트라 알고리즘에서 최소 거리를 유지하거나, Huffman 코딩에서 빈도수가 높은 문자에 높은 우선순위를 부여하는 데 활용된다. 스택, 큐, 우선순위 큐 비교 자료구조 삭제되는 요소 스택 가장 최근에 들어온 데이터 큐 가장 먼저 들어온 데이터 우선순위 큐 가장 우선순위가 높은 데이터.. Ⅷ 트리 Chapter 08 트리 1. 트리의 개념① 트리란?트리는 계층적 구조를 나타내는 자료구조로, 실제 트리를 거꾸로 엎어 놓은 모양을 하고 있기 때문에 트리라 부른다. 리스트, 스택, 큐 등은 선형구조에 해당한다. - 트리는 부모-자식 관계의 노드들로 이루어진다. - 응용분야: 계층적인 조직 표현, 컴퓨터 디스크의 디렉토리 구조, 인공지능에서의 결정트리 (decision tree) - 트리의 종류는 이진트리와 일반트리가 있다. 기존의 자료구조와 다른 점은 ‘분류’의 개념이 들어가는 것이다. ② 선형 자료구조와 비선형 자료구조선형 자료구조(Linear) - 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것이다. - 자료들 간의 앞뒤 관계가 1:1의 선형관계 - 배열과 리스트가 대표적이고 더 나아가.. Ⅶ 연결 리스트Ⅱ Chapter 07 연결 리스트 1. 원형 연결 리스트① 원형 연결 리스트란?원형 연결 리스트(Circle linked List)란 단순 연결 리스트(Singly Linked List)의 마지막 노드의 포인터가 NULL이 아닌 헤드(첫 번째 노드)를 가리키는 형태의 리스트다. 따라서 리스트의 끝이 존재하지 않는다. 원형 연결 리스트에서 마지막 노드의 링크 필드는 NULL이 아니라 첫 번째 노드의 주소가 된다. 이러한 원형 연결 리스트는 하나의 노드에서 다른 모든 노드로 접근이 가능하다는 장점이 있다. 하나의 노드에서 링크를 계속 따라 가면 결국 모든 노드를 거쳐 자기 자신에게로 되돌아오는 구조를 갖추고 있다. 그래서 노드의 삽입과 삭제가 단순 연결 리스트보다 수월하다. 단, 삭제나 삽입 시 항상 선행 노.. Ⅵ 연결 리스트 Ⅰ Chapter 06 연결 리스트 Ⅰ 1. 리스트 ① 리스트란? 삽입과 삭제가 제한없이 아무 곳에서나 일어날 수 있는 자료구조 자료를 저장할 때 사용되는 자료구조 중 하나로 현실의 예에서는 버킷 리스트나 해야 할 일을 표시한 표를 들 수 있다. 큐도 일종의 리스트로 볼 수 있다. 리스트에는 항목들이 차례대로 정리되어 있고 각각의 항목은 순서나 위치를 가진다. *리스트와 집합은 같아 보일 수 있으나 집합은 순서의 개념이 없기 때문에 둘을 다르다고 할 수 있다. 리스트를 기호로 나타내면 다음과 같이 나타낼 수 있다. L = (A,B,C,….,(N-1)) 리스트의 기본적인 연산 1) 리스트에 새로운 항목 추가(삽입 연산) 2) 리스트에서 항목 삭제(삭제 연산) 3) 리스트에서 항목 탐색(탐색 연산) ② 리스트 .. Ⅴ 큐 Chapter 05 큐 1. 큐(Queue) ① 큐란? 삽입은 맨 뒤에서 진행되고 삭제는 맨 앞에서 진행되는 것이 큐 큐: 먼저 들어온 데이터가 먼저 나가는 자료구조 - 선입선출(FIFO: First-In First-Out) - (예) 매표소의 대기열 자료구조에서 가장 중요한 것(핵심)은 삽입&삭제 ② 큐ADT 객체: 0개 이상의 요소들로 구성된 선형 리스트 연산은 다음과 같다. create(max_size) :: = 최대 크기가 max_size인 공백큐를 생성한다. init(q) ::= 큐를 초기화한다. is_empty(q) ::= if(size == 0) return TRUE; else return FALSE; is_full(q) ::= if (size == max_size) return TRUE; .. Ⅳ 스택 Chapter 04 스택 1. 스택 ① 스택이란? 스택(stack): 쌓아놓은 더미 삽입하고 삭제하는 방식에 따라서 자료구조의 종류가 나뉜다. 즉, 자료구조를 결정하는 요인은 2가지다. 삽입과 삭제. - 스택에서 입출력은 맨 위에서만 일어나고 스택의 중간에서는 데이터를 삭제할 수 없다. - 입출력이 이루어지는 부분을 스택 상단(stack top)이라 하고 반대쪽인 바닥부분을 스택 하단(stack bottom)이라고 한다. - 스택에 저장되는 것을 요소(element)라고 부른다. - 스택에 요소가 하나도 없을 때 그러한 스택을 공백 스택(empty stack)이라고 한다. ② 스택의 특징 후입선출(LIFO:Last-In First-Out): 가장 최근에 들어온 데이터가 가장 먼저 나간다. 스택은 특히 자.. Ⅲ 배열, 구조체, 포인터 Chapter 03 배열, 구조체, 포인터 1. 배열 ① 배열이란? 타입이 같은 데이터들을 하나로 묶는 방법 ② 배열 ADT 배열은 elements로 구성, 각각의 요소는 인덱스로 표시한다. 배열은 elements로 구성, 각각의 요소는 인덱스로 표시한다. - Create 배열 구현 방법 create(10) int A[10]; get(A, i) value = A[i]; (read읽어와서 value에 집어 넣는 것) set(A, I, v) A[i] = v; ③ 1차원 배열 int list[6]; list[0] = 100; //set 연산에 해당된다. value = list[0]; // get 연산에 해당된다. ④ 배열의 응용: 다항식 프로그램에서 다항식을 처리하려면 다항식을 위한 자료구조가 필요하다. 어떤.. 이전 1 2 다음
