땡땡

문제 설명

2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT

입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요.

제한 조건

• 2016년은 윤년입니다.
• 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다)

입출력 예

코드

string solution(int a, int b) 
{
    int month_day[] = {31,29,31,30,31,30,31,31,30,31,30,31};
    string str_day[] = {"FRI","SAT","SUN","MON","TUE","WED","THU"};
    string answer = "";
    int total_day = 0;

    for (int i = 1; i < a; i++)
    {
        total_day += month_day[i-1];
    }
    total_day += b -1;

    answer = str_day[total_day % 7];

    return answer;
}

버블정렬(Bubble sort)에 대해 설명하고 예제소스를 구현해보아라

• 오름차순으로 정렬한다.
• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 
• 구현은 간단하지만 비효율적이다.
• 시간 복잡도 : O(n^2)

void bubble_sort(int list[], int n)
{
    int temp;
    for (int i = n - 1; i > 0; i--) {
        // 0 ~ (i-1)까지 반복
        for (int j = 0; j < i; j++) {
            // j번째와 j+1번째의 요소가 크기 순이 아니면 교환
            if (list[j] < list[j + 1]) {
                temp = list[j];
                list[j] = list[j + 1];
                list[j + 1] = temp;
            }
        }
    }
}

선택정렬(Selection Sort)에 대해 설명하시고 예제소스를 구현해보아라

• 오름차순으로 정렬한다.
• 원소를 넣을 위치를 정해두고 어떤 원소를 넣을지 선택하는 알고리즘
• 첫번째 자료를 두번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫번째에 놓고, 두번째 자료를 세번재 자료부터 마지막 자료까지 차례대로 비교하여 그 중 가장 작은 값을 찾아 두번재에 놓고 ... 이러한 과정을 반복하여 정렬을 수행한다.
• 구현은 간단하지만 비효율적이다.
• 시간 복잡도 : O(n^2)

void selectionSort(int arr[], int size) {
    int minIndex;
    int temp;
    for (int i = 0; i < size - 1; i++) {

        minIndex = i;
        
        for (int j = i + 1; j < size; j++)
        {
            if (arr[j] < arr[minIndex])
            {
                minIndex = j;
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

삽입정렬(Insertion Sort)에 대해 설명하시오 예제소스를 구현해보아라

• 오름차순으로 정렬한다.
• 삽입 정렬은 두번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘이다.
• 즉, 두번째 자료는 첫번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네 번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입 될 위치를 찾는다. 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한칸 씩 뒤로 이동시킨다.
• 처음 Key값은 두 번재 자료부터 시작한다.
• 시간복잡도 : O(n^2)

void insertion_sort(int arr[], int size)
{
    int i, j;
    int key;

    for (i = 1; i < size; i++)
    {
        key = arr[i];
        for (j = i - 1; j >= 0; j--)
        {
            if (arr[j] < key) break;
            arr[j + 1] = arr[j];
        }
        arr[j + 1] = key;
    }
}

퀵 정렬(Quick Sort)에 대해 설명하시고 예제소스를 구현해보아라

• 오름차순을 기준으로 정렬한다.
• 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot)이라고 한다. 피벗을 기준으로 피벗보다 작은 요소들은 왼쪽으로, 피벗보다 큰 요소들은 오른쪽으로 옮겨진다. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 이 과정을 더 이상 분할이 불가능할 때까지 반복한다.
• 다른 정렬 알고리즘에 비해 속도가 빠르므로 사용빈도가 높다.
• 시간복잡도 : 평균 O(nlogn) 최악 O(n^2)

void swap(int *arr,int a, int b){
    int tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}
 
void quick_sort(int *arr, int start, int end)
{
    int pivot = arr[start];
    int left = start+1;
    int right = end;
 
    while(left <= right)
    {
 
        while(arr[left] < pivot)  { left++; }  //pivot보다 작은 경우는 건너뛰고 크거나 같은경우 멈춤
        while(arr[right] > pivot) { right--; } //pivot보다 큰 경우는 건너뛰고 작거나 같은경우 멈춤
 
        if(left <= right){ swap(arr, left, right); }
    }
 
    //1개로 쪼개질때 까지
    if(start < end)
    { 
        swap(arr, start, right);  	   //pivot값과 arr[right] 값 swap
 
        myQuickSort(arr, start, right-1);  //앞 부분
        myQuickSort(arr, right+1, end);    //뒷 부분
    }
 
    return;
}

[출처 및 참고 사이트]

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

https://blockdmask.tistory.com/177

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

• 정렬되어있지 않은 배열의 처음부터 끝까지 단방향으로 비교하여 원하는 데이터를 찾아내는 알고리즘이다.
• 시간복잡도 : 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;
}