Angievelopment

Heap 개념 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 우선순위 큐를 구현하기 위하여 만들어진 자료구조 우선순위 큐 우선순위의 개념을 큐에 도입한 자료구조. 데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다. 이용사례 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석적인 계산 반정렬 상태(느슨한 정렬 상태) 를 유지한다. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 - 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값..

해시 정의 데이터를 저장할 위치 = 인덱스를 간단한 연산으로 구하는 것 내부적으로 배열을 사용해 표를 저장함 다양한 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 것 원소의 검색, 추가/삭제도 효율적으로 수행할 수 있음 개념 원소의 개수가 13개인 배열이 있다고 하자 |인덱스|0|1|2|3|4|5|6|7|8|9|10|11|12| |---|-|-|-|-|-|-|-|-|-|-|-|-|-| |키|5|6|14|20|29|34|37|51|69|75|-|-|-| 이 배열에 원소 35를 정렬에 맞게 추가한다고 하자 키 5 6 14 20 29 34 37 51 69 75 해시값(13으로 나눈 나머지) 5 6 1 7 3 8 11 12 4 10 해시값 (hash value) : 데이터에 접근할 때 기준이 되는 값 해..

이진 검색 트리 정의 이진 탐색 + 연결 리스트 이진 탐색 탐색에 소요되는 시간 복잡도는 O(logN) 하지만 삽입, 삭제가 불가능. 연결 리스트 삽입, 삭제의 시간 복잡도: O(1) 탐색하는 시간 복잡도: O(N) 이 두 가지를 합하여 장점을 모두 얻기 위해 고안된 것이 이진 탐색 트리 즉, 효율적인 탐색 능력을 가지고 자료의 삽입, 삭제도 가능하게 만드는 것이다. 조건 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다. 같은 키 값을 갖는 노드는 없다. 이진 트리의 중위 순회(inorder)로 정렬된 순서를 읽을 수 있다. 작동 원리 1. 검색 루트부터 검색을 진행한다. 이때 선택하는 현..

Tree Tree의 구성요소 Node(노드): 트리를 구성하고 있는 각각의 요소 Edge(간선): 트리에서 노드와 노드 사이를 연결하는 선 Root Node(루트 노드): 트리 구조에서 최상단에 위치한 노드. 부모가 없는 노드 Termanal Node(Leaf Node, 단말 노드): 하위에 더이상 다른 노드가 연결되어 있지 않은 노드. 자식이 없는 노드 Internal Node(내부 노드, 비단말 노드): 단말 노드를 제외한 모든 노드. 루트 노드도 포함. 레벨(level, 깊이(depth)): 루트에서 어떤 노드까지의 경로 길이(간선의 수) 트리의 높이(height): 트리의 최고 레벨 부모 노드: 자신과 연결된 상위 노드 자식 노드: 자신과 연결된 하위 노드 형제 노드: 같은 부모를 가지는 노드 크..

Stack 데이터가 입력되면 입력되는 순서대로 쌓고, 나중에 들어온 것부터 먼저 사용하는 자료구조 LIFO(Last in First Out)의 구조. 활용 프로그램을 수행할때 사용 main 프로그램 위에 실행되는 함수가 쌓여서 호출됨 시간복잡도 : O(n) 공간복잡도 : O(n) /* * @ TITLE Stack (배열로 구현한 스택) */ interface Stack{ boolean isEmpty(); boolean isFull(); void push(char item); char pop(); char peek(); void clear(); } public class ArrayStack implements Stack { private int top; private int stackSize; privat..

Array vs Linked List 비교 array linked list 검색 random access 지원 index를 통해 직접적으로 접근 가능, O(1) Sequential Access 지원 처음부터 node를 순회, O(n) 저장 논리적 저장순서와 물리적 저장순서가 일치함 모두 흩어져서 저장됨 [head, [tail]]에서 tail에 연결된 node 정보 저장 삽입, 삭제 데이터를 중간에 삽입 or 맨 앞에 삽입하는 경우 : 이후 데이터를 shift 해야함 -> O(n) 맨 앞 or 맨 뒤에 삽입 -> O(1) 중간에 삽입 : 삽입할 위치를 검색하고 삽입 -> O(n) 메모리 할당 Stack에 할당함 compile time에 할당됨 : Static Memory Allocation Heap에 할당..

목차 1. Map이란? 2. Map의 특성 3. Map의 종류 1. Map이란? key, value로 이루어진 자료구조 key와 value가 짝지어지는 걸 mapping된다고 함 2. Map의 특성 key의 중복이 허용되지 않는다 value는 중복이 혀용된다 key, value 중 하나만 저장하지 않는다 배열과 같이 순서보다 정의된 key로 상응하는(mapping)되는 데이터를 찾고 저장하는 데 유용 3. Map의 종류 (JAVA) HashMap key, value의 쌍으로 구성된 일반적인 Map 순서 보장되지 않음 사용자가 위치를 결정하거나 알 수 없음 많은 양의 데이터를 검색할 때 좋은 성능을 보임 TreeMap key의 값을 이용해 순서대로 정렬하여 저장 key의 값을 이용해 탐색, 정렬을 통한 탐..

목차 1. Trie란? 2. Trie의 특성 3. Trie의 장단점 4. 구현 코드 5. 사용 예시 1. Trie란? 탐색 트리의 일종으로 동적 집합이나 연관 배열을 저장하는 데 사용됨 Digital Tree, Radix Tree, Prefix Tree라고도 불림 텍스트 자동 완성 기능과 같이 문자열을 저장하고 탐색하는 데 유용 2. Trie의 특성 이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않음 형태의 맵이다 key는 주로 문자열이다 value는 key에 해당하는 자식 노드이다. 키의 값은 자료 구조 전체에 분산된다 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다 루트 노드는 빈 문자열이며 자식 노드만 가지고 있다 문자열의 길이가 m일 때, 탐색과..