Computer Science/Data Structure

개요 아직 개발을 입문하지 얼마 되지 않은 나는 알고리즘 문제를 풀다 보면, List를 언제 사용하는지, Map과 Set도 언제 사용하는지에 대해 헷갈릴 때가 많아서 정리해야지 했던걸 까먹기 전에 정리하려고 한다. List, Set, Map의 특징 정리 1. List 순서가 있고 중복을 허용하는 자료구조 순서가 있으므로 index를 통해 원소에 접근이 가능하며, 크기가 가변적이다. 1-1. LinkedList - 각 노드가 연결되어 있는 자료구조. 노드는 데이터와 포인터로 이루어져 있다. - 데이터의 삽입 및 삭제는 O(1)의 시간복잡도로 빠르지만, 데이터를 검색하는 경우 O(N)이 걸린다는 단점이 있다. 1-2. ArrayList - 배열을 기반으로 데이터를 저장하는 자료구조 - 데이터를 순차적으로 저..

트리(Tree)란? 그래프의 일종으로 정점과 간선을 이용하여 데이터의 배치 형태를 추상화한 재귀적 자료구조 마치 나무를 거꾸로 뒤집은 것과 유사해서 트리라고 한다. 트리의 구조 노드 (Node) : 트리를 구성하고 있는 기본 요소. 키나 데이터, 하위 노드에 대한 포인터를 갖고 있다. 간선 (Edge) : 노드와 노드 간의 연결선 루트 노드 (Root Node) : 부모 노드가 없는 최상위 노드 부모 노드 (Parent Node) : 자식 노드를 가진 노드 자식 노드 (Child Node) : 부모 노드의 하위 노드 형제 노드 (Sibling Node) : 같은 부모 노드를 가지는 노드 외부 노드 (External Node, Outer Node) : 단말 노드, 리프 노드라고도 하며, 자식 노드가 없는 ..

그래프(Graph)란? 정점과 간선으로 이루어진 자료구조 -> 정점 간의 관계를 표현하는 조직도 (트리는 그래프의 일종) 트리와는 달리 그래프는 정점마다 간선이 없을 수도 있고 있을 수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. 그래프의 구조 정점(Vertex) : 노드(Node)라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3) 간선(Edge) : 링크(Link)라고도 하며 노드 간의 관계를 나타낸다. 인접 정점(Adjacent Vertex) : 간선에 의해 연결된 정점. (위에서 0과 1은 인접 정점) 단순 경로(Simple-Path) : 경로 중 반복되는 정점이 없는 것 / 같은 간선을 지나가지 않는 경로. (0->3->2->1) 차수(Degree) : 무방향 그래..

해시 테이블(Hash Table)이란? 대량의 정보를 저장하고 특정 요소를 효율적으로 검색할 수 있는 데이터 구조. 순서와 무관하게 해시함수를 사용하여 key를 해시값으로 매핑하고, 해당 해시값을 주소 삼아 value를 함께 저장하는 구조. key-value 쌍으로 묶인 자료구조라고 보면 된다. 예를 들면, 해시는 전화번호부와 같아서 전화번호를 몰라서 전화번호부를 이용할 때, 이름이라는 key로 전화번호라는 value를 찾는 거처럼 이해하면 쉽다. 또한 해시는 모든 데이터 타입으로 접근이 가능하다. // HashMap이라는 배열에 "A" 인덱스를 가진 value true가 있다. HashMap.put("A", true); -> HashMap["A"] = true; 해시 테이블의 구조 key 고유한 값, ..

연결리스트(Linked List)란? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 노드에 있는 포인터는 이전이나 다음 노드를 연결하는 역할이다. 늘어선 노드의 중간지점에도 추가 및 삭제가 O(1)의 시간이 걸린다는 장점이 있으나 중간지점의 데이터를 검색하려면 처음부터 탐색을 해야 하기 때문에 O(n)의 시간이 걸리는 단점이 있다. 연결리스트의 구조 연결리스트의 노드는 데이터와 포인터로 구성되어있다. 포인터는 이전이나 다음 노드의 주소를 값으로 가지고 있다. 노드의 시작점을 Head, 끝점을 Tail이라 부른다. 연결리스트의 종류 1. 단일 연결리스트(Singly LinkedList) : 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인..