유제필의 개발 블로그

먼저 아래와 같은 큐 구조가 있다. 유선순위 큐의 각 요소는 우선순위를 가지고, 이들 요소의 우선순위 오름차순으로 연결된다. 이 예제에서는 낮은 값의 데이터들이 높은 우선순위를 가진다. 위 큐에서 20의 값을 넣는 과정을 살펴보면, 먼저 첫 요소부터 순서차적으로 우선순위를 비교한다. 20은 2와 17보다 크고 22보다 작으므로 17과 22사이에 삽입되어야 한다. 우선순위 큐의 제거 우선순위 큐의 제거 연산은 가장 앞 요소인 전단만 제거하면 되므로, 간단하다. 힙을 이용한 우선순위 큐 구현 방법 우선순위 큐를 구현하기 위해 힙을 이용한다. 여기서 힙(Heap)은 자유 저장소의 힙이 아닌, 힙 순서 속성(Heap Order Priority)을 만족하는 완전 이진트리를 말한다. 완전 이진 트리란 최고 깊이(잎..

요약 수식 계산을 위한 트리 구조로 후위 변환 표기식으로 트리를 구축하고, 중위 표기식으로 변환하여 사용 1개의 연산자와 2개의 피연산자를 요구함 피 연산자는 잎 노드임 연산자는 뿌리 또는 가지 노드임 뒤에서부터 역순으로 계산이 되어야 함 뒤에서부터 1개씩 토큰을 확인해 연산자인지 피연산자인지 확인 수식 트리(Experssion Tree) 수식 트리란 이름 그대로 수식을 표현하는 트리이며, 수식 이진 트리라고도 한다. 하나의 연산자가 2개의 피연산자를 취한다는 가정 아래, 수식 트리는 일반적으로 2가지의 규칙을 가진다. 피연산자는 잎 노드이다. 연산자는 뿌리 노드 또는 가지 노드이다. 예를 들어 아래와 같은 수식이 있다. (1 * 2) + (7 - 8) 피연산자 1, 2, 7, 8은 모두 잎 노드이고, ..

요약 트리 구조에서 하나의 노드가 자식 노드를 2개까지 가질 수 있는 트리 구조 포화 이진 트리와 완전 이진 트리 구조로 나뉨 높이에 따라 높이 균형 트리와 완전 높이 균형 트리 구조로 나뉨 노드 방문 순서에 따라 전위 순회, 중위 순회로 나뉨 트리 소멸 시 잎 구조부터 제거해야 하며 후위 순회 방식으로 제거해야 이진 트리(Binary Tree) 이진 트리란 일반 트리와 개념은 같지만, 하나의 노드가 자식 노드를 2개까지만 가질 수 있다는 점이 다르다. 이진 트리라는 이름도 자식을 둘만 가진다는 의미에서 붙어진 이름이다. 아래 그림이 이진 트리의 구조를 개념적으로 표현한 그림이다. 이진 트리의 종류 이진 트리의 가장 중요한 부분은 노드의 최대 차수가 2라는 사실이다. 즉, 모든 이진 트리 노드의 자식 수..

트리(Tree)란 트리는 그 이름에서 알 수 있듯이 나무를 닮은 자료구조이다. 실생활에서 이러한 구조를 많이 사용하는데, 의사 결정 트리, 스킬 트리 등 여러 방면으로 많이 사용한다. 컴퓨터 과학에서도 활용도가 매우 높다. HTML, XML 문서를 다룰 때 사용하는 DOM, PC 폴더 구조, 운영체제 파일 시스템 등도 트리 구조로 이루어져 있다. 트리의 구성 요소 트리는 크게 뿌리(Root), 가지(Branch), 잎(Leaf) 세 가지 요소로 이루어져 있다. 뿌리, 가지, 잎은 모두 똑같은 노드이지만 트리에서 어디에 위치하는지에 따라 불리는 이름이 달라진다. 뿌리는 트리 자료구조의 가장 위에 있는 노드를 가리키고, 가지는 뿌리와 잎 사이에 있는 모든 노드를 말한다. 그리고 가지의 끝에 있는(마지막) 노..

요약 링 버퍼 큐 복잡도 : O(1) 배열 큐 복잡도 : O(n) 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조인 FIFO(First In - First Out) 구조를 따름 큐에 데이터를 넣는 작업을 인큐(Enqueue), 또는 스택과 같이 푸쉬(Push)라고 함 큐에서 데이터를 꺼내는 작업을 디큐(Dequeue) 또는 스택과 같이 팝(Pop)이라고 함 데이터를 꺼내는 쪽을 프론트(Front), 데이터를 넣는 쪽을 리어(Rear)라고 함 링 버퍼는 배열의 처음과 끝이 연결되어 있는 구조로, 배열 요소를 앞쪽으로 옮기지 않아도 되어 좀 더 효율적인 구조로 사용 가능 일반 배열로 사용하는 큐로 구현 시 배열 요소를 앞쪽으로 옮겨야 하는 작업이 필요 큐(Queue)란 큐란 스택과 비슷한 자료구조로..

요약 데이터를 일시적으로 저장히기 위해 사용하는 자료구조로 한 곳에서만 입출력이 일어남 먼저 들어간 데이터는 마지막에 나오는 FIFO 구조 (First In - Last Out) 마지막에 들어간 데이터는 먼저 나오는 LIFO 구조 (Last In - First Out) 데이터를 담는 행위를 Push, 데이터를 추출하는 행위를 Pop이라고 함 중요 구조체 멤버로 저장할 메모리 공간, 현재 가리키는 위치, 최대 사이즈 3가지가 필요 스택(Stack)이란 스택은 바닥에서 부터 데이터를 쌓아 올리는 자료구조의 일종이며, 스택의 입/출력은 오로지 꼭대기에서만 이루어진다. 가장 먼저 들어간 데이터는 가장 나중에 나오는 구조이고(FILO First In - Last Out), 가장 마지막에 들어간 데이터는 가장 먼저..

환형 링크드 리스트(Circular Linked List) 요약 더블 링크드 리스트와 동일하며, 다른 점은 헤드와 테일이 연결되어 있음 테일은 자신의 nextNode로 헤드를 가리키고, 헤드는 prevNode로 테일을 가리킴 리스트의 시작과 끝을 미리 알 수 있음 환형 링크드 리스트(Circular Linked List)란 환현 링크드는 헤드와 테일이 연결되어 있는 리스트 구조를 말한다. 테일은 자신의 nextNode로 헤드를 가리키고, 헤드는 prevNode로 테일을 가리킨다. 환형 링크드 리스트의 가장 큰 장점은 리스트의 시작과 끝을 미리 알 수 있다는 부분이다. 이러한 장점으로, 더블 링크드의 삽입 함수와 같은 부분의 성능을 많이 개선할 수 있다. 또한 노드를 뒤에서 역순으로 찾아나갈 수 있는 탐색..

요약 링크드 리스트의 문제였던 탐색 문제를 개선한 링크드 리스트 자료구조 첫 데이터를 헤드, 끝 데이터를 테일, 각 데이터를 노드라고 부름 각 노드의 다음 노드 주소와 이전 노드 주소 양 방향을 관리 노드가 앞 뒤 양 방향을 다루므로 접근은 용이하나 삭제 등에서 각각 전부 삭제해 주어야 함 데이터의 접근이 어려우나, 생성, 소멸, 삭제 등은 쉬움 더블 링크드 리스트(Double Linked List)란 더블 링크드 리스트란 링크드 리스트의 탐색 기능을 개선한 자료구조이다. 기존 링크드 리스트에서 탐색을 하기 위해 헤드에서 테일 방향으로의 노드를 모두 거쳐야 했다. 이러한 불편함을 더블 링크드 리스트 구조에선 헤드 -> 테일 및 테일 -> 헤드 방향, 즉 양방향 탐색이 가능하도록 개선했다. 양방향 탐색이 ..

요약 배열의 반대 개념으로, 데이터의 크기를 유연하게 변경할 수 있음 첫 데이터를 헤드, 끝 데이터를 테일, 각 데이터를 노드라고 부름 다음 노드의 주소를 이전 노드의 저장하여 다음 노드의 주소로 접근 데이터의 접근이 어려우나, 생성, 소멸, 삭제 등은 쉬움 장점 새로운 노두의 추가, 삽입, 삭제가 쉽고 빠름. (배열은 새로운 요소를 삽입하거나 삭제를 하기 어려움) 현재 노드의 다음 노드를 얻어오는 연산에 대해 비용이 발생하지 않음 단점 다음 노드를 가리키려는 포인터 때문에 각 노드마다 추가적인 메모리가 필요함 특정 위치에 있는 노드에 접근하기 위한 비용이 크며 접근하기 까지 시간이 많이 필요함 (노드에 접근하기 위해 N - 1회의 접근이 필요함) 리스트란 리스트는 이름과 같이 목록 형태로 이루어진 데이..