땡땡

순차검색에 대해 설명하시고 예제소스를 구현해보아라.

• 정렬되어있지 않은 배열의 처음부터 끝까지 단방향으로 비교하여 원하는 데이터를 찾아내는 알고리즘이다.
• 시간복잡도 : O(n)
• 장점 : 구현이 쉽고 단순하다
• 단점 : 배열의 크기가 크면 비효율적이다.

int sequentialSearch(int a[], int  length, int  target) 
{
	for (int i = 0; i < length; i++)
	{
		if (a[i] == target)
		{
			return i;
		}
	}
	return 0;
}

이분검색(Binary Search)에 대해 설명하시고 예제소스를 구현해보아라.

• 정렬되어있는 자료를 반씩 나누어 나머지 반만 검색하는 방식을 반복하여 자료를 찾는 검색(탐색)방법
• 시간 복잡도: O(log n)
• 장점 : 빠른 속도로 원하는 자료를 찾을 수 있다.

int BSearch(int arr[], int target) 
{
    int low = 0;
    int high = sizeof(arr)/sizeof(int)-1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target)
        {
            return mid;
        }
        else if (arr[mid] > target)
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return -1;
}

재귀함수를 이용하여 피보나치 수열을 구현해보아라.

• 피보나치 수열이란 ? 처음 두 항은 1이고 세번째 항부터 이전 두 항의 합이 된다. ( 1,1,2,3,5,8... )
• 재귀함수란? 자기자신을 return 값으로 가지는 함수

int fibo(int num)
{
	if (num == 0)
	{
		return 0;
	}
	else if(num == 1)
	{
		return 1;
	}
	else
	{
		return fibo(num - 1) + fibo(num - 2);
	}
}

[출처 및 참고 사이트]

https://cjh5414.github.io/binary-search/

https://mainia.tistory.com/4409

연결리스트(linked list)란?

• 연결리스트(Linked List)는 리스트의 항목들을 노드(Node)로 분산하여 저장하는 리스트이다.
• 노드(Node)의 구성으로는 데이터필드(데이터 저장) 와 링크필드(다른 노드의 주소값 저장)가 존재
• 장점 : 삽입과 삭제가 용이하며 연속된 메모리 공간이 필요 없기 때문에 크기 제한이 없다. 
• 단점 : 구현이 어렵고 까다롭고 오류가 방생하기 쉽다.
• 단순(단일) 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등이 있다.

단순 연결리스트(Simple linked list)에 대해 설명하시고 예제소스를 구현해보아라

• 하나의 링크 필드를 이용하여 하나의 방향으로 연결되어 있으며, 마지막 노드의 링크 값이 NULL인 연결리스트.
• 단점 : 한 노드에서 이전 노드의 역방향으로 노드를 탐색할 수 없다. 시간복잡도가 O(n)으로 속도가느리다.(맨처음 노드부터 탐색해야함)
• 예제
• addfront(element value) : 첫 노드에 추가
• addrear(delement value) : 마지막 노드에 추가
• void delfornt() : 첫 노드 제거
• void del(element value) : 특정 노드 제거
• void print_list(Node* Current) : 모든 리스트 출력

  #include <stdio.h>
  #include <stdlib.h>
  #include <malloc.h>
  
  typedef int element; 
  typedef struct Node
  {
  	element data;
  	struct Node* next;
  }Node;
  
  Node* pStart = NULL;		//리스트 처음
  Node* pEnd = NULL;			//리스트 마지막
  
  // 첫 노드에 추가
  void addfront(element value)
  {
  	Node* Current = (Node*)malloc(sizeof(Node));
  
  	Current->data = value;
  
  	if (pStart == NULL)
  	{
  		Current->next = NULL;
  		pStart = pEnd = Current;
  	}
  	else
  	{
  		Current->next = pStart;
  		pStart = Current;
  	}
  }
  
  // 마지막노드에 추가
  void addrear(element value)
  {
  	Node* Current = (Node*)malloc(sizeof(Node));
  
  	Current->data = value;
  	Current->next = NULL;
  
  	if (pStart == NULL)
  	{
  		pStart = pEnd = Current;
  	}
  	else
  	{
  		pEnd->next = Current;
  		pEnd = Current;
  	}
  }
  
  // 앞부분의 노드 제거
  void delfornt()
  {
  	if (pStart == NULL) return;
  
  	Node* Current = pStart;
  	pStart = pStart->next;
  	free(Current);
  
  }
  
  // 특정 노드 제거
  void del(element value)
  {
  	if (pStart == NULL) return;
  
  	if (pStart->data == value)
  	{
  		Node* Current = pStart;
  		pStart = pStart->next;
  		free(Current);
  		return;
  	}
  
  	Node* head = pStart;
  	Node* temp = head->next;
  
  	while (temp!=NULL)
  	{
  		if (temp->data == value)
  		{
  			head->next = temp->next;
  			free(temp);
  			break;
  		}
  		head = temp;
  		temp = head->next;
  	}
  }
  
  // 모든 리스트 출력
  void print_list(Node* Current)
  {
  	Current = pStart;
  	while(Current != NULL)
  	{
  		printf("%d->", Current->data);
  		Current = Current->next;
  	}
  	printf("NULL \n");
  }
  
  int main()
  {
  	for (int i = 0; i < 5; i++) {
  		addrear(i);
  		print_list(pStart);
  	}
  
  	for (int i = 0; i < 5; i++) {
  		delfornt();
  		print_list(pStart);
  	}
  
  	for (int i = 0; i < 5; i++) {
  		addfront(i);
  		print_list(pStart);
  	}
  
  	del(3);
  	print_list(pStart);
  
  	return 0;
  }
  /* 결과
  0->NULL
  0->1->NULL
  0->1->2->NULL
  0->1->2->3->NULL
  0->1->2->3->4->NULL
  1->2->3->4->NULL
  2->3->4->NULL
  3->4->NULL
  4->NULL
  NULL
  0->NULL
  1->0->NULL
  2->1->0->NULL
  3->2->1->0->NULL
  4->3->2->1->0->NULL
  4->2->1->0->NULL
  */

이중 연결리스트(Doubly linked list)에 대해 설명하시고 예제소스를 구현해보아라

• 두개의 링크 필드를 이용하여 양방향(이전 노드(previous),다음 노드(next))으로 연결 되어있다.
• 장점 : 앞,뒤로의 탐색이 가능하다. 
• 단점 : 이전 노드를 지정하기 위한 변수를 하나 더 사용해야 하기 때문에 단일 연결 리스트에 비해 메모리를 더 많이 사용한다. 또 구현이 복잡해진다. 

출처 및 참고 사이트 : https://salix97.tistory.com/283

스택(Stack)에 대해 설명하고 예제소스를 구현해보아라

• 후입선출(LIFO : Last In Fisrt Out) 방식의 자료구조
• 후입선출이란 나중에 들어간 것이 먼저 나온다는 뜻이다. 
• 배열 정수형 스택 예제
• isFull() : 스택이 가득차있는지 확인하는 함수
• isEmpty() : 스택이 비워져있는지 확인하는 함수
• push(int data) : 스택에 자료를 넣는 함수
• pop() : 스택에 있는 자료를 빼는 함수

#include <iostream>
#include <stdio.h>
#define MAX_SIZE 100

class stack
{
private:
	int nArray[MAX_SIZE];
	int index;

public:
	stack();
	bool isFull();
	bool isEmpty();
	void push(int data);
	int pop();
};

stack::stack()
{
	index = -1;
}

bool stack::isEmpty()
{
	if (index <= -1) return true;
	else			 return false;
}

bool stack::isFull()
{
	if (index >= MAX_SIZE-1) return true;
	else					 return false;

}

void stack::push(int data)
{
	if (isFull()) 
	{
		printf("꽉 찼습니다");
		return;
	}
	nArray[++index] = data;
}

int stack::pop()
{
	if (isEmpty())
	{
		printf("스택이 비었습니다");
		return -1;
	}
	return nArray[index--];
}

int main()
{
	stack st;
	int input;

	scanf_s("%d", &input);
	st.push(input);

	printf("%d", st.pop());

	return 0;
}

큐(Queue)에 대해 설명하고 예제소스를 구현해보아라

• 선입선출(FIFO : First In Fisrt Out) 방식의 자료구조
• 선입선출이란 먼저 들어간 것이 먼저 나온다는 뜻이다. (ex : 화장실 줄을 생각해보자)
• 원형큐(Circular Queue)예제
• 앞당김 작업 없이 지속적인 큐의 사용을 위해 사용
• isFull() : 큐에 가득차있는지 확인하는 함수
• isEmpty() : 큐가 비워져있는지 확인하는 함수
• enqueue(int data) : 큐에 자료를 넣는 함수
• dequeue() : 큐에 있는 자료를 빼는 함수

#include <iostream>
#include <stdio.h>
# define MAX_SIZE 5

class Queue
{
private:
	int nArray[MAX_SIZE];
	int index_front;
	int index_back;

public:
	Queue();

	bool isEmpty();
	bool isFull();
	void enqueue(int data);
	int dequeue();

};

Queue::Queue()
{
	index_front = 0;
	index_back = 0;
}

bool Queue::isEmpty()
{
	if (index_front == index_back)  return true;
	else				return false;
}

bool Queue::isFull()
{
	if ((index_back + 1)%MAX_SIZE == index_front)    return true;
	else	 					 return false;
}

void Queue::enqueue(int data)
{
	if (isFull())
	{
		printf("큐 FULL\n");
		return;
	}

	index_back = (index_back + 1) % MAX_SIZE;
	nArray[index_back] = data;

	return;
}

int Queue::dequeue()
{
	if (isEmpty()) 
	{
		printf("큐 Empty\n");
		return -1;
	}

	index_front = (index_front + 1) % MAX_SIZE;
	return nArray[index_front];
}

int main()
{
	Queue tq;
	for (int i = 1; i < 6; i++)
	{
		tq.enqueue(i);
	}

	printf("pop 한번 %d\n", tq.dequeue());
	tq.enqueue(11);

	while (!tq.isEmpty())
	{
		printf("%d\n", tq.dequeue());
	}

	printf("%d\n", tq.isFull());
	printf("%d\n", tq.isEmpty());

	return 0;
}