자료구조10 chapter13 자료구조 큐 3.1 큐 ADT FIFO 선입선출 3.1.2 큐의 핵심 기능 : 삽입과 제거 연산 전단 : 큐의 가장 앞 요소 후단 : 큐의 가장 마지막 요소 삽입은 후단, 제거는 전단에서 수행된다. 3.2 순환 큐 전단과 후단을 가리키는 변수를 만든다. 삽입이 일어날 때 마다 후단의 위치 +1. 삽입이 이루어질 때 후단이 가리키는 위치에 데이터를 바로 입력. 배열의 시작과 끝을 연결하면 메모리 용량을 잘 사용할 수 있다. 전단과 후단 사이에 공백 메모리를 둬서 큐가 공백상태일 때는 전단과 후단이 같은 곳을 가리키고, 큐가 포화상태일 때는 후단이 전단보다 1 작은 값을 가지도록 하여 상태를 구분한다. 3.2.2 순환 큐의 기본 연산 순환 큐의 노드 구조체 선언 typedef int ElementType; typedef.. 2023. 4. 14. Chapter04 트리 알고리즘 4.1 트리 ADT 운영체제 파일 시스템 HTML, XML을 다룰때 쓰는 DOM 검색엔진, 데이터베이스 4.1.2 트리의 구성요소 뿌리 가지 잎 부모노드 : 바로 하위 노드가 자식노드 자식노드 : 바로 상위 노드가 부모노드 형제노드 : 한 부모 밑에서 태어난 노드 경로 : B-D-F는 B에서 F까지의 경로 경로의 길이 : 2 노드의 깊이 : 뿌리노드에서 해당노드까지 이르는 경로의 길이(B가 뿌리면 F의 깊이는 2) 레벨 : 깊이가 같은 노드의 집합 트리의 높이 : 가장 깊은 곳에 있는 잎의 노드까지의 깊이 차수 : 그 노드의 자식 노드 개수 트리의 차수 : 트리 내에 있는 노드들 중에 자식노드가 가장 많은 노드의 차수 4.2 이진트리 하나의 노드가 자식노드를 2개 까지만 가질 수 있는 트리, 즉 노드의 .. 2023. 4. 7. chapter02 자료구조 스택 2.1.1 스택의 개념 활용도가 높은 자료구조 (아래서는 자료구조를 말하지만 메모리에서) 지역변수는 스택에 할당된다. 요소의 삽입과 삭제가 한쪽 끝에서만 이루어진다 스택의 주요기능 : Push (삽입), Pop (제거) 2.2 배열로 구현하는 스택 각 노드를 동적으로 생성하고 제거하는 대신 스택 생성 초기에 사용자가 부여한 용량만큼의 노드를 한꺼번에 생성한다. (미리 메모리 용량을 정해줘야 함…) 그리고 최상위 노드의 위치를 나타내는 변수를 두고 삽입과 제거 연산을 수행한다. (아래에서는 다르지만, 생성 함수에서 바로 스택의 주소를 반환하면 포인터변수를 선언함과 동시에 값을 삽입할 수 있다.) #include #include //배열기반으로 구현되는 스택의 노드 typedef int ElementType.. 2023. 3. 27. chapter01 자료구조 리스트 (c언어) 1.1.1. 리스트의 개념 헤드 : 첫번째 노드 테일 : 마지막 노드 리스트의 길이 : 헤드부터 테일까지의 노드 개수 갖춰야할 연산 : Append(추가), Insert(삽입), Remove(제거), GetAt(반환) 1.1.2 리스트와 배열 비교 배열 : 배열의 크기를 지정해 줘야 하고 생성한 후에 그 크기를 변경할 수 없다. 리스트 : 배열 처럼 집합 보관 기능을 가지면서도 크기를 바꿀 수 있는 자료구조 1.2 링크드 리스트 구조 데이터 다음 노드를 가리키는 포인터 구현 노드를 표현하는 방법 : 구조체로 나타낼 수 있다. #include typedef int ElementType; struct Node{ ElementType Data; //데이터 struct Node* NextNode; //다음 노드.. 2023. 3. 27. chapter00 알아두면 쓸 데 있는 자료구조와 알고리즘 1. 자료구조 자료구조 : 컴퓨터가 데이터를 효율적으로 다룰 수 있게 도와주는 데이터 보관 방법과 데이터에 관한 연산의 총체 단순 자료구조 : int, char 등등 복합 자료구조 선형 : 데이터 요소를 순차적으로 연결하는 자료구조 배열 링크드리스트 스택 큐 힙 비선형 : 데이터 요소를 비순차적으로 연결하는 자료구조 트리 그래프 ADT (Abstract Data Types) 추상데이터 형식 자료구조가 갖춰야 할 일련의 연산 c언어로 표현하면 함수 ADT가 청사진을 제공하면 자료구조는 이를 구현한다. 예를 들어 리스트 구현(배열을 이용하여)할 때 리스트의 길이 : 배열의 길이 시작노드 : 배열의 첫 요소 마지막 노드 : 배열의 마지막 노드 현재노드 : 현재 요소의 인덱스 여기에 탐색/추가/삽입/수정/삭제 .. 2023. 3. 23. 6. 파이썬 마지막 자료구조 힙 1. 힙(Heap) 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 완전 이진트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾을 때 시간복잡도는 O(n)이다. 이에 반해, 힙에 데이터를 넣고, 최댓값과 최소값을 찾으려면 시간복잡도는 O(logn)이다. 우선순위 큐와 같이, 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘을 구현할 때 힙을 쓴다 2. 힙의 구조 최대힙 : 최대값을 가지기 위한 구조 최소힙 : 최소값을 구하기 위한 구조 다음 두가지 조건을 가지고 있는 자료구조 최대힙 : 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다 최소힙 : 각 노드의 값은 해당 노드.. 2023. 1. 21. 이전 1 2 다음
