프로그래밍 공부

큐는 데이터를 처리하기 위해 일시적으로 쌓아 놓은 자료구조이다. 하지만 큐는 스택과는 다르게 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO, First In First Out)인 점이 스택과 다르다. 쉽게 이해하려면 은행 창구나 선착순 시스템을 생각하면 된다 먼저 온 사람한테 서비스를 제공하듯이 큐도 먼저 들어온 데이터부터 우선 처리해준다. 선형 큐도 있지만 원형 큐를 구현할 줄 알면 선형 큐도 구현할 수 있으니 굳이 설명하지 않는다. 코드 #include using namespace std; struct queue{ int max; // 큐의 최대 용량 int size; // 현재 요소의 개수 int front; // 프런트 int rear; // 리어 int *que; // 큐의 맨 앞..

스택은 데이터를 일시적으로 저장하기 위한 자료구조로 후입선출(LIFO, Last In First Out)이다. 말그대로 데이터를 쌓는다는 느낌으로 이해하면 된다 가장 나중에 쌓은 접시를 제일 먼저 사용하게 된다고 생각하면 이해하기 편할것이다. #include using namespace std; struct stk{ int max; int ptr; int *stk; }; int stk_init(stk* s, int max){ // 스택을 초기화 s->ptr = 0; if((s->stk = new int[max]) == NULL){ s->max = 0; return -1; } s->max = max; return 0; } int push(stk* s, int data){ // 스택에 데이터를 추가 if(s..

이진 검색은 데이터가 정렬되어있을 경우에 사용가능 한 검색 알고리즘이다. 선형검색보다 더 빠르다는 장점이 있다. 이진 검색은 인덱스의 중간에서 시작하고 중간 인덱스의 원소가 키 값보다 크면 첫번째 인덱스 부터 중간 인덱스 - 1 까지 검색해주고, 키 값보다 작으면 중간 인덱스부터 마지막 인덱스까지 검색을 해주고 이를 반복한다. 예를 들어 배열 안의 원소가 [ 1, 2, 3 ,4 ,5 ,6 ,7, 8]이 있을때 6을 찾으려고 하면 (0 + 7) / 2 = 3은 중간 값인데 찾는 키값은 6이다 따라서 중간 값보다 1 더 큰 4번 인덱스를 시작 인덱스 값으로 넣어주고 다시 검색을 하면 (4 + 7) / 2 = 5이다 아직도 찾는 값이 아니다 그리고 다음 중간 값은 (5 + 7) / 2 = 6 키 값을 찾았으면..

배열에서 데이터를 검사하는 방법중 하나인 선형 검색 또는 순차 검색으로 불리는 방법은 배열에서 데이터를 찾는 가장기본적인 방법이지만 확실하게 모든 요소를 검색할수 있고 정렬되지 않은 배열도 검색할수 있다는점이 장점이다. 말그대로 순서대로 배열을 검색하는 방법인데 배열의 처음 요소 부터 배열의 끝 요소 까지 반복하며 데이터를 찾습니다 반복문을 사용하여 구현합니다. while문 사용 int linear_search_while(const int arr[], int n , int key){ // while syntax int i = 0; while(true){ if(i == n){ return -1; } if(arr[i] == key){ return i; } i++; } } for 문 사용 int linear_..

이진검색트리 Binary Search Tree는 이진트리가 다음 조건을 만족하면 된다 1. 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작다 2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다. 3. 같은 키 값을 갖는 노드는 없다. 참고로 이진검색트리는 중위 순회를 하면 키 값의 오름차순으로 노드를 얻을 수 있다. 언어 : C++ 실행환경 : Visual Studio 2017 노드 struct BinNode { // 노드를 표현하는 구조체 int data; // 노드의 데이터를 나타냄 BinNode *left; // 왼쪽 자식 노드에 대한 포인터 BinNode *right; // 오른쪽 자식 노드에 대한 포인터 }; 노드는 구조체를 사용해서 만든다...

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include using namespace std; void insertion_sort(int *arr, int n){ int i,j; for(i = 1; i 0 && arr[j - 1] > tmp; j--) {// j가 0보다 크고, arr[j - 1] 값이 tmp보다 클 때 반복함 arr[j] = arr[j-1]; } arr[j] = tmp; } } int main() { int arr[5] = {3,2,5,9,1}; for(auto i : arr){ cout