자료구조와 알고리즘/자료구조8 힙 힙이란? 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리 완전 이진트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고 최대, 최솟값을 찾기 위해선 O(n)이 걸림 이에 반해서 힙에 데이터를 넣고 최대 최소를 찾기위해선 O(logn)이 걸림 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용된다. 힙의 구조 힙은 최댓값을 구하기 위한 구조와 최솟값을 구하기 위한 구조로 분류할 수 있다. 힙의 조건 1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다(최대 힙) 2. 최소 힙은 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작다. 3. 완전 이진트리 .. 2020. 9. 3. 트리 1. 트리 구조 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조입니다. 실제로는 이진트리 (Binary Tree) 형태의 구조로, 탐색 알고리즘 구현을 위해 많이 사용됩니다. 2. 용어 Node : 트리에서 데이터를 저장하는 기본 요소(데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Terminal Node): Child Node가 하나도 없는 노드 Sibling.. 2020. 9. 2. 해쉬 테이블 해쉬 구조 Hash Table : 키에 데이터를 저장하는 데이터 구조 key를 통해 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 용어 해쉬 : 임의 값을 고정 길이로 변환하는 것 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수 : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값 또는 해쉬 주소 : Key를 해싱 함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성 있게 찾을 수 있음 슬롯 : 한 개의 데이터를 저장할 수 있는 공간 저장할 데이터에 대해 Key를 추출할 수 있는 별도 함수도 존재할 수 있음. 장점 - 데이터 저장/읽기 속도가 빠르다 - 해쉬는 키에 대한 데이터가 .. 2020. 9. 2. 링크드 리스트 1. Linked List의 구조 연결된 리스트이다. 배열은 순차적으로 연결된 공간에 데이터를 나열하는 반면 링크드 리스트는 물리적으로 떨어진 데이터를 포인터를 사용해 연결해 관리하는 구조이다. 2. 기본 용어 Node : 데이터 저장 단위이다 (데이터의 값, 포인터(다음 데이터의 주소)로 구성된다. Pointer : 각 노드 안에서 다음이나 , 이전 노드와의 연결정보를 가지고 있는 공간 장점 - 미리 데이터공간을 할당하지 않아도 된다. 단점 - 연결을 위한 별도 데이터 공간이 필요하므로, 저장공간 효율이 높지 않음 - 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림 - 중간 데이터 삭제 시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요 3. 더블 링크드 리스트 기본구조 이중 연결 리스.. 2020. 8. 26. 스택 데이터를 제한적으로 접근할 수 있는 구조 - 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 1. 스택 구조 스택은 LIFO (Last In, First Out) 또는 FILO(Frist In, Last Out) 데이터 관리 방식을 따름 LIFO : 마지막에 넣은 데이터를 먼저 추출하는 데이터 관리 정책 FILO : 처음에 넣은 데이터를 가장 마지막에 추출하는 데이터 관리 정책 대표적인 스택의 활용 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 주요 기능 push() : 데이터를 스택에 넣기 pop() : 데이터를 스택에서 꺼내기 스택의 장단점 장점 구조가 단순해서 , 구현이 쉽다 데이터 저장/읽는 속도가 빠르다. 단점 데이터 최대 개수를 미.. 2020. 8. 18. 큐 (Queue) 1. 큐 구조 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조입니다. FIFO(First-in, First-Out) 또는 LILO(Last-in , Last-Out) 방식으로 스택과 꺼내는 순서가 반대입니다. 2. 큐 용어 - Enqueue : 큐에 데이터를 넣는 기능 - Dequeue : 큐에서 데이터를 꺼내는 기능 3. 큐 관련 라이브러리 1) java Queue 인터페이스를 제공해주며 구현체인 LinkedList, priorityQueue, priorityBlockingQueue를 사용합니다. method - void offer(Type data) : 순차적으로 데이터를 저장합니다. - Type poll() : 가장 먼저 보관한 값을 꺼내고 반환합니다. - Type peek() : 가장 먼저.. 2020. 8. 17. 배열 데이터를 나열하고, 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 1. 배열이 왜 필요할까? - 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 - 같은 종류의 데이터를 순차적으로 저장 인덱스는 각 각의 저장공간에 번호를 새겨서 바로 데이터를 찾을 수 있도록 도와주는 번호 배열의 장점 - 데이터에 빠른 접근이 가능합니다. 배열의 단점 - 배열은 공간을 미리 설정을 해야합니다. 따라서 공간을 넘어서는 데이터를 추가하기 위해선 새로운 배열을 만들어야 합니다. - 배열은 데이터의 추가/삭제에 대해서 많은 비용이 발생합니다. 2020. 8. 17. 자료구조 자료구조는 무엇일까? 우리는 수많은 데이터들을 다룬다. 이러한 데이터를 구조적으로 표현하는 방식입니다. 어떻게 표현한다는 걸까? 데이터들을 효율적으로 메모리에 배치한 뒤 저장하여 관리까지 하기 위함입니다. 데이터마다 적절한 자료구조가 다르며 자료구조의 사용은 메모리의 사용 용량을 절약해주며 실행시간까지 단축시켜줄 수 있습니다. 구조적이라는 것은 뭘까? 데이터 값의 모임, 데이터 간의 관계 그리고 데이터에 적용할 수 있는 함수나 명령체계 등을 이야기합니다. 즉 이러한 데이터들을 현실에서 우리가 나열하듯이 컴퓨터로 표현 가능한 형태로 구조화시킨 것이 자료구조입니다. 자료구조에서는 Search 자료의 탐색, Insert 자료의 추가, delete 자료의 삭제 등이 수행됩니다. 자료구조를 선택할 때는 여러 가지.. 2020. 7. 29. 이전 1 다음
