블링블링 범블링

트리(Tree) 트리는 기존에 정리했던 스택과 큐와 같은 선형 자료구조가 아닌 비선형구조를 가진 자료구조다. 아래 그림과 같이 비선형구조는 데이터가 계층으로 구성되어있는 구조로 선형구조와 큰 차이를 띄고 있다. 트리 자료구조의 대표적인 예는 파일구조를 들 수 있다. 폴더안에 폴더 또는 파일이 있는 것을 떠올리면 된다. 오늘은 트리의 전체적인 개념에 대해 정리해볼 계획이다. 트리 자료구조가 지닌 특징과 구조에 대해서 알아보자. [특징] 1. Root(루트)가 존재한다.최상위에 존재하는 노드를 Root라고 정해 놓고, 계층을 나눈다. 2. Node의 개수에서 -1한 값은 트리의 간선 개수와 같다.트리는 모든 노드가 연결되어 있기 때문에 (N(노드의 개수)- 1 )간선이 존재하게 된다. 3. 높이가 H인 이진..

벡터(vector) 벡터는 배열과 비슷하다. vector stl를 사용하는 이유는 여러가지가 있겠지만 배열보다 몇가지 이점이 있기 때문에 사용한다. 물론 벡터와 배열 장단점이 있기 때문에 필요에 따라 사용하는 것이 좋다. 1. 가변배열이기 때문에 메모리를 효율적으로 사용할 수 있다. (배열과의 차이점) 기존의 배열은 크기를 정하고 선언하게 된다. 하지만 만약에 그 공간을 다 사용하지 않는 경우에는 메모리가 낭비 될 수도 있다. 물론 크게 남는게 아니라면 엄청난 낭비는 아닐 것이다. 내가 처음 벡터의 개념을 접했을 때 배열 크기에 제한을 받지 않고 데이터를 저장할 수 있어서 무한한 바구니 같다는 느낌이 들었다. 특정 기준으로 데이터집합이 필요한 경우에는 벡터를 사용한다. 2. 중간 데이터를 순차적 접근을 ..

큐(Queue) queue는 대표적인 선형 자료구조 중에 하나다. queue는 FIFO(First In First Out)성질을 가지고 있다. 먼저 들어온 데이터가 가장 먼저 나간다는 의미다.대표적으로 비유하는 것이 대기순서표이다. 먼저 온사람이 먼저 접수를 하고, 나중에 온 사람은 가장 뒤에서 기다려야 하는 것처럼 큐도 그렇다.그림과 같이 새로운 데이터는 꼬리에 들어오고 기존의 데이터는 머리 쪽부터 차곡차곡 쌓인다. 그리고 데이터를 뺄 때는 가장 먼저 들어왔던 데이터가 나가는 구조다. 나는 주로 queue는 bfs탐색을 할 때 주로 사용한다. 직접 구현보다는 STL을 사용하기 간편하기 때문에 사용하지만 직접 구현해서 쓰는 것도 해봐야할 것 같다. 배열을 이용하지 않고, 리스트를 이용해 구현을 했다. #..

스택(Stack) 스택은 선형 자료구조에서 대표적인 것 중에 하나다. 스택을 떠올리면 가장 먼저 생각하는 것은 이러한 구조의 그림이다. 바구니에 책을 차례대로 쌓고, 이 것을 꺼내려면 가장 나중에 쌓은 책을 꺼내야 한다. 많은 책에서 이 것을 LIFO(Last In First Out)라고 한다. 가장 나중에 들어 간 것이 가장 먼저 나온다는 의미다. 스택은 재귀 함수를 할 때도 많이 언급되는 자료구조이기도 하다. 스택을 구현할 때 배열을 이용해 하는 법과 리스트를 이용하는 방법이 있다. 나는 리스트로 구현을 했다. STL을 사용하지 못할 때는 이렇게 구현해서 써야하고, 개념을 이해하기 위해서는 직접 구현해보는 것이 좋은 것 같다. 나도 복습할 겸 다시 구현을 해봤다. #include #include us..

원형 연결리스트(Circular Linked List) 원형 연결리스트는 이 전에 해왔던 단일 연결리스트나 이중 연결리스트에서 끝을 처음과 연결된 리스트를 말한다. 그림 상으로는 원으로 그렸지만 실제로는 선형 연결리스트의 마지막 노드의 next 포인터를 처음으로 연결 시켜주면 된다. 원형리스트(단일 연결리스트로 표현)는 모든 포인터가 다음 노드로 연결되어있다. 이러한 cycle 구조자료의 구현이 필요할 때는 원형리스트가 유용하다. 다시 마지막에서 첫번째로 이동하지 않아도 다음 노드가 첫번째 노드를 가리키기 때문이다. [데이터 삽입]?123456789101112131415161718192021222324//삽입 void addNode(int data) { //가장 마지막에 노드를 추가한다. Node *ne..

단일 연결리스트(Singly Linked List) 단일 연결리스트란 단일 방향(포인터)을 가진 리스트를 말한다. 포인터를 이용해 다음 순서의 노드를 가리켜주고, 이를 통해 머리부터 끝까지 탐색을 돌 수 있다. ?12345678910class Node {public: int data; Node *next; Node() {} Node(int data) : data(data) { //노드를 생성할 때 매개변수 값을 data변수에 값을 대입시켜준다. this->next = NULL; // next포인터를 초기화 시켜준다. } ~Node() {}}; 단일 연결리스트의 노드의 구성은 data와 다음 노드를 가리키는 next 포인터 두 가지가 있다. 예제는 단순히 데이터를 int형 변수 하나를 사용했지만 구조체를 ..

리스트는 자주 사용되는 자료구조 중에 하나다. 노드를 생성하고, 이를 포인터를 이용해 연결 시켜준다고 해서 연결리스트(Linked List)라고 한다. 배열만큼이나 자주 사용되는 자료구조다. 배열과 링크드 리스트는 순서대로 데이터를 나열한다는 공통점이 있지만 차이점과 각각의 장점이 있기 때문에 필요에 따라 사용한다. [배열] 배열은 인덱스 번호를 가지고 있다. 때문에 원하는 데이터의 위치를 알고 있다면 빠르게 참조할 수 있다. 결과적으로 N번 째 요소의 참조를 자주 해야 하는 경우에는 배열을 사용한다. 배열의 인덱스를 통해 빠르게 원하는 데이터를 사용할 수 있다는 장점을 지닌다. [리스트] 리스트는 중간에 데이터를 삽입해야 하거나, 삭제해야하는 경우에 용이하다.보이는 것처럼 새로운 노드를 생성하고 포인터..