3-Elementary Data Structure

이 챕터에서는 알고리즘 구현을 위해 이용되는 자료구조들 중 내가 잘 모르는 것에 대해서만 알아본다.

 

(1) Stack과 Queue

쉽고 대충 알고 있으니까 안 다룸. array implementation과 linked list implementation둘다 가능. head와 tail정하는 것도신경써서 해야한다는 점만 유의하자. 근데 재미있어 보이는 문제가 있어서 소개한다. 사실 학교에서 자료구조 중간고사때 나왔던 문제 같은데 틀렸다. 근데 여기서 보니까 화가나서 열심히 풀어봤다. 그냥 발상 문제인 것 같다.

 

재밌는 문제: 두 개의 Stack을 써서 Queue를 만들고 Enqueue와 Dequeue의 Time Complexity를 분석하시오.

 

Stack과 queue는 in과 out이 그 순서가 완전히 반대니까 그걸 구현해줘야 한다. 따라서 다음과 같이 구현해보자.

1) Instack과 Outstack이라는 두 Stack을 만든다.

2) push할 때 item은 무조건 Instack에 넣는다.

3) Pop은 다음과 같이 한다. 

*Outstack에 무언가가 없는 경우

--> InStack에 있는 요소를 거꾸로 뒤집어 Outstack에 넣는다.

다음 그림과 같은 과정이라고 보면 될 것 같다.

이러면 맨 첨에 들어온 1부터 나갈 준비가 된다. 만약 OutStack에 뭔가 있다면 그냥 그것을 pop하면 된다.

코드는 그래서 다음과 같다.

#include<iostream>
#include<stack>
using namespace std;

template<class T>
class PrivateQueue {
private:
	stack<T> inqueue;
	stack<T> outqueue;

public:
	void enqueue(T item) {
		inqueue.push(item);
	}
	T dequeue() {
		if (outqueue.empty()) 
			while (!inqueue.empty()) { //inqueue에 뭐가 차있으면
				outqueue.push(inqueue.top());
				inqueue.pop();
			}
		T temp = outqueue.top();
		outqueue.pop();
		return temp;
	}
};

int main() {
	PrivateQueue<int> temp;
	for (int i = 0; i < 10; i++) {
		temp.enqueue(i);
	}
	for (int i = 0; i < 10; i++) {
		cout << temp.dequeue() << " ";
	}
	cout << endl;
	return 0;
}

 Time complexity는 상황에 따라 달라지니까 Average를 생각해보자. 

Push는 당연히 O(1)이다. 뭐 검사할 필요도 없고 걍 넣으면 되니까

Pop이 상황에 따라 달라진다. OutStack에 뭔가 있을 때는 걍 O(1)인데 없으면 Instack에 있는걸 모두 pop해야 하니까..

n개를 push하고 n개를 pop하는 상황을 생각해보자.

pop을 하는데 걸리는 총 시간은 맨 처음 Stack에서 꺼내는 n time외에는 전부 const하다. 굳이 따지면 2n-1정도 될 것이다. 근데 이걸 n번하니까 Average는 const한 O(1)이 될 것이다. 

그래서 이렇게 구현하면 Time Complexity도 훌륭하게 나오는 것 같다.

 

(2) Linked List & DLL

이것도 구현은 쉽게 된다.

문제는 Time complexity를 잘 알아야 앞으로 알고리즘을 구현할 때 도움이 될 것이니까 핵심적인 연산에 대한 Complexity만 좀 보자.

Linked list에서 핵심적인 연산은 다음과 같다.

Search, Insert, Delete 정도?

1) Search

정렬이나 그런게 안 된 List면 당연히 O(n)

2) Insert와 Delete

주어진 조건에 따라 달라짐.

 

(3) Tree

Tree는 종류도 다양하고 구현 방법도 array implementation과 linked list implementation이 모두 가능하다. 책에서는 linked list tree의 구현을 다루고 있는데 Heap같은 것을 구현할 때는 array based로도 많이 구현한다. 뭐 그리고 Tree의 recursive한 정의를 제대로 알 필요는 없는 것 같다. 그냥 상식적으로 어떤 구존지만 알면 될 것 같다. 물론 complete binary tree, full binary tree등의 terminology는 알아야 할 것 같다. 여기는 알고리즘 공부하면서 필요해지면 채우자

 

(4) Hash

필요할 때 채우자