728x90 자료구조6 힙 정렬(Heap Sort) 힙 정렬(Heap Sort)은 큌 정렬(Quick sort)과 병합 정렬(Merge Sort)과 같은 시간 복잡도 O(N*logN)를 가지고 있다. 힙 트리를 이용하는 정렬 방법이다. 힙 트리란 힙 트리의 조건 중 부모 노드의 값은 항상 자식 노드(하위 노드)의 값보다 크거나 작아야 한다. 힙 트리는 위의 조건은 만족하는 정렬은 두가지 뿐이다. 최대 힙(Max Heap), 최소 힙(Min Heap) 힙 트리 구조의 자녀 트리 사이에는 대소관계는 정해지지 않는다. 또한 힙 트리는 완전 이진 트리를 조건으로 가지고 있어야 한다. 왼쪽부터 차근차근 채워나가며 1~n까지 만들어지는 트리구조이다. 완전 이진 트리의 장점은 트리를 배열로 쉽게 구현이 가능하며, 부모 노드와 자식 노드 간에 관계를 수식화 할 수 있다.. 2021. 5. 14. C언어 - 큐, 큐 구현 (Queue), 배열 구현 큐는 FIFO 구조로 먼저 들어오면 먼저 나가는 성질을 가지고 있다. 스택과 비슷하면서도 다른 구조를 가지고 있다. 그래서 스택은 세워서 넣는 식으로 하고 큐는 눕혀서 넣고 빼면서 설명을 한다. 코드 #include #define MAX 5 int front = 0; int rear = 0; int queue[MAX]; void init(int data) { int tmp=(rear+1)%MAX; if(tmp == front) { printf(" Full "); printf(" \n"); return; } else { rear = (rear+1) % MAX; queue[rear]=data; } } void delete() { if(front == rear) { printf(" Emty "); printf.. 2021. 3. 12. 트리와 이진 트리(Binary Tree) 트리 구조란 그래프의 일종으로, 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 그리고 부모 노드와 자식 노드로 이루어진 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.(ko.wikipedia.org/wiki/트리_구조) 이진트리란 (Binary Tree) 컴퓨터에서 쓰이는 이진트리는 수학과 다르다. 컴퓨터에서 이진트리는 부모 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 이진 트리의 조건들 한 부모 노드에 자식 노드는 최소 0부터 최대 2개의 자식 노드를 가질 수 있다. 부모보다 작으면 왼쪽 자식 부모보다 크면 오른쪽 자식으로 보내야 한다. 이진트리를 순회하는 방식은 4가지가 있다. 1. 전위 순회 2. 중위 순회 3. 후위 순회 4... 2021. 2. 5. C언어 - 정렬 (Sort) 정렬이란 Computer Science 에서 정렬 알고리즘은 데이터를 일정한 순서로 나열하는것이다. 흔히 사용되는 것은 숫자 정렬과 문자 정렬 (사전순 정렬)이다. 좋은 정렬을 만들기 위해 알고리즘의 최적화가 중요하다. 정렬에는 다양한 종류가 존재한다. 크게 내부 정렬과 외부 정렬이 존재하고 내부 정렬은 하나의 배열에 저장할 수 있을 경우 사용되고 외부 정렬은 데이터가 많아 하나의 배열로 저장하기 어려울때 사용된다. 외부 정렬은 내부 정렬을 응용한 정렬이기 때문에 내부 정렬을 먼저 공부하면 된다. 내부정렬에는 순차 정렬, 버블 정렬, 선택 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬, 병합 정렬, 힙 정렬, 도수정렬 등 다양하게 존재한다. 순차 정렬 자세히 보기 버블 정렬 자세히 보기 선택 정렬 자세히 보기 .. 2020. 11. 13. C언어 - 배열 배열이란 같은 데이터형의 요소들이 동일한 크기를 나열되어 있는 집합이다. 이름으로 구분이 아닌 첨자에 의한 구분이라 그에 따른 장단점이 있다. 배열이 1 ~ n까지 있는 배열이 있다고 가정하면 c언어에서는 0 ~ n-1로 나타낸다. 배열도 변수와 같이 정수형 문자형 자료형 등으로 선언할 수 있다. //배열의 크기만 선언후 초기값을 설정하지 않음 int main() { int arr[5]; } //배열의 크기만 선언후 초기값을 설정하지 않음 int main() { char arr[5]; } 위와 같이 선언 가능하다. 배열에는 선언과 같이 초기화하는 것이 중요한데 초기화하는 방법은 아래와 같다. //배열의 크기설정과 배열의 값을 따로 지정, 크기 선언과 동시에 초기화를 해 주는것이 프로그래밍상 안전하다. i.. 2020. 11. 6. 자료구조 (Data Structure) 개념 및 정의 컴퓨터에서 자료를 효율적으로 사용하기 위해서 특성에 따라 분류 및 관리하여 저장 및 처리하는 모든 작업을 자료구조라 한다. 반복적이거나 복잡한 자료처리를 효율적으로 처리하기 위해 자료구조를 잘 이용해야 한다. 자료구조는 프로그래밍의 직접적인 영향을 미친다. 단순하게 하나의 반복을 생각하는 게 아닌 1000만 번 반복한다고 가정했을 때 자료구조가 주는 이점은 무시하기 어렵다. 이러한 자료구조가 모이면 알고리즘이라 할 수 있다. 정렬부터 선형구조 비선형구조 순으로 공부해 보자. 공부할 때 사용할 언어는 c언어이고 c언어를 택한 이유는 순차적 언어이기 때문이다. 선형구조 - 순차 리스트 또는 선형 리스트라고도 한다. 순차 리스트 - 데이터를 연속적인 기억공간에 배정하는 자료구조로서 배열, 큐, .. 2020. 10. 30. 이전 1 다음 728x90
