[CS(Computer Science)]/[자료구조 in C]

[자료구조] 이진트리와 시간복잡도 로그의 의미

이진트리란? : 모든 노드의 차수가 0 이상 2 이하인 트리 이진트리의 시간복잡도는 O(log(n))이라고 들어왔을 겁니다. 하지만 그 과정은 모르는 경우가 많다.(필자도 그랬다) 그래서 과정을 설명하려고 합니다. 그리고 왜 이진트리를 사용할수록 2배씩 빨라진다고 말하는지도 알아보도록 하겠습니다. 1. 이진트리 시간복잡도 계산 트리는 h의 높이를 가질때 최대 n = 2h - 1의 노드 수를 가지고 최소 n = h의 노드 수를 가집니다. 최대 n = 2h - 1 최소 n = h 기억할 것은 최대 노드의 개수!! 왜냐하면 빅오 표기법은 최악을 기준으로 삼기 때문에 가장 오래 걸리는 기준은 노드 수가 가장 많은 경우이기 때문입니다. n = 2h - 1 n + 1 = 2h log(n + 1) = h h = lo..

[자료구조] 정렬 : C언어

1. 정렬이란? : 정렬은 물건을 크기 순으로 오름차순이나 내림차순으로 나열하는 것 단순하지만 비효울적인 방법 삽입정렬, 선택정렬, 버블정렬 복잡하지만 효율적인 방법 퀵정렬, 히프정렬, 합병정렬, 기수정렬 2. 선택 정렬(selection sort) #include #include #define MAX_SIZE 10 #define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) int list[MAX_SIZE]; int n; // void selection_sort(int list[], int n) { int i, j, least, temp; for (i = 0; i < n - 1; i++) { least = i; // 최소값 탐색 for (j = i + 1; j < n; ..

[자료구조] 트리_하 : C언어

1. 수식 트리 : 후위 순회를 사용 루트 노드보다 자식 노드를 먼저 방문하여 수식의 값을 계산 연산자와 피연산자로 구성 연산자(operator) : 비단말노드 피연산자(operand) : 단말노드 계산 순서는 다음과 같다. 32*56*+ ==> 36 #include typedef struct TreeNode { int data; struct TreeNode* left, * right; } TreeNode; // + // * + // 1 4 16 25 TreeNode n1 = { 1, NULL, NULL }; TreeNode n2 = { 4, NULL, NULL }; TreeNode n3 = { '*', &n1, &n2 }; TreeNode n4 = { 16, NULL, NULL }; TreeNode n..

[자료구조] 트리_상 : C언어

1. 트리의 개념 리스트, 스택, 큐 등은 선형 자료 구조(linear data structure) 선형으로 나열되어 있는 구조 트리는 계층적인 구조를 나타내는 자료구조 트리는 부모 - 자식 관계의 노드들로 이루어진다 가족의 가계도나 회사의 조직도 등 트리에서 사용되는 용어 노드(node): 트리의 구성요소 루트(root): 부모가 없는 노드(A) 서브 트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리 비말단노드: 적어도 하나의 자식을 가지는 노드(A, B, C, D) 단말 노드(terminal node): 자식이 없는 노드(E, F, G, H, I, J) 자식, 부모, 형제, 조상, 자손 노드: 인간과 동일 레벨(level): 트리의 각층의 번호 높이(height): 트리의 최대..

[자료구조] 연결리스트(2) : C언어

1. 원형 연결 리스트 정의 : 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트 => 한 노드에서 다른 모든 노드로의 접근이 가능 => 원형이기 때문에 다른 노드들을 거쳐서 결국 자기자신으로 되돌아 올 수 있음 => 삭제나 삽입 시에는 항상 선행 노드를 가리키는 포인터가 필요 변형된 원형 연결 리스트 => 마지막 노드는 헤드 포인터인 헤드가 가리키고 첫번째 노드는 화살표 연산자를 이용해서 head -> link로 가리킴 => 헤드포인터가 마지막 노드를 가리키도록 구성하면 리스트의 처음이나 마지막에 노드를 삽입하는 연산이 단순 연결 리스트에 비해 용이하다. 1. 원형 연결 리스트의 처음에 삽입 ListNode* insert_first(ListNode* head, element data) { ListN..

[자료구조] 연결리스트(1) : C언어

리스트(list) 자료를 정리하는 방법 중에 하나 리스트의 기본 연산 1. 삽입 연산 리스트에 새로운 항목을 추가 2. 삭제 연산 리스트에서 항목을 삭제 3. 탐색 연산 리스트에서 특정한 항목을 검색 리스트의 구현 방법 리스트는 배열과 연결리스트를 이용하여 구현 가능 장점 단점 배열 간단하게 구현가능, 크기가 고정 1. 데이터를 중간에 삽입할 경우에 데이터들이 이동해야함 2. 데이터를 삽입할 경우 공간이 부족하면 더 큰 배열을 만들어서 데이터를 기존 복사하고 새로운 데이터를 추가 => cpu시간을 낭비시킴 연결 리스트 1. 중간에 쉽게 삽입/삭제 가능 2. 리스트의 크기가 제한되지 않음 임의의 항목에 접근할 경우 배열보다 시간이 오래 걸림 구조체로 정의한 리스트 #define MAX_LIST_SIZE 1..