본문 바로가기

📚 Computer Science/Data Structure10

[자료구조] 해시 테이블(Hash Table) 해시 테이블(Hash Table) 해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 해시함수(Hash Function)를 사용하여 변환한 값을 index로 삼음 해시 함수(Hash Function)를 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 함 대표적인 예로 파이썬의 dictionary, 루비의 Hash, 자바의 Map 등이 있음 해시 테이블의 특징 기본 연산으로는 search, insert, delete가 있음 순차적으로 데이터를 저장하지 않음 key를 통해서 value를 얻을 수 있음 => 이진탐색트리나 배열에 비해 속도가 빠름 커다란 데이터를 해시해서 짧은 길이로 축약할 수 있기 때문에 데이터를 비교할 때 효율적 value는 중복 가능하.. 2023. 3. 15.

[자료구조] 우선순위 큐(Priority Queue) 우선순위 큐(Priority) 순서에 상관없이 우선수위가 높은 데이터가 먼저 나가는 형태의 자료구조 우선순위 대기열이라고도 함 대기열에서 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 제공되는 자료구조 일반적으로 힙(Heap)을 사용하여 구현 모든 항목에는 우선순위가 있음 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 큐에서 제외 두 요소의 우선순위가 같은 경우 큐의 순서에 따라 제공 우선순위 큐 구현 방법 배열, 연결리스트, 힙을 이용하여 구현 가능 구현 방법 삽입 (enqueue) 삭제 (denqueue) 배열 (unsorted array) O(1) O(N) 연결 리스트 (unsorted linked list) O(1) O(N) 정렬된 배열 (sorted array) O(N) O(1) .. 2023. 3. 13.

[자료구조] 힙(Heap) 힙(Heap) 완전 이진트리 기반의 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 우선순위 큐를 위해 만들어진 자료구조 반정렬상태(느슨한 정렬상태) 유지 큰 값이 상위에 있고 작은 값이 하위에 있는 정도 중복된 값 허용 힙의 종류 최대 힙(max heap) 부모 노드의 키 값이 자식노드의 키 값보다 크거나 같은 완전 이진트리 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값 보다 작거나 같은 이진트리 힙의 활용 시뮬레이션 시스템 네트워크 트래픽 제어 운영 체제에서의 작업 스케쥴링 수치 해석적인 계산 힙의 구현 힙을 저장하는 표준적인 자료구조는 배열 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않음 특정 위치의 노드 번호는 새로운.. 2023. 3. 13.

[자료구조] 트리(Tree) 트리(Tree) 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조 계층적인 자료를 표현하는데 이용 노드(node)들과 노드들을 연결하는 간선(edge)들로 구성 하나의 루트노드를 가짐 트리와 관련된 용어 노드(node) 트리를 구성하고 있는 기본요소 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음 간선(edge) 노드와 노드 간의 연결선 (link, branch라고도 부름) 루트 노드(root node) 부모가 없는 최상위 노드, 트리는 하나의 루트 노드만을 가짐 (A) 부모 노드(parent node) 자신 노드를 가진 노드 (H, I의 부모 노드는 D) 자식 노드(child node) 부모 노드의 하위 노드 (노드 D의 자식 노드는 H, I) 형제 노드(sibling node) 같은.. 2023. 3. 9.

[자료구조] 그래프(Graph) 그래프(Graph) 연결되어있는 원소간의 관계를 표현한 자료구조 노드(Node)와 그 노드를 연결하는 간선(Edge)을 하나로 모아 놓은 자료구조 그래프 관련 용어 정점(vertex): 위치라는 개념 (node 라고도 부름) 간선(edge): 위치 간의 관계, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프에 존재하는 정점의 모든 차수의 합 = 그래프의 간선 수의 2배 진입 차수(in-degree): 방향 그래프에서 외부에서 오는 간선의 수 (내차수 라고도 부름) 진출 차수(out-degree): 방향 그래픙에서 외부로 향하는 .. 2023. 3. 8.

[자료구조] Time Complexity (시간 복잡도) Time Complexity (시간 복잡도) 컴퓨터 프로그램의 입력값과 연산 수행 시간의 상관관계를 나타내는 척도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계 알고리즘의 로직이 얼마나 오랜 시간이 걸리는지 나타내는 데 사용 알고리즘의 로직을 코드로 구현할 때, 효율적으로 구현하기위해 고려해야 함 효율적인 알고리즘 구현: 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성 주로 빅-오 표기법을 사용해 나타냄 시간 복잡도를 표기하는 방법 Big-O(Big-Oh, 빅-오) ⇒ 상한 점근, 최악의 경우에 대해 나타내는 방법 Big-Ω(Big-Omega, 빅-오메가) ⇒ 하한 점근, 최선의 경우에 대해 나타내는 방법 Big-θ(Big-Theta, 빅-세타) ⇒ 빅 오와 빅 오메가의 공통부.. 2023. 3. 7.

이전 1 2 다음

티스토리툴바