나의 작은 valley

미완. 자료구조 다음주내로 완강내고 그다음에 뭘 하던지 하자ㅏㅏㅏ /...........

그래프란 연결 관계에 제한이 없는 트리 자료구조이다. 연결 관계에 제한이 없다는 의미는 '트리는 일방향으로 이어지지만 그래프는 양방향으로 이어지는 것이 가능하다는 점'을 의미한다. 그래프 트리에서 node라고 부르는 것을 그래프에서는 Vertex(정점)라고 부른다. 또한 Vertex간의 연결을 Edge(간선)이라고 부른다. 이러한 특징을 가지는 그래프는 주로 연결 관계를 다루는 경우에 사용된다. 가령 홍대에서 강남을 가는 지하철 노선을 보면 역들이 Vertex이고 그 사이 철도가 Edge인 것이다. 그래프는 최단거리를 구하는 등 다양한 알고리즘에 활용된다. 그래프는 다음과 같은 생김새를 가졌는데 양방향 간선인 경우는 방향표를 생략하는 경우도 있다. 트리와 달리 그래프는 언제든지 Vertex에 재접근이 가..

최대 힙은 각 노드의 값이 그 자식 노드의 값보다 크거나 같은 완전 이진 트리를 말한다. 그러면 완전 이진 트리랑 차이점은 무엇이냐? 바로 대강 만드는게 가능하다 ! 최대 힙 그러니깐 힙 자료구조에 값을 넣으면 이진 트리에 순서대로 들어간다. 이진 트리의 순서란 다음과 같다. 그러니깐 입력받은 값이 어떠하든 무조건 일단 저 순서대로 저장이 된다. 이떄 규칙이 하나 있는데 자식 노드의 값이 부모 노드보다 크면 안된다. 그래서 딱 그 경우에 대해서만 값을 바꿔준다. 그러면 1번 자리에 무조건 해당 트리의 최댓값이 위치하게 된다. 최대 힙에서 값을 Pop하면 무조건 최댓값이 나온다. 1번 자리가 Pop되면 그 자리는 그 다음 최댓값이 위치한다. 그래서 최대 힙 자료구조를 내 마음대로 정의하자면 대강 이진 트리..

균형 이진 트리란 모든 노드 간의 높이 차이가 1 이하인 이진 트리를 의미한다. 도입의 필요성 균형 이진 트리의 필요성은 무엇일까? 이진 트리 탐색은 시간 복잡도가 낮다. 그러나 항상 시간 복잡도가 낮을까? 아니다. 만약 부모 노드 값이 말도 안되게 크다면 즉 그림 1과 같은 상황이 되고 그러한 경우 시간 복잡도는 O(log n)에서 O(n)이 된다. 이런 균형이 꺠진 이진 트리를 다시 균형 잡히게 만들기 위해 AVL 기법이 등장하였다. 균형 이진 트리란 균형 이진 트리란 어떠한 노드를 부모 노드라 간주했을 때 부모 노드 기준으로 왼쪽 노드들과 오른쪽 노드들의 개수의 차이가 1 이하가 된 상태를 말한다. 가령 위의 그림1 에서 10은 균형이 잡힌 상태이다. 왼쪽 노드의 개수: 0, 오른쪽 노드의 개수: ..

이진 트리 탐색이란 이진 트리 구조의 수형도에서 특정한 값을 찾는 작업을 말한다. 이때 규칙이 있는데 시작 노드의 값이 5이면 그 다음 노드의 값이 5보다 작은 경우 왼쪽에 위치하고 5보다 큰 경우에는 오른쪽에 위치한다. 그 뒤로 오는 노드들도 이러한 규칙에 따라서 분배된다. 이렇게 분기가 나뉘기 때문에 더 낮은 시간복잡도를 가진다. 그러나 만약 시작 노드 값이 비이상적으로 크거나 작은 값이여서 이후에 들어오는 모든 노드의 값들이 한쪽 방향으로 쏠린다면 그러한 경우의 한하여 최악의 시간 복잡도를 가지게 된다. 구현 struct Item // key와 value의 쌍(pair) { K key = K();// first V value = V();// second }; struct Node { Item ite..

이진 트리란 각 노드가 최대 2개의 자식 노드를 가지는 자료구조를 말한다. 지금까지 배운 다른 자료구조들은 모두 데이터가 하나씩 연결이 되어 있었다. 가령 연결 리스트를 예로들면 한 노드가 다른 노드 1개랑만 연결이 되어있다. 이런 식으로 일렬로 연결된 자료구조를 선형(Linear) 자료구조라고 한다. 두 개의 노드와 연결된 양방향 연결 리스트라는 녀석도 있는데 그런 자료형들은 비선형 자료구조라고 하고 가장 대표적인 비선형 자료구조는 이진 트리이다. 이진 트리 구현 및 형태 시각화 현재 만드려는 트리의 모양은 다음과 같다. 미리 어느정도 구현된 이진트리 구현 코드이다. #include #include #include #include "Queue.h" #include "Stack.h" template cl..

수식을 표현하는 방법에는 infix 방식과 postfix 방식이 있다. infix 방식은 우리가 흔히 쓰는 수식을 말한다. 가령 1 * 2 + 3 / 4 이런 식이 infix 방식으로 수식을 표현한 것이다. 그러나 컴퓨터에서는 내부적으로 infix로 들어온 입력을 postfix 방식으로 변환하여 계산을 한다. infix To postfix 예시 infix: 8 / 2 - 3 + 4 * 5 - 1 * 2 = 19 postfix: 8 2 / 3 - 4 5 * + 1 2 * - = 4 3 - 4 5 * + 1 2 * - = 1 4 5 * + 1 2 * - = 1 20 + 1 2 * - = 21 1 2 * - = 21 2 - = 19 수식을 한 곳에 몰아서 놓고 수식을 만나면 넣은 두 숫자를 빼서 연산을 하고 ..

단방향 연결 리스트는 데이터 구조 중 하나로, 각 노드가 데이터 요소와 다음 노드를 가리키는 포인터로 이루어진 구조이다. 배열과는 다르게 각 원소들이 직렬이 아닌 각각 따로 떨어져있다는 점이 특징이다. 이러한 성질은 데이터를 추가/삭제하는 상황에서 시간 복잡도를 더 적게 사용하기 때문에 효율적이다. 연결 노드 다양한 기능을 추가하기 전에 우선 연결 노드 자체를 구현해보자. struct Node { int item = 0; // item = 1; first->next = nullptr; Node* second = nullptr; second = new Node; second->item = 2; second->next = nullptr; Node* third = nullptr; third = new Node..

덱 자료구조는 큐 자료구조에 여러가지 기능이 추가된 자료구조이다. 발음이랑 철자가 비슷해서 덱(deque) 자료구조를 디큐(dequeue)와 헷갈리기 쉬운데 둘은 전혀 다른 자료구조이다. 덱 자료구조 설명 핵심 함수는 총 4가지로 다음과 같다. PushFront PushBack PopFront PopBack 함수의 이름에서 알 수 있듯이 각각 순서대로 원소를 시작 부분에 추가하는 기능, 원소를 끝 부분에 추가하는 기능, 시작 부분에 원소를 Pop하는 기능, 끝 부분에 원소를 Pop하는 기능을 수행한다. 그런데 PushBack은 이전에 포스팅에서 다룬 큐 자료구조의 enqueue함수와 기능이 동일하고 popfront는 dequeue 함수와 기능이 동일한 것을 확인할 수 있다. 그렇기에 deque를 구현할 ..

큐(Queue)란 먼저 들어온 사람이 먼저 처리되는 즉 선착순으로 처리되는 구조를 가르키는 일반적인 단어이다. 주문한 음식이 나와서 A가 받으러 나갔고 그다음 음식을 받으러 B가 나갔다. 이때 가게에 새로운 사람 E가 들어왔다. E는 어느 자리에 앉아야 할까? 당장 생각해볼 수 있는 경우는 2가지이다. c와 d의 값을 복사해서 앞으로 땡기고 인덱스 2 자리에 e를 넣는 것이다. 혹은 배열의 크기를 키워서 인덱스 4 자리에 e를 넣는 것이다. 후자의 경우를 택한다면 배열의 크기가 무한정으로 계속 늘어날 것이고 앞에는 비어있는 원소들이 계속 생겨날 것이다. 전자를 택하는 것도 후자의 비하면 합리적이긴 하지만 이미 있는 공간을 놔두고 굳이 원소를 복사하여 옮기는 안해도 될 연산을 한다. E를 그냥 인덱스 0 ..