비선형5 [Data Structure] 비선형 - 우선순위 큐 '우선순위 큐'는 우선순위가 가장 높은 자료가 가장 먼저 꺼내지는 큐다. C++과 python은 내장 라이브러리로 우선순위 큐를 제공하지만, 자바스크립트는 직접 구현해 사용해야한다. 우선순위 큐는 보통 힙(heap)이라는 트리를 사용해서 구현한다. 힙은 가장 큰/작은 원소를 찾는 데 최적화된 형태의 이진 트리로, 힙을 사용하면 새 원소를 추가하는 연산과 가장 큰/작은 원소를 꺼내는 연산을 모두 O(lgN) 시간에 수행할 수 있다. 여기서는 가장 큰 원소를 찾는 최대 힙(max-heap)을 만들어보자. 힙의 정의 힙이 갖는 가장 중요한 규칙은 부모 노드가 가진 원소는 항상 자식 노드가 가진 원소보다 크다는 것이다. 힙에서 이 규칙은 부모 자식 관계에만 적용된다. 이 규칙에 의하면 트리의 가장 큰 원소는 루.. 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. 이전 1 다음
