Trie는 단어 집합을 나타내는 문제를 해결하기 위해 만들어진 구조이다. retrieval이란 단어에서 유래되었고 Tree 구조와 구별하기 위해서 '트라이'로 발음된다. Trie는 기본적으론 트리 데이터 구조이지만 생성 및 사용 방법 측면에서 따라야 할 몇 가지 규칙이 있다. Trie는 노드가 알파벳 문자를 저장하는 Tree와 같은 자료구조이다. 특정 방식으로 노드를 구조화하면 Tree의 분기 경로르 따라 이동하여 구조에서 단어와 문자열을 검색할 수 있다. 각 Trie는 가능한 알파벳 값에 대해 하나씩 다른 노드에 대한 링크가 있는 빈 루트 노드가 있다. Trie의 모양과 구조는 항상 연결된 노드의 집합이며 빈 루트 노드에 다시 연결된다. 주목해야 할 점은 Trie의 자식 노드 수가 가능한 총 값 수에 ..

Tree를 공부하면서 비선형 구조에 대해 공부를 했었다. 비선형 구조는 데이터가 순서를 따르지 않는다는 것이다. 적어도 배열, 링크드 리스트처럼 명백한 숫자는 아니다. 트리는 루트 노드에서 시작해서 다른 노드로 연결했었다. 그래서 하위 트리가 포함되는 재귀적인 특성을 가졌다. 트리에서는 이진 탐색 트리와 같이 모양, 순서에 따라 나눴다. 우리가 사용하기에 효율적인 트리들은 지켜야하는 규칙들이 있었다. 하지만 우리가 이 규칙을 아예 안쓴다면 어떨까? 트리의 개념에서는 안될 것이라 생각하지만 그래프의 개념에서는 다르다. 트리는 더 많은 규칙을 따라야 하는 제한된 유형의 그래프에 불과하다. 그래프와 트리의 다른 점은 트리는 루트 노드에서 자식 노드로 한 방향으로만 흐르고 루프 또는 사이클이 존재할 수 없다. ..

Heap이란? 힙은 따라야 하는 몇 가지 추가 규칙이 있는 이진 트리이다. 이 두 가지 규칙이 힙을 다른 트리 구조와 구별하는 요소를 정의하는 속성이다. 그 속성은 트리의 모양과 노드의 순서이다. 먼저 모양이다. 이진 트리가 힙이 되려면 완전 트리여야한다. 완전 트리는 트리의 마지막 level을 제외하고는 노드들이 다 채워져 있어야한다. 그리고 트리의 마지막 level에서는 항상 맨 왼쪽 노드가 먼저 채워져야한다. 순서의 규칙은 부모 노드는 자식 노드의 값보다 크거나 같아야 하거나 자식 노드의 값보다 작거나 같아야 한다. 이 두 형식의 순서에 따라서 힙이 분류된다. 최소 힙(min heap)은 루트 포함 모든 상위 노드가 하위 노드보다 값이 작거나 같은 경우이다. 결국 최소 값이 루트 노드가 되는 것이다..

나무에는 수많은 가지가 존재한다. 그리고 가지처럼 뻗어나간다는 말은 다양한 갈래로 갈 수 있다는 말이고 오늘은 이 나무를 뒤집은 Tree라는 추상 자료형에 대해 알아보자. 자료 구조를 분류하기 위해선 데이터를 저장하는 방식에 대한 부분이 있지만 그거보다 더 큰 범주에는 선형인지 비선형인지가 있다. 즉, 데이터가 구성되고 탐색되는 방식에 sequence와 order가 있는지 여부이다. 배열이나 링크드 리스트 같은 선형 데이터 구조에서 데이터는 순서가 지정되고 순서가 매우 중요하다. 순차적으로만 순회할 수 있기 때문이다. 그러나 비선형 데이터 구조도 있다. 까다롭고 다루기 어려울 수 있지만 선형 데이터 구조를 이해했다면 무리가 없을 것이다. 비선형 자료 구조는 실제로 순서를 따르지 않는다. 순서대로가 아니다..

우리가 생활함에 있어서 어떤 작업이나 요청들을 처리할때 가장 쉽게 어떤 순서로 처리할까? 예를 들어, 내가 어떤 가게의 종업원이 되었다고 생각해보자. 요리를 하시는 사장님께 주문이 들어왔음을 알리는 순서를 어떤 식으로 구성할까? 일반적으로는 그냥 들어오는 순서대로이다. Queue가 해당 방식으로 구현된다. 그렇다면 쉬운 또 다른 방식은 어떤 것이 있을까? 예를 들어, 내가 어떤 가게의 종업원이 되었다고 생각해보자. 사장님께서 요리 재료를 들고 들어오시면서 냉장고에 넣으라고 박스단위로 쌓아놓으셨다. 그럴땐 어떤 박스부터 냉장고에 넣을까? 보통은 맨위의 박스부터 냉장고에 넣는다. 그럼 맨위에 쌓인 박스는 사장님께서 제일 처음 가져온 박스일까? 아니다. 가장 마지막에 가져온 박스일 것이다. 이 경우, 가장 최..

Linked List가 뭘까? Linked List를 정말로 이해하려면 연결 목록이 어떤 유형의 자료 구조인지 알아야 한다. Linked List의 한 가지 특징은 선형 자료 구조라는 것인데, 이는 그것들이 어떻게 구성되고 가로지르는지에 대한 sequence와 order가 있다는 것이다. 예를 들어 징검다리를 생각했을때 중간 지점을 가기 위해선 처음 돌부터 해당 지점까지 순차적으로 이동해야한다. 배열, 링크드 리스트 등이 선형 자료 구조이다. 비선형 자료 구조는 항목을 순서대로 정렬할 필요가 없고 비순차적으로 탐색이 가능하다. 해시 테이블 , 트리, 그래프 등이 비선형 자료 구조에 속한다. 그렇다면 배열과 링크드 리스트의 차이점이 무엇일까? 가장 큰 차이점은 시스템에서 메모리를 사용하는 방식이다. 배열이..