스택(Stack)에 대해 설명하고 예제소스를 구현해보아라
- 스택은 LIFO(Last In First Out)의 원리로 동작하는 선형적인 자료구조이다. 데이터가 들어가고 나오는 입구가 하나뿐이므로 입구로 들어간 데이터가 스택에 차곡차곡 쌓여있다가 들어간 반대 순서로 나온다. 마지막에 들어간 원소가 처음에 나온다.
- 주로 계산 중에 잠시 기억해야하는 임시적인 자료를 관리하는 용도로 사용된다.
- CPU도 여러가지 정보를 저장하기 위해 스택을 사용하는데 이를 시스템 스택이라 한다.
- 다음 예제는 배열로 정수형 스택을 구현한 것이다.
#include <iostream>
int* Stack;
int Size;
int Top;
void InitStack(int aSize){
Size = aSize;
Stack = (int*)malloc(Size * sizeof(int));
Top -= 1;
}
bool Push(int data){
if (Top < Size - 1){
Top++;
Stack[Top] = data;
return true;
}else
return false;
}
int Pop(){
if (Top >= 0)
return Stack[Top--];
else
return -1;
}
void FreeStack() { free(Stack); }
void main(){
InitStack(256);
Push(7);
Push(0);
Push(6);
while (Top != -1)
printf("%d\n", Pop());
}
큐(Queue)에 대해 설명하시오 예제소스를 구현해보아라.
- 큐는 FIFO(First In First Out)의 원리대로 동작하는 자료구조이다. 동일한 자료의 집합을 다룬다는 면에 있어서는 스택과 비슷하지만, 가장 먼저 들어간 자료가 가장 늦게 나온다는 점이 다르다.
- 넣은 순서대로 자료를 꺼내가므로 순서대로 처리해야하는 자료를 임시적으로 저장하는 용도로 흔히 사용한다.
- 저장되는 자료의 타입이 동일하므로 배열 또는 연결리스트로 큐를 구현할 수 있다.
- 다음 예제는 배열로 정수형 큐를 구현한 것이다.
#include <iostream>
int *Queue;
int QSize;
int head, tail;
void InitQueue(int size){
QSize = size + 1;
Queue = (int*)malloc(QSize * sizeof(int));
head = tail = 0;
}
bool EnQueue(int data){
if ((tail + 1) % QSize == head)
return false;
Queue[tail] = data;
tail = (tail + 1) % QSize;
return true;
}
int DeQueue(){
int data;
if (head == tail)
return -1;
data = Queue[head];
head = (head + 1) % QSize;
return data;
}
void FreeQueue() { free(Queue); }
void main(){
InitQueue(10);
printf("빈 상태에서 삭제 할 때 = %d\n", DeQueue());
for (int i = 0; i < 10; i++)
EnQueue(i);
printf("가득 찬 상태에서 삽입 %s \n", EnQueue(100) ? "성공" : "실패");
for (int i = 0; i < 10; i++)
printf("%d ", DeQueue());
FreeQueue();
}
단순 연결리스트에 대해 설명하시고 예제소스를 구현해보아라
- 연결리스트는 동적배열과 같이 같은 타입의 데이터 여러 개를 저장 할 수 있는 가변 크기를 가지는 자료구조이다. 하지만 동적배열과 달리 연결리스트는 요소들이 링크에 의해 논리적으로 연결되어있어 링크를 따라가면 이전, 이후 요소들을 찾을 수 있다.
- 이러한 특징 때문에 삽입, 삭제를 할 때도 물리적인 메모리 이동없이 요소간의 링크만 조작하면 되므로 동적배열에 비해 속도가 빠르다는 차이점이 있다.
- 배열의 요소 하나는 자신이 기억할 데이터 값만을 가지는데에 비해 연결리스트의 요소인 노드는 데이터 외에 연결상태에 대한 정보인 링크를 추가로 가져야한다.
- 자기 다음의 요소가 누구인지를 스스로 기억하고 있어야 흩어져 있는 노드들의 순서를 알 수 있는데 이 연결정보를 저장하는 것이 바로 링크이다.
- 이때, 링크 하나만 가지는 것을 단순 연결리스트라고하고 두 개의 링크를 가지는 것을 이중 연결리스트라고 한다.
- 노드를 구성하는 데이터와 링크는 타입이 다르기 때문에 노드는 이형 타입의 집합인 구조체로 정의한다.
- 구조체로 정의한 노드
struct Node{
int value; // 데이터
Node *next; // 링크
};
- Value 멤버는 노드가 기억하는 정보의 실체인 데이터이다. 배열 요소 타입에 제한이 없는 것처럼 연결리스트가 저장하는 정보의 종류에도 제한이 없으므로 노드의 데이터는 임의타입, 임의개수로 정의 할 수 있다.
- 여러개의 변수들을 한꺼번에 가질수도 있고 포인터나 배열 또는 다른 구조체를 노드에 포함시키는 것도 물론 가능하다. 위 예제 코드에서는 편의상 정수값 하나만을 노드에 포함시켰다.
- Next 멤버는 다음 노드에 대한 포인터를 가지는 링크이다. Node 구조체안에 다른 Node 구조체의 번지 정보가 포함되어 있는데 자신에 대한 포인터를 멤버로 가지는 가지 참조 구조체이므로 무한대가 되지는 않는다.
- 이 포인터가 가리키는 곳을 찾아가면 다음 노드가 저장된 곳을 알 수 있다.
이중 연결리스트에 대해 설명하시고 예제소스를 구현해보아라.
순차검색에 대해 설명하시고 예제소스를 구현해보아라.
이분검색에 대해 설명하시고 예제소스를 구현해보아라.
재귀함수를 이용하여 피보나치 수열을 구현해보아라.
버블정렬에 대해 설명하시오 예제소스를 구현해보아라
선택정렬에 대해 설명하시고 예제소스를 구현해보아라
삽입정렬에 대해 설명하시오 예제소스를 구현해보아라
퀵 정렬에 대해 설명하시고 예제소스를 구현해보아라
싱글톤에 대해 설명하시고 예제소스를 구현해보아라
Vector와 List의 차이점
- 반복자의레벨
- Vector는 요소들이 인접해 있으므로 임의 접근이 가능하지만, List는 노드가 흩어져 있으므로 양방향으로만 이동이 가능히다. 이는 +n 연산을 반복자가 지원하지 않으므로 순서 값으로 요소를 엑세스하는 [n]연산자를 지원하지 않으며, at함수도 당연히 지원하지 않는다.
- List는 임의 위치를 상수 시간내에 엑세스 할 수 없으며 반드시 순회를 해야만 원하는 요소를 찾을 수 있다. 임의접근 방복자를 요구하는 sort나 binary_search 알고리즘은 List에서 사용할 수 없다.
- 삽입 삭제 속도
- List는 각 요소들이 노드로 할당되어 링크에 의해 연결이 되어 있으므로 삽입 삭제시 링크만 조작해주면 된다. 요소들이 흩어져있다 하더라도 삽입, 삭제시에 메모리 이동을 할 필요가 없으므로 어느 위치에서든 상수 시간내에 삽입, 삭제가 가능하다.
- 이에 비해 벡터는 중간에서 삽입,삭제할 때 데이터를 밀고 당겨야 하므로 속도가 다소 느리다.
- 결론은 구조와 링크방식의 차이점에 기인한다. 읽기 속도가 중요하다면 벡터를 선택하는 것이 좋고, 삽입 삭제가 아주 빈번하다면 리스트가 더 나은 선택이다.
BST(Binary Search Tree)에 대해 설명하시오
- 이진탐색트리는 데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적인 구조로, 이진 트리이면서 같은 값을 갖는 노드가 없어야한다.
- 왼쪽 서브 트리에 있는 모든 데이터는 현재 노드의 값보다 작고, 오른쪽 서브 트리에 있는 모든 노드의 데이터는 현재 노드의 값보다 크다. 즉, 정렬이 되어있어야 한다.