분류 전체보기
-
Chap 06. 우선순위 큐자료구조 with 윤성우 2021. 1. 29. 17:00
배열의 단점 - 데이터를 '삽입' 및 '삭제'하는 과정에서 데이터를 한 칸씩 이동하는 연산이 필요하다. - '삽입의 위치'를 찾기 위해 모든 데이터와 비교하여야한다. 연결리스트의 단점 - '삽입의 위치'를 찾기 위해 모든 데이터와 비교하여야한다. 위의 단점들을 보완하기 위해 우리는 '완전 이진 트리'인 힙을 사용하여야한다. ● 배열과 연결리스트의 단점이 '힙'에는 존재하지 않는다. ● 완전 이진 트리 (차곡 차곡 데이터를 쌓는 트리) ● 모든 노드에 저장된 값의 우선 순위는 자식 노드에 저장된 값의 우선순위보다 크거나 같아야한다. = 루트 노드가 우선순위가 높아야 한다. 배열과 연결리스트에서는 삽입을 하기 위해서는 삽입하는 데이터와 저장되어있는 데이터와 모두 비교를 해야한다. 하지만 은 1. ..
-
Chap 05. 트리자료구조 with 윤성우 2021. 1. 29. 16:21
트리는 '계층적 관계'를 표현하는 자료구조이다. 트리는 '비선형' 자료구조이다. ● 노드 : 트리의 구성 요소에 해당하는 요소 ● 간선 : 노드와 노드를 연결하는 선 ● 루트 노드 : 트리에서 최상위에 존재하는 노드 ● 단말 노드 : 아래로 다른 노드가 연결되어 있지 않는 노드 ● 부모 노드 : 연결된 노드 중 상위에 있는 노드 ● 자식 노드 : 연결된 노드 중 하위에 있는 노드 ● 형제 노드 : 부모 노드가 같은 노드 서브 트리 : 하나의 트리를 구성하는 왼쪽과 오른쪽의 작은 트리 서브 트리또한 서브트리로 이루어져 있다.(재귀적인 관계) 이진 트리의 조건 ● 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어 진다. ● 나뉘어진 두 서브 트리 모두 이진 트리어야한다. (재귀적) 트리는 루트노드부터 lev..
-
Chap 04.큐(Queue)자료구조 with 윤성우 2021. 1. 26. 13:06
먼저 들어간 것이 먼저 나오는 First In First Out = FIFO ex) 줄서기 typedef struct_lQueue { Node* front; Node* rear; }LQueue;//연결리스트 typedef struct _cQueue { int front; int rear; Data queArr[QUE_LEN]; }CQueue;//배열 rear - 입구를 나타내는 인덱스/노드 front - 출구를 나타내는 인덱스/노드 데이터 저장(enqueue) 하면 rear 이 이동 데이터 삭제(dequeue) 하면 front 가 이동 ● 큐(배열)의 문제점 비어있는 배열이 있지만, R이 오른쪽으로 이동할 수가 없다. 따라서, 이런 단점을 보완하기 위해 '원형 큐'가 도입되었다. ● 원형 큐의 문제점 R..
-
Chap 03. 스택(stack)자료구조 with 윤성우 2021. 1. 26. 12:15
● 스택의 기본 개념 마지막에 넣은게 가장 먼저 나온다 = Last In First Out = LIFO = 먼저 넣은게 가장 늦게 나온다 = Fist In Last Out = FILO ● stack의 구조체와 핵심 연산 typedef struct _node { Data data; struct _node *next; }Node; typedef struct _listStack { Node *head; }ListStack; - push : 넣는다. - pop : 꺼낸다. = 삭제한다. - peek : 통 안을 들여다 본다. ● 수식의 표기법 - 중위 표기법 피연산자들 사이에 연산자가 배치된 수식 연산의 순서에 대한 정보가 담겨 있지 않다. - 전위 표기법 피연산자들 앞에 연산자가 배치된 수식 5 + 2 / 7..
-
Chap 02. 연결리스트자료구조 with 윤성우 2021. 1. 26. 11:48
리스트에는 순차리스트와 연결리스트가 있다. '순차리스트'는 '배열'을 기반으로 구현된 리스트. '연결리스트'는 메모리의 '동적 할당'을 기반으로 구현된 리스트. - 배열 장점 : 접근이 빠르다 단점 : 메모리 사용 비효율적,데이터 삭제시 배열 처리 번거로움 - 연결리스트 장점 : 메모리 사용 효율적 단점 : 접근이 느리다 '연결리스트'를 공부하기에 앞서 다음 코드를 보자 typedef struct _node { int data; //데이터를 저장할 장소 struct _node* next; //다른 변수를 가리키기 위한 장소 }Node; Node 자체를 바구니라 지칭한다면, 바구니는 '구조체 멤버 next'를 통해 연결이 되어있다. '연결리스트'에 데이터를 [1,2,3,4,5] 순차적으로 추가할때, 연결리..
-
Chap 01. 자료구조와 알고리즘의 이해자료구조 with 윤성우 2021. 1. 24. 21:25
● 자료구조에 대한 이해 자료구조에서는 데이터를 표현하고 저장하는 방법에 대해서 설명한다. 내가 공부할 자료구조는 선형 자료구조와 비선형 자료구조 이다. 선형 자료구조 : 데이터를 선의 형태로 나란히 혹은 일렬로 저장하는 방식이다. ex) 리스트와 스택, 큐 비선형 자료구조 : 데이터를 나란히 저장하지 않는 구조이다. 자료구조는 '데이터의 표현 및 저장방법'이라 하였다. 그렇다면, 알고리즘은 '문제의 해결 방법'을 뜻한다. 예를들어, int arr[10] = {1,2,3,4,5,6,7,8,9,10}; for (int i = 0; i 시간복잡도 2. 어떤 상황에서 메모리를 적게 쓰는지, 많이 쓰는지 메모리의 사용량 => 공간복잡도 일반적으로, 알고리즘을 평가할때 '실행속도'에 초점을 둔다. '실행속도', ..
-
윤성우의 열혈 자료구조자료구조 with 윤성우 2021. 1. 24. 20:32
저는 자료구조를 C언어로, 윤성우의 열혈 자료구조로 공부하였습니다. 문제가 될시 답변 부탁드리겠습니다.