Computer Science/Data Structure (8) 썸네일형 리스트형 [DS] Hashing 1. hash table hash table은 hashing을 통해서 데이터를 저장하는 데이터 구조이다. hashing은 내부적으로 hash function 을 사용하여서 key와 value를 mapping 하여 hash table에 저장하여 데이터 구조를 형성하는 것을 의미한다. hash table에 데이터의 key와 value가 mapping 되어 저장되기 때문에 탐색에서 average case에 대해서 시간 복잡도가 O(1)이 된다. collision이 발생하는 경우에는 O(1)의 시간 복잡도를 보장할 수 없다. 그렇기 때문에 hash table에서의 성능은 hash function과 collision 발생 시의 정책에 따라 달라진다. 다음 예제는 hash table의 크기가 6이고 hash fun.. [DS] Graph MST & Shortest path - 이전 글: [DS] Graph 개념과 탐색방법 3. MST (Minimum Spanning Tree) 최소 신장 트리 (MST)는 그래프의 최소 연결 트리를 의미한다. 최소 연결 트리란 edge의 weight가 최소인 spanning tree를 말한다. spanning tree는 그래프의 모든 정점을 cycle 없이 연결한 형태를 말한다. 최소 신장 트리는 N개의 정점과 N-1개의 간선으로 연결되어 있으며 가중치의 합이 신장 트리 중에 최소인 값이 되어야 하기 때문에 단순히 가장 적은 간선을 사용한다고 해서 최소 비용을 얻을 수 없다. MST를 찾는 대표적인 방법으로는 Kruskal 알고리즘과 Prim 알고리즘이 있다. 1) Kruskal algorithm greedy 한 방법으로 간선을 선택하여서 .. [DS] Graph 개념과 탐색방법 1. Graph 그래프는 비선형 자료구조로 정점(vertex, 또는 노드 node)과 정점들을 있는 간선(edge)으로 이루어져 있다. 간선은 E(u,v)로 표현할 수 있는데, 이는 vertex u 와 vertex v를 연결하는 간선이라는 뜻이다. undirected graph 에서는 (u,v)와 (v,u)가 같은 의미를 가지지만 directed graph 에서는 (u,v)와 (v,u) 이 서로 방향이 다르기 때문에 다른 간선을 의미한다. 간선은 weight, value, cost 등의 가중치를 주어서 실제 문제에 적용하기도 한다. 1) 용어 Undirected Graph: 정점과 간선의 연결관계에서 간선의 방향성이 존재하지 않는 그래프 Directed Graph: 정점과 간선의 연결관계에서 간선의 방향.. [DS] Heap 1. Heap 힙은 Tree 구조를 기반으로 한 자료구조의 일종으로 배열로 구현한 Complete Binary Tree (완전이진트리) 구조로 이루어져 있다. 힙은 root 노드에 위치하는 값의 성질에 따라 max heap과 min heap 두가지로 나뉜다. 1) max heap: 각 노드의 값이 해당 child 노드들의 값보다 큰 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 큰 값을 가진다. 2) min heap: 각 노드의 값이 해당 child 노드들의 값보다 작은 값을 가지는 완전 이진 트리. 루트노드가 트리에서 가장 작은 값을 가진다. 2. 배열을 통한 구현 heap을 배열로 구현하게 되면 root 노드의 인덱스가 0이 되고, 뒤이어서 나머지 노드들의 값이 저장된다. 이때 heap은 완.. [DS] Tree & Binary Tree 1. Tree 트리는 비선형 자료구조로 부모와 자녀로 이루어진 계층적 관계를 가진 자료구조이다. 1) 용어 - Node: 노드. 트리를 구성하고 있는 각각의 요소를 의미한다. - Edge: 간선. 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미하다. - Root Node: 루트 노드. 트리 구조에서 최상위에 있는 노드 (뿌리)를 의미한다. - Terminal Node (leaf Node): 단말 노드. 하위에 다른 노드가 연결되어 있지 않은 노드를 의미한다. - Internal Node: 내부 노드, 비단말 노드. 단말 노드를 제외한 모든 노드로 루트 노드를 포함한다. - degree: 차수. 자식 노드의 개수. - height: 높이. 트리에서 루트 노드부터 가장 깊은 리프 노드까지의 길이. -.. [DS] Stack & Queue 1. Stack 스택은 선형 자료구조의 하나로 LIFO (Last In First Out) 또는 FILO (First In Last Out)라 불리는 구조로 이루어져 있다. 데이터 삽입시에 삽입되는 순서대로 스택 안에 차곡차곡 쌓이고, 출력시에는 마지막에 삽입된 데이터부터 역순으로 출력되는 식으로 데이터가 운영된다. 수식의 계산이나 서브 함수 실행 후의 복귀 등 재귀적인 상황에서 많이 사용한다. - Stack 자바 구현 더보기 import java.util.Arrays; import java.util.EmptyStackException; public class CustomStack { private static final int DEFAULT_CAPACITY = 10; private Object[] el.. [DS] Array & Linked List 1. Array 가장 기본적인 자료구조로 메모리 상에 같은 타입의 데이터가 연속적으로 저장되어 있다. 이러한 구조는 첫번째 원소의 위치를 기본 index로 offset을 더하여 이어지는 원소들의 위치를 계산하기에 쉽다. 이때문에 array는 논리적 저장순서와 물리적 저장순서가 일치한다. 따라서 index를 통해서 원소에 랜덤하게 접근이 가능하다. 따라서 검색 time complexity 는 O(1) 이다. 검색과 달리 삭제와 삽입 등의 과정에서는 해당 원소에 접근하여 작업을 완료한 후 빈 공간에 대해서 다른 원소들을 shifting 해줘야 하는 cost가 발생하고 이 경우의 시간 복잡도는 O(N)이 된다. 그렇기 때문에 array 값의 삽입, 삭제의 Time complexity는 O(N) 이다. 2. L.. [DS] 자료구조 개념 및 종류 1. 자료구조란? 자료구조는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다. 대부분의 언어는 일정 수준의 모듈 개념을 가지고 있으며, 이는 자료구조가 검증된 구현은 감춘 채 인터페이스만을 이용하여 다양한 프로그램에서 사용되는 것을 가능하게 해준다. 2. 자료구조.. 이전 1 다음
