[Basic] Data/Data Structure11 [Data Structure] 비선형 - 우선순위 큐 '우선순위 큐'는 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 큐다. C++과 python은 내장 라이브러리로 우선순위 큐를 제공하지만, 자바스크립트는 직접 구현해 사용해야한다. 우선순위 큐는 보통 힙(heap)이라는 트리를 사용해서 구현한다. 힙은 가장 큰/작은 원소를 찾는 데 최적화된 형태의 이진 트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰/작은 원소를 꺼내는 연산을 모두 O(lgN) 시간에 수행할 수 있다. 여기서는 가장 큰 원소를 찾는 최대 힙(max-heap)을 만들어보자. 힙의 정의 힙이 갖는 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크다는 것이다. 힙에서 이 규칙은 부모 자식 관계에만 적용된다. 이 규칙에 의하면 트리의 가장 큰 원소는 루.. 2023. 3. 16. [Data Structure] 선형 자료구조 배열 배열은 가장 기초적인 선형 자료구조다. 배열의 원소들은 메모리 상의 연속된 위치에 저장된다. 이 특성 덕분에 캐시의 효율성을 극대화 할 수 있다. 캐시는 보통 메모리의 일정 영역을 저장해놓기 때문에 배열같이 연속적인 위치에 저장된 데이터의 경우 더 빠른 속도로 접근이 가능하다. 배열의 원소들은 각각 인덱스로 구분 가능하다. 주어진 인덱스에 있는 원소를 반환하거나 변경하는 동작을 O(1)에 할 수 있다. 배열은 선언할 때 배열의 크기를 지정해야 한다는 문제점을 가지고 있다. 처음 선언한 크기보다 더 많은 자료를 집어넣을 수 없다. 동적 배열 (Dynamic Array) 배열의 크기를 변경할 수 없다는 문제를 해결하기 위해 크기가 변경되는 '동적 배열'이 고안됐다. 배열의 특성을 그대로 이어받지만 추가.. 2023. 3. 16. [Data Structure] 비선형 - Heap(힙) Heap(힙) Binary Tree(이진트리) 최소 힙 : 부모의 키 값이 자식의 키 값보다 작거나 같다. 루트 노드의 키 값이 트리의 최솟값 최대 힙: 부모의 키 값이 자식의 키 값보다 크거나 같다. 루트 노드의 키 값이 트리의 최댓값 최대 힙 → 힙 정렬 알고리즘 → 우선순위 큐 2023. 2. 21. [Data Structure] 비선형 - Tree(트리) 트리 구조는 맨 위의 사진과 같이 하나의 뿌리로부터 시작되어서 가지가 여러 갈래로 뻗어있는 자료 구조를 말한다. 트리 구조가 어디서 많이 봤다고 하면 착각은 아니다. 스포츠를 좋아하는 사람이라면 많이 봤을 것이라고 생각되는 토너먼트 대진표도 트리 구조이다. 아래서부터 차례로 올라가서 가장 꼭대기까지 가는 것이 토너먼트이다. 트리구조는 반대로 위의 뿌리 노드부터 시작해서 아래로 내려가는 구조다. Tree (트리) 노드로 이루어진 비선형 자료 구조 그래프가 계층적 구조를 가진 형태 최상위 노드(루트)를 가지고 있음 상위 노드를 부모(parent) 노드, 하위 노드를 자식(child) 노드라 한다. 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 .. 2023. 2. 21. [Data Structure] 비선형 - Graph(그래프) Graph(그래프) 객체 간의 연결을 시각화한 것으로 정점(Vertex)간의 관계를 표현하는 자료구조 단순히 노드(N, node)와 그 노드를 연결한 간선을 하나로 모아놓은 자료 구조. 즉, 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조이다. nodes/vertices(노드) 사이에 edge(엣지)가 있는 collection directed(방향) 그래프는 일방통행 undirected(무방향) 그래프는 양방향 → 소셜 미디어 네트워크를 나타내는 데 사용 → 검색 엔진에 의해 웹 페이지 및 링크를 나타내는 데 사용 → GPS에서 위치와 경로를 나타내는 데 사용 그래프의 용어 정점(vertex) : 그래프를 형성하는 노드 간선(edge) : 그래프에서 노드 간의 연결 (정점 간에 '선') - 아크라.. 2023. 2. 21. [Data Structure] 비선형 - Hash Table(해시 테이블) Hash Table(해시 테이블) 해시 테이블은 '키-값'쌍으로 데이터를 저장하는 자료구조 중 하나로 빠른 검색, 빠른 삽입이 가능하다는 특징을 가진다. 해시 테이블이 빠르게 데이터에 접근할 수 있는 이유는 내부적으로 배열(버킷)을 사용해서 데이터를 저장하기 때문이다. 배열에 저장된 데이터를 데이터 고유의 인덱스로 접근하기 때문에 평균적으로 O(1)의 시간 복잡도로 검색할 수 있다. 고유 인덱스는 데이터의 키 값에 해시 함수(hash function)을 적용해 생성한다. Hash Function 적절한 해시 함수를 사용하는 것은 매우 중요하다. 각각 데이터는 데이터 고유의 인덱스를 가져야 하는데, 어설픈 해시 함수를 사용할 경우 인덱스가 많이 겹치는 경우가 발생할 수 있기 떄문이다. 이 경우를 'coll.. 2023. 2. 21. [Data Structure] 선형 - Queue(큐) Queue (큐) 스택과 반대로 먼저 저장된 것이 제일 먼저 나온다. 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다. 가장 먼저 입력된 요소를 처리하는 FIFO (First In First Out) 또는 LILO(Last-In, Last-Out) 방식. Ex) 큐 구현 class Queue { constructor() { this.storage = {}; // 여기에 담는다. this.front = 0; this.rear = 0; } size() { return Object.keys(this.storage).length; } // 큐에 데이터를 추가 할 수 있어야 한다. enqueue(element) { this.storage[this.rear] = element; this.rear += .. 2023. 2. 21. [Data Structure] 선형 - Stack(스택) Stack (스택) 순서가 보존되는 선형 데이터 구조 가장 마지막 요소(가장 최근 요소)부터 처리하는 LIFO (Last In First Out) 또는 FILO(First-In, Last-Out)데이터 관리방식을 따름 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 데이터를 제한적으로 접근할 수 있는 구조 → 실행 취소 → 수학적 표현식을 구문 분석하고 평가 → 재귀 프로그래밍에서 함수 호출을 구현 2023. 2. 21. [Data Structure] 선형 - Linked List(연결 리스트) Linked List (연결 리스트) 각 데이터 시퀀스가 순서를 가지고 연결된 순차적 구조 동적인 데이터 추가/삭제에 유리하다. 각 요소는 Node 각 Node에는 key와 다음 노드를 가리키는 포인터인 next가 포함 (참조한다) 첫 번째 요소는 Head 마지막 요소는 Tail → Alt + Tab을 사용하여 프로그램 간 전환 → 갤러리 연결 리스트의 장점 리스트 길이가 가변적이라 배열의 단점을 커버 할 수 있다. 연결 리시트의 단점 어떤 노드를 Search하거나 데이터를 변경할때 바로 찾아낼 수 없다. 사용 데이터가 자주 추가되거나 가변적으로 자주 변하게 될 프로그램이면 링크드리스트를 쓰는것이 좋고, 주로 데이터의 변경이나 탐색을 위한것이라면 배열을 쓰는것이 좋다. 2023. 2. 21. [Data Structure] 선형 - Array(배열) Array(배열) 동일한 타입의 데이터들을 저장하며, 고정된 크기를 가지고 있다. 인덱싱이 되어 있어 인덱스 번호로 데이터에 접근할 수 있다. → 배열 목록, 힙, 해시 테이블, 벡터 및 행렬과 같은 기타 데이터 구조를 구축하기 위한 빌딩 블록으로 사용 → 삽입 정렬, 빠른 정렬, 버블 정렬 및 병합 정렬과 같은 다양한 정렬 알고리즘에 사용 데이터를 나열하고, 각 데이터를 인덱스에 대응해주고 인덱스로 데이터를 접근할 수 있도록 구성된 데이터 구조 파이썬에서는 리스트 타입이 배열기능을 제공 배열이 왜 필요할까? - 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 - 같은 종류의 데이터를 순차적으로 저장 배열의 장점 - 인덱스로 인한 빠른 접근 가능 배열의 단점 - 미리 배열의 크기를 설정해줘야함으로 데.. 2023. 2. 20. 이전 1 2 다음
