학교 수업/자료구조
-
Trie학교 수업/자료구조 2020. 9. 9. 18:23
Trie(트라이)- 개념 : 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조- 사용 목적 : 문자열 탐색 ex) 검색어 자동완성, 사전에서 찾기, 문자열 검사- 구현 코드 예시문제 ) [프로그래머스] 자동완성https://programmers.co.kr/learn/courses/30/lessons/17685 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #include #include using namespace std; #define ALPHA 26 str..
-
자료구조 2학교 수업/자료구조 2020. 5. 17. 16:50
저번 포스팅에 이어 자료구조에 대한 설명을 하겠다. 8. heap - 최대값, 최소값을 찾아내는 연산을 쉽게 하기 위해 고안된 자료구조 - 각 node가 (key, element)로 구성 - Heap-Order와 (Almost) Complete Binary Tree조건을 만족하는 binary tree이다. * heap-order: 모든 노드에 대해 각 노드의 키값이 자식 노드의 키값보다 작지 않거나(max heap, 이때 root의 키값이 가장 크다) 자식노드의 키값보다 크지않은(min heap, root의 키값이 가장 작다)을 만족해야 한다. * last node: heap의 maximum깊이의 가장 오른쪽 노드를 의미 - heap의 연산들 (min-heap기준으로 설명) 1) 삽입 연산(insert(..
-
자료구조 1학교 수업/자료구조 2020. 5. 15. 11:45
자료구조에서 배웠던, 여러 자료들에 대해서 간략히 설명하겠다. ADT(Abstract Data Type): 컴퓨터 과학에서 자료들과 자료들에 대한 연산들을 명기한 것. 자료구조의 추상화 1. Array- 장점: 배열에서 특정 위치의 값을 찾기에 편리하다. - 단점: 배열의 크기를 넘는 값을 삽입할 경우 문제 / 배열의 중간에 삽입 or 삭제 연산 시 번거로움 발생 2. Linked List- 선형으로 연결된 노드들을 가지는 자료구조- 노드간 pointer를 이용해 list를 구현하므로 메모리에 연속적으로 값을 저장할 필요 없다.- Array list와 달리, 추가 및 삭제가 쉽지만 데이터 접근 시 최악의 경우 O(n) time 소요- 3가지로 나뉨 1) Single Linked list- 한방향으로 연결..