[자료구조 복습6] 이진 탐색 트리 (Binary Search Tree)
이진탐색트리 (Binary Search Tree)란, 기존의 이진 트리가 변형된 형태이다 . 이는 말 그대로 '탐색'을 더 효율적으로 하기 위해 설계된 자료구조로, 맨 위 노드를 기준으로 왼쪽은 맨 위 노드보다 작은 데이터가, 오른 쪽은 맨 위 노드보다 큰 데이터가 삽입된다. 또한, 모든 subtree는 이진탐색트리이므로, 모든 subtree에도 이러한 법칙이 적용된다. 그러면 이진탐색트리의 cpp 코드를 하나씩 살펴보도록 하겠다. 1. 트리 노드 타입 class BSTNode { public: int key; BSTNode* left =NULL; BSTNode* right = NULL; }; 2. BST 클래스 class BST { public: BSTNode* root = NULL; void inse..
[자료구조 복습5] 이중연결리스트로 덱(double- ended queue) 구현하기
덱 이란? 덱은 큐와 스택의 기능을 모두 갖춘 만능 리스트라고 생각하면 된다. 즉, 앞 ,뒤 모두에서 데이터가 삽입가능하고, 앞, 뒤 모두에서 데이터가 삭제가 가능한 자료구조이다. 즉 add rear 와 delete front는 큐의 성질이고, add rear 와 delete rear는 스택의 성질이라고 보면 된다. 덱은 주로 이중연결리스트로 구현이 되는데, 그 이유는 front와 rear에서 모두 삽입 , 삭제하려면 양쪽으로 링크를 가진 이중연결리스트가 편리하기 때문이다. 또한 덱은 앞,뒤에서 삭제삽입이 이루어지기 때문에, 큐처럼 head 포인터와 tail포인터를 모두 가지고 있어야한다. 덱은 앞서 봤던 큐와 스택을 짬뽕?! 해놓은 개념이라 까다롭지 않으므로 바로 소스코드를 살펴보도록 하겠다! 역시나 ..
[자료구조 복습4] 원형 큐와 연결리스트 큐 구현하기
큐 란 무엇인가? FIFO, "가장 먼저 들어온 것이 가장 먼저나가는 " 자료구조의 형태이다. 이는 영화관 매표소의 줄을 생각하면 쉽다. 가장 먼저 온 사람이 가장 먼저 티켓을 받고 줄에서 나간다! 그래서 큐는 리스트의 두군데에서 입출력을 담당한다. 스택의 경우 tail 즉 꼬리부분이 입출력을 모두 담당했지만, 큐의 경우 입력은 뒤에서! 출력은 앞에서 ! 담당한다. 그래서 각각 출력을 담당하는 부분을 front , 입력을 rear 라고 한다. 그러면 이러한 큐를 어떻게 구현하는가 ? 일단 크게 세가지의 방법이 있다. 1) 배열리스트 구현 2)원형 배열 구현 3)연결리스트 구현 1번 배열리스트 구현은 너무 쉽게 구현되기 때문에 패스하고, 2번과 3번을 구현해보도록 하겠다. 먼저 원형큐를 살펴보자! 배열을 ..
B0J 1874 스택수열
먼저 해당 문제의 로직이다 이렇게 스택의 성질을 이용해서, 스택 배열을 구현하거나, STL stack을 이용하면 비교적 쉽게 풀린다. 하지만..! 나는 '스택'이란 것 자체를 이용하지 않고 이문제를 풀어보고싶었다( ?!?) 그래서 두가지의 소스코드가 나왔다. 일단 스택을 이용한 소스코드이다. 매우간결하다 #include #include #include #include using namespace std; vectorans; int main(void) { int n; int num; cin >> n; stack s; int j = 1; for (int i = 0; i > num; if (s.empty() || s.top() < num) { //stack이 empty거나, to..