본문 바로가기

Data Structure

 (5)
우선순위 큐 : 힙(heap) 큐(Queue)는 선입선출(FIFO)로 이뤄진 자료구조다. 우선순위 큐(Priority Queue)는 큐의 출력 조건을 선입에서 특정 우선순위로 바꾼 큐를 의미한다. 다시 말해, 먼저 들어온 순서대로 내보내는 것이 아니라, 값들 간 우선순위를 설정하고, 이 우선순위가 높은 순서대로 출력하는 자료구조(큐)다. 우선순위 큐를 구현하는 포인트는 아래 2가지다.1. 데이터 간 우선순위의 기준은 무엇인가? (예 - 값의 크기 등)2. 우선순위가 높은 데이터 순으로 어떻게 정렬할 것인가? 1번 사항은 사용자의 목적에 따라 정하면 되며, 2번의 경우, 해당 큐에서 데이터를 출력하거나 입력할 때마다 고려해야 한다. 따라서, 우선순위 큐의 ADT에서는 (1) Insert, (2) delete 메서드 구현이 핵심니다.(1..
트리 : [4] 이진탐색트리 이진탐색트리(Binary Search Tree)는 탐색작업을 효율적으로 수행하기 위해 만들어진 이진트리다. ㄴ 임의의 노드 기준으로 노드의 값(Key, value)보다 (1) 작으면 왼쪽, (2) 크면 오른쪽에 저장한다.ㄴ 결과적으로 가장 왼쪽 끝의 자식노드에는 가장 작은 값을, 가장 오른쪽 끝의 자식노드에는 가장 큰 값을 갖는다.ㄴ 이진탐색트리를 중위순회하게되면, 오름차순으로 정렬된 배열을 출력한다. 이진탐색트리 연산위에서 말한 바와 같이 이진탐색트리를 구현하기 위해선 (1) 삽입, (2) 삭제연산을 구현해야 한다. (1) 삽입연산이진탐색트리가 존재할 때, 새로운 값을 삽입하고자 할 때 사용하는 방법이다. 핵심은 새롭게 삽입하고자 하는 변수(key)와 트리 내 존재하는 노드의 값을 순차적으로 비교하여 ..
트리 : [3] 이진트리 순회 순회(traversal)란, 트리의 노드들을 빠뜨리거나 중복하지 않고 모두 방문하는 탐색 방법이다. L, V, R을 각각 왼쪽으로 이동, 방문(또는 출력), 오른쪽으로 이동을 나타낸다고 할 때, 총 6가지 방법으로 L, V, R을 나열할 수 있다. 그러나 트리 : [2] 이진트리에서 언급한 바와 같이, 이진트리에는 왼쪽 $\rightarrow$ 오른쪽으로 이동이 정해져있다고 가정하기 때문에 (1) VLR, (2) LVR, (3) LRV 총 3가지 조합만 가능하다. 이 각각을 (1) 전위순회(preorder traversal), (2) 중위순회(inorder traversal), (3) 후위순회(postorder traversal)이라고 한다. 그 외 레벨순서대로 이진트리를 방문하는 (4) 레벨순회(lev..
트리 : [2] 이진트리 이진트리(Binary Tree)의 경우, 상대적으로 많이 사용하는 자료구조로 다음과 같은 특징을 갖는다. 이진트리 개념1. 모든 노드가 2개의 서브트리를 갖는 트리다. (서브트리는 공백($\emptyset$)을 포함한다.)    = 모든 노드는 최대 2개의 자식노드를 갖을 수 있다. (자식노드는 $\emptyset$을 포함한다.)    = 모든 노드의 차수(degree)는 2 이하다.2. 이진트리의 서브트리 간에는 왼쪽 $\rightarrow$ 오른쪽 순서가 존재한다. 이진트리의 성질1. 노드가 $N$개이면, 링크는 $N-1$개다. (=루트를 제외한 모든 노드는 부모노드가 존재) 2. 레벨(level)이 $i$일 때, 해당 레벨이 갖을 수 있는 최대 노드 수 : $2^{i-1}$    ㄴ 높이(heigh..
트리 : [1] 일반트리 트리(Tree)는 다음과 같은 특성을 갖는 자료구조다. (1) 위계구조를 나타내는 자료 구조다.(2) 트리의 원소(노드) 간 $1:N$의 비선형 구조를 갖는다.  트리 관련 용어 정리$\quad$ (1) 노드(Node) : 트리의 구성요소$\quad$ (2) 루트(Root) : 노드 중 부모를 갖지 않는 노드$\quad$ (3) 단말노드(Leaf) : 자식 노드를 갖지 않는 노드$\quad$ (4) 레벨(Level) : 트리의 각 층이 갖는 순서로, 루트는 0 또는 1이 된다.$\quad$ (5) 높이(Height) : 트리의 최대 레벨$\quad$ (6) 차수(Degree) : 자식 노드 수$\quad$ (7) 서브트리(Subtree) : 노드와 그 자식 노드로 이뤄진 집합$\quad$ (8) 포레스트..

티스토리툴바