공부
-
AVL Tree공부/자료구조 2018. 8. 17. 23:09
BST에서 위와 같은 Skewed Tree의 경우 복잡도가 O(n)이 나오는 한계점을 해결하기 위해 AVL Tree가 고안됨. AVL 은 해당 자료구조를 만든 사람의 앞글자를 하나씩 따서 만든 것(..)AVL Tree 예시AVL TreeNot AVL Tree용어노드의 height: hbalance factor: bf (왼쪽 서브트리의 height - 오른쪽 서브트리의 hegiht)empty height: -1특징AVL 트리는 BST이면서 동시에 균형을 유지하고 있음모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하 (왼쪽과 오른쪽 서브트리의 height 계산 결과가 1, 0, -1 이외라면 해당 트리는 AVL 트리가 아님 - 만약 height가 없는 경우는 -1) 즉, 모든 노드들은 balance..
-
Binary Search Tree공부/자료구조 2018. 8. 15. 18:04
Binary Search Tree(BST - 이진검색트리) 는 비어있거나 아래의 속성을 만족하는 binary tree 입니다. 자세하게 Binary Search (이진 검색)과 Linked List를 결합한 자료구조입니다. 이진 검색의 검색능력을 유지하면서 빈번한 값의 삽입, 삭제가 가능하도록 고안되었습니다. 이진검색의 경우 검색에 소요되는 시간복잡도는 O(log₂n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. linked list의 경우 자료 입력, 삭제에 필요한 시간복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 복잡도가 발생합니다.정의각각의 모든 node 들의 key는 중복된 값이 아님 (unique)기존의 binary tree는 순서가 없지만 BST는 순서가 존재parent node..
-
Heap공부/자료구조 2018. 8. 13. 21:07
Heap은 Complete Binary Tree를 기본으로 가지는 자료구조일반적으로 array로 구현하는 것이 좋음Heap 은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨시간복잡도: O(log₂N)Heap은 다음과 같은 속성(property)를 만족함A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계가 성립종종 priority queue를 보충하는대에 사용종류max heap: root노드가 가장 큰 수min heap: root노드가 가장 작은 수Max Heap부모노드의 키가 자식노드의 키보다 항상 큼 Node Insertionmax heap에서 노드 추가는 말단의 맨 오른쪽의 leaf node에 자리를 하나 만들고 해당 노드에 값을 대입한 다음 parent node와 값을 ..
-
Binary Tree공부/자료구조 2018. 8. 1. 22:13
degree가 최대 2인 트리i번째 level에 나올 수 있는 노드의 최대 개수는 2^(i - 1)주의 할 것은 전체 tree의 노드 최대 개수 또는 i번째 level까지 전체 노드의 개수가 아닌 i번째 level만 단독으로 보고 있음.k가 tree의 depth일 때, 최대 노드의 개수는 : 2^k -1위 그림에서 2번째 level의 노드의 최대 개수는 2^(2-1) = 2개이고, depth는 2^2-1 = 3개, height는 2^3 - 1 = 7개임 binary tree에는 skewed tree, complete binary tree, full(perfect) binary tree가 있음Full (Perfect) Binary Tree마지막 레벨까지 노드가 꽉 차게 있는 트리 Complete Binar..
-
Tree공부/자료구조 2018. 7. 31. 22:04
Tree 구조 트리는 위와 같은 구조를 갖고 있습니다.용어node: 트리에서 데이터를 의미branch(link): 노드와 노드를 연결root node: 최상위 노드interior node: 자기자신 아래에 연결된 노드가 있는 형태leaf node: 자기자신 아래에 노드가 더이상 연결되어있지 않은 형태parent: child 노드들이 연결되어 있는 상위 노드child: 부모노드 아래에 연결되어 있는 노드sibling: 부모노드 아래에 존재하며 동일한 레벨에 있는 노드degree (노드의 degree): 자기자신 아래에 연결된 노드가 몇개가 있는지depth: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 branch(link)의 수level: 트리의 특정 depth를 가지는 노드의 집합height: 루트노드..
-
Stack, Queue, Circular Queue공부/자료구조 2018. 7. 30. 23:02
StackLIFO(Last-In-First-Out) - 가장 마지막에 들어온 데이터가 가장 먼저 나감 stack에서 데이터의 삽입, 삭제를 push와 pop으로 부름stack을 구현하기 위해선, 초기에 pop이 되지 않도록 array가 비어 있는지 확인하는 함수 (isEmpty)가 필요. 타입선언 언어라면 어레이의 사이즈를 정하기 때문에 어레이에 데이터가 가득 찼는지 확인하는 함수 (isFull)이 필요.QueueFIFO(First-In-First-Out) - 가장 먼저 들어온 데이터가 가장 먼저 나감 위 그림에서 f(front)는 데이터의 시작위치를 가리키고 r(rear)은 현재 입력된 데이터의 위치를 가리킴 stack과 유사하게 어레이가 비어있는지 확인하는 함수 (isEmpty)와 가득 찼는지 확인하..
-
ADT, 복잡도(시간복잡도, 공간복잡도), 빅오 분석법공부/자료구조 2018. 7. 29. 23:38
추상화(Abstraction) - 중요한 속성만 포함하는 개체.즉 가장 중요한 것에 초점을 두고 그 이외의 부가적인 것은 무시함.ADT - Abstract Data Type한 개의 특별한 데이터 타입의 데이터 표현과 그 타입의 연산을 제공하는 부 프로그램만을 포함하는 클로저이다. 한마디로 사용자에게는 연산에 대한 형식과 제약조건만 알려주고 실제로 어떻게 처리되는지는 표현하지 않는 기능타입 객체의 표현은 숨겨지고 타입의 정의에서 연산 제공타입 선언과 연산들은 단일 구문 단위에 포함자바의 클래스 타입이라 볼 수 있음 ADT에서 중요한 것은 어떻게 구현되는지는 몰라도 무엇을 하는지 알면 사용자는 만들 수 있다는 점.복잡도 (Complexity)프로그램의 실행이 얼마나 오래 걸리는가 (= time complex..
-
엔디안(Endian)이란?공부 2018. 7. 15. 01:04
엔디안이란?엔디안(Endian)은 컴퓨터의 메모리와 같은 1차원의 공간에 여러 개의 연속된 대상을 배열하는 방법을 뜻하며, 바이트를 배열하는 방법을 특히 바이트 순서(Byte order)라 합니다. 엔디안은 보통 큰 단위가 앞에 나오는 빅 엔디안(Big-endian)과 작은 단위가 앞에 나오는 리틀 엔디안(Little-endian)으로 나눌 수 있으며, 두 경우에 속하지 않거나 둘을 모두 지원하는 것을 미들 엔디안(Middle-endian)이라 부르기도 합니다. 사람이 숫자를 쓰는 방법과 같이 큰 단위의 바이트가 앞에 오는 방식이 빅 엔디안입니다. 빅 엔디안리틀 엔디안0x123412 3434 120x1a3ecd1a 3e cdcd 3e 1a16진수는 2개가 1바이트이므로 묶어서 계산합니다.장단점빅 엔디안은..
-
이진법, 16진법, 비트와바이트, 인코딩공부 2018. 7. 12. 22:43
정말정말 간단한건데 사용안할 줄 알고 대충알고 넘어갔다가 이번에 큰코를 다쳤.............16진법만 다시 정리할까 했는데 전체적인 내용을 다시 까먹지 않기 위해 비트와 관련된 알고 있는 내용까지 전부 정리합니다.이진법 (binary)컴퓨터는 이진법으로 이해를 합니다. 우리가 사용하는 수의 표현방법은 십진법입니다. 이진법에는 0 또는 1 만 존재합니다. 알다시피 십진법은 0~9까지 존재합니다.십진법 ↔ 이진법십진법에서 1은 이진법에서도 1입니다. 십진법에서 3은 이진법으로 표현하자면 11이 됩니다. 이를 다시 십진법으로 변경하자면 2^1 + 2^0 = 3 으로 성립이 됩니다. 자리 수가 n개인 이진법를 십진법로 계산하는 공식은 2^n-1 + 2^n-2 + ... + 2^1 + 2^0 이 됩니다. ..