Soongle's Morgorithm

스트링 정의 스트링은 쉽게 설명하자면 문자열이다. 기존에 우리가 일반적인 배열을 통하여 구현하던 문자열보다 많은 기능을 지원한다. 스트링을 크게 두 가지로 나누어 설명할 수 있다. STL 자료구조로써의 String과 C++에서 문자열을 쉽게 다루도록 제작된 String 헤더함수로 설명할 수 있다. 따라서 String은 총 두차례에 걸쳐 포스팅하여 강의할 것이다. 이번 강의에서는 STL 자료구조로써의 String을 다룰 것이다. String Library(스트링 라이브러리) STL 자료구조로써의 String을 사용하고자 한다면, 앞에서 많이 다뤘던 다른 STL 자료구조와 마찬가지로 헤더를 선언하고 변수를 선언하여 사용하면 된다. 그에 대한 코드는 아래와 같다. #include string 변수명; // 스..

큐의 정의 큐(queue)는 스택과 마찬가지로 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝(front & back)에서만 일어난다. 스택은 한 쪽 끝에서만 자료를 넣거나(back) 뺄(front) 수 있는 선형 구조(FIFO - First In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 오래 전에 푸쉬한 자료부터 나오게 된다. Queue Library(큐 라이브러리) 스택과 마찬가지로 큐를 구현할 수 있는 방법에는 여러가지가 있다. 배열을 선언하여 만드는 방법과, 라이브러리를 호출하여 이미 구현된 큐와 그 멤버함수를 활용하는 방법이..

스택의 정의 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝(top)에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 한다. 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)로 되어 있다. 자료를 넣는 것을 '밀어 넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸시한 자료부터 나오게 된다. ex) 쌓아올린 접시, 웹 브라우저의 뒤로 가기 기능, 수식의 괄호 검사 (자료 출처 - 위키백과) Stack Library(스택 라이브러리) 스택을 구현할 수 있는 방법에는 여러가지가 있다. 배열을 선언하여 ..

벡터의 정의 벡터(std::vector)는 동적 배열 구조를 C++로 구현한 것이다. 이것은 C의 배열(빠른 랜덤 접근이 가능한)처럼 행동하지만 자동으로 배열의 크기 조절과 객체의 추가와 삭제가 가능하다. 벡터는 C++ 표준 템플릿 라이브러리 중의 하나인 템플릿 클래스이다. 어떤 타입이라도 저장할 수 있지만, 한 번에 한 타입만 저장이 가능하다. 요소에 접근하거나, 앞 또는 뒤에 요소를 추가하거나 삭제할 수 있고 크기를 알 수 있는 멤버 함수를 제공하고 있다. (일반 배열과 구동이 매우 유사하므로 따로 그림은 삽입하지 않겠다.) Vector Library(벡터 라이브러리) 벡터또한 스택과 큐와 마찬가지로 STL의 자료구조 중 하나이다. 따라서 헤더와 변수를 선언하는 것이 매우 유사하다. 벡터 헤더 선언과..

AVL 트리란, George Adelson-Velsky와 Evgenii Landis가 발표한 최초의 균형잡힌 이진트리(balanced binary tree)이다. AVL 트리 클래스를 Node구조체를 사용한 링크 표현법으로 구현하였다. AVL 트리의 가장 핵심적인 기술은 바로 회전(Rotation)이다. RR, LL, RL, LR 네 가지 경우에서의 회전을 통해 트리 전체의 좌우 균형을 맞추기 때문이다. 이렇게 균형이 맞춰진 트리는 값을 탐색할 때 최악의 경우에도 O(log n)의 시간안에 탐색을 끝낼 수 있다. 각각의 회전을 해야하는 경우는 아래와 같다 RR : 오른쪽, 오른쪽으로 치우친 경우 → 현재 노드 기준으로 왼쪽으로 회전시킨다 LL : 왼쪽, 왼쪽으로 치우친 경우 → 현재 노드 기준으로 오른쪽..

이진 탐색 트리란, 다음과 같은 특징을 갖는 이진 트리이다 모든 노드의 값은 유일하다. 왼쪽 노드의 값은 자신의 값보다 작다. 오른쪽 노드의 값은 자신의 값보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 이진 탐색 트리 클래스를 Node 구조체를 사용한 링크 표현법으로 구현하였다. 모든 함수들은 재귀로 구현하였다. #include #include using namespace std; struct Node { int data; Node* left; Node* right; }; class BinaryTree { public: BinaryTree(); ~BinaryTree(); int size(); int height(); bool search(int key); bool insert(int ite..