fishersheep

#include #include #include #include #include #include #include using namespace std; int bS(int* arr, int len, int value)//binarySearch 함수 { int start, mid, end; start = 0; end = len - 1; while (1) { if (start > end)//검색에 실패한경우 { cout

#include #include #include #include #include using namespace std; void insertionSort(int arr[], int n)//삽입정렬함수 { int temp = 0; int j; for (int i = 1; i = 0 && arr[j] > temp; j--)//i보다 작은 인덱스와 비교해서 arr[j]가 temp보다 크다면 { arr[j + 1] = arr[j];//오른쪽으로 값 이동 } arr[j+1] = temp;//위에 for문 조건에 맞지않으면 temp는 원래 있던 자리에 값에저장되고 조건에 맞다면 j--된 j에서 ..

탐색(Search) 탐색은 말그대로 데이터를 찾는 방법으로서, 자료구조에서 효율적인 탐색을 위해서는 어떤방식으로 찾을까 뿐만아니라 효율적인 탐색을 위한 저장방법을 고민해야한다. 순차탐색: 정렬되지 않은 데이터를 대상으로 하는 탐색 이진탐색: 정렬된 데이터를 대상으로 하는 탐색 이진탐색트리 이진탐색트리는 이진트리에서 데이터의 저장규칙을 더한 것으로 이 저장규칙은 특정 데이터의 위치를 찾는데 사용한다. 이진트리: 모든 노드의 자식 노드가 각각 최대 2개인 트리 이진탐색트리의단점: 이진탐색트리의 조건을 만족하면서도 저장순서에 따라서 탐색의 성능이 크게 저하될 수 있다. 이진탐색트리 조건 1. 노드에 저장된 키는 유일해야한다. 2. 루트노드의 키가 왼쪽 서브트리를 구성하는 노드의 키값들과 비교했을때 가장 커야한..

버블정렬(Bubble Sort) 버블정렬이란 인접한 두개의 데이터를 비교해서 정렬을 진행하는 방법이다. 버블정렬의 성능은 좋은편은 아니다. (정렬알고리즘에서 성능은 비교의 횟수와 이동의 횟수를 근거) ex) 배열에 숫자들을 오름차순으로 정렬할때 첫번째 수를 시작으로 끝의 숫자까지 인접한 수와 비교하고 이동한다. 선택정렬(Selection Sort) 선택정렬이란 제자리정렬 알고리즘중 하나이며, 오름차순으로 정렬한다면 가장 작은 최솟값을 맨앞에 놓고 그 이후의 값들을 하나씩 비교한 후 올바른 값을 선택하여 채워넣는 정렬방법입니다. 버블정렬과 비슷한 성능을 가지고 있다. 삽입정렬(Insertion Sort) 삽입정렬은 정렬대상을 정렬된 부분과 안된부분으로 두 부분으로 나눈 후 정렬안된부분의 데이터를 정렬된부분..

우선순위큐(Priority Queue) 우선순위큐는 선입선출인 큐와는 다르게 이름 그대로 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다. 우선순위의 판단기준은 데이터에 근거하며, 목적에 맞게 우선순위를 결정해야 한다. 우선순위큐 구현 방법: 배열기반, 연결리스트기반, 힙(Heap)기반 우선순위큐는 배열 및 연결리스트 보다는 힙으로 구현하는 것이 가장 바람직하다. 힙을 사용해야 이유: 배열과 연결리스트는 우선순위가 낮은 데이터를 삽입할 경우 모든 데이터와 우선순위를 비교해야 한다. 하지만 힙을 사용하면 삽입과 같은 과정을 진행할때 대부분 부모노드와 자식노드사이에서 비교연산이 이루어지기 때문에 힙은 트리의 높이 만큼 비교연산을 진행하면 된다. ->힙을 사용하여 우선순위큐 구현(우선순위큐는 추상적인 개..

트리(Tree) 트리는 비선형 자료구조로서 계층적 관계를 표현하는 자료구조 입니다. 트리구조의 예시: 기업의 조직도, 컴퓨터의 디렉토리 구조 (가지를 늘려가면서 뻗어나가는 특성을 가지는 구조들) 이진트리(Binary Tree) 이진트리는 루트노드를 중심으로 두개의 서브 트리로 나누어지는 트리로서, 나누어진 두개의 서브트리 역시 이진트리여야 합니다. (=자식노드가 2개씩 있는 트리) 이진트리는 노드가 위치할 수 있는 위치에 노드가 없다면 공집합 노드가 있는 것으로 간주합니다. 때문에 서브트리가 하나인 노드가 존재하더라도 이진트리가 될 수 있습니다. 이진트리의 일부 연산은 재귀호출을 사용합니다. 이진트리는 배열기반 및 연결리스트 기반으로 구현할 수 있습니다. 포화이진트리(Full Binary Tree): 모..

덱(Deque) 덱(Deque)은 double - ended queue의 줄인 표현으로서, 양방향으로 데이터의 삽입 및 제거가 가능한 자료구조 이다. 양방향으로 데이터의 이동이 가능한 특성때문에 큐와 스택을 조합한 자료구조로 이해할 수도 있다. 덱의 핵심 기능은 앞으로데이터삽입, 앞으로데이터제거, 뒤로데이터삽입, 뒤로데이터제거 이다. 덱 또한 배열 및 연결리스트로 구현이 가능하지만 덱의 특성상 가장 잘어울리는 것은 양방향연결리스트 이다. 덱(Deque)의 ADT DequeInit: 덱의 초기화를 진행하는 함수로서 제일 먼저 수행되어야 한다. DQIsEmpty: 덱이 비어있는지 확인하는 함수이다. DQAddFirst: 덱의 머리에 데이터를 저장하는 함수로서 매개변수로 전달된 데이터를 저장한다. DQAddL..

큐(Queue)란 큐는 스택과 같은 자료구조로서 스택과의 유일한 차이는 먼저들어간 데이터가 먼저 나오는 구조입니다. 이 구조는 비유하자면 먼저 들어간 차가 먼저 나오는 터널이 있다. FIFO(First-In, First-Out): 선입선출 큐 역시 스택과 마찬가지로 배열 또는 연결리스트를 기반으로한 구현이 가능하다. Queue의 ADT QueueInit: 제일 먼저 호출해야하는 함수로서 큐의 초기화를 수행한다. QIsEmpty: 큐가 비었는지 확인하는 함수이다. 비었으면 TRUE, 비어있지않으면 FALSE를 반환한다. Enqueue: 큐에 데이터를 저장하는 함수로서 매개변수로 전달받은 데이터를 저장한다. 스택의 push와 같은 역활이다. Dequeue: 가장 앞선 데이터를 삭제하는 함수로서, 삭제된 데이..

스택(Stack) 스택이란 선형자료구조의 일종으로서 후입선출 방식의 자료구조이다. (LIFO: Last - In, First - Out) 간단하게 생각하면 한쪽만 뚫려있는 통을 생각하면 된다. 이 통에 무언가를 넣고 뺄때 먼저 들어간건이 나중에 나오게 될 것이다. 스택은 배열 또는 연결리스트를 사용하여 구현이 가능하다. (배열과 연결리스트 모두 선형 자료구조) 스택의 ADT StackInit: 스택의 초기화역활로서, 제일먼저 호출해야한다. IsEmpty: 스택이 비어있는지 확인하는 역활이다. Push: 스택에 데이터를 저장하는 역활이다. 매개 변수로 받은 데이터를 저장한다. Pop: 마지막에 저장된 요소를 삭제 및 반환한다. Peek: 마지막에 저장된요소를 반환하지만 삭제는 하지않는다. 연결리스트로 구현..

CLinkedList.h 노드와 리스트를 정의하고 사용될 함수를 선언하는 헤더파일입니다. #ifndef __C_LINKED_LIST_H__ #define __C_LINKED_LIST_H__ #define TRUE 1 #define FALSE 0 typedef int Data; typedef struct _node { Data data; struct _node* next; }Node; typedef struct _CLL { Node* tail; Node* cur; Node* before; int numOfData; }CList; typedef CList List; void ListInit(List* plist); void LInsert(List* plist, Data data); void LInsertFr..