개발일기 개발일기

자료구조

• 트라이(Trie)

  자료구조 2022. 1. 4. 02:50

  트라이(Trie)란 뭔가? 간단하게 얘기하면 문자열 집합을 위한 '트리 자료 구조'다. prefix tree, digital search tree, retrieval tree 등으로 불리는 자료 구조이며, retrieval tree 에서 트라이(Trie)라는 단어가 유래했다고 알려져 있다. 이진 탐색 트리에서는 원하는 원소를 찾는데 O(logN) 만큼의 시간이 걸린다. 하지만, 원하는 원소(문자 하나)가 아닌, 문자열을 찾기 위해서는 문자열의 길이 만큼 비교를 해야하기 때문에 O(MlogN) 만큼의 시간이 걸린다(M은 문자열의 길이). 이처럼 문자열을 찾는데 기존에 있던 자료 구조로는 시간이 오래 걸리기 때문에 '더 빠른 시간 내에 문자열을 찾아낼 수 있는 자료 구조'로써 만들어 진 것이 트라이(Trie..

  Read More
• 해시(Hash)

  자료구조 2022. 1. 3. 01:18

  해시(Hash)가 뭐지? 개발을 하다보면 굉장히 자주 듣는 단어 중 하나인데, 찾아본 적이 없어서 거리감이 느껴지는 단어다. 위키피디아, 나무위키에 의하면, 해시 함수를 해시로 줄여 부르는 것이고 임의의 길이를 가진 데이터를 고정된 길이의 데이터로 매핑하는 함수를 의미한다. 예를 들어, 어떤 숫자를 10으로 나눴을 때, 나머지를 구하는 함수가 해시 함수라고 한다. 특징 해시 함수 적용해서 나온 고정된 길이의 값을 해시값(해시 코드, 해시섬, 체크섬)이라고 한다. 복잡하지 않은 알고리즘으로 구현되어, CPU와 메모리 등의 시스템 자원을 덜 소모한다. 같은 입력값에 대해서는 같은 출력값 보장. 이 출력값은 고른 범위에 균일하게 분포하는 경향이 있다. 입력값보다 출력값 범위가 좁기 때문에 같은 출력값에 대한 ..

  Read More
• 트리(Tree)

  자료구조 2021. 12. 31. 04:20

  트리(Tree)? 자료 구조의 형태가 나무(=Tree)와 닮아 트리라 이름 붙여졌다. 어떤 특성을 가지고 있길래 나무와 비슷한 구조를 띠게 되었을까? 특징을 한 번 살펴봐야겠다. 특징 노드A가 노드B를 가리킬 때 A를 부모 노드(parent node), B를 자식 노드(child node)라 한다. 자식 노드가 없는 노드를 잎 노드(leaf node)라 하고 잎 노드가 아닌 노드를 내부 노드(internal node)라 한다. 부모 노드가 없는 최상위 노드를 루트 노드(root node)라 한다. 여러 노드가 한 노드를 가리킬 수 없다. 회로(Cycle)가 없다. 즉, 자식 노드나 자식 노드의 자식 노드가 부모 노드를 가리킬 수 없다. 노드를 잇는 선은 간선(edge)라고 하며 서로 다른 노드 사이에 하..

  Read More
• 힙(Heap)

  자료구조 2021. 12. 28. 23:57

  힙(Heap)? '무엇인가를 쌓아올린 더미'라는 뜻을 가진 영단어입니다. 힙 트리를 줄여 힙이라 부릅니다. 이 의미를 잘 기억해두고, 힙이 어떤 형태와 특성을 가지고 있기에 이런 이름이 붙여졌는지 알아보겠습니다. 특징 힙의 목적은 '최대값 또는 최소값을 빠르게 찾기' 최대 힙과 최소 힙 2 종류가 있습니다. 최대 힙은 부모 노드의 값이 자식 노드 보다 항상 큰 힙이고, 최소 힙은 부모 노드의 값이 자식 노드 보다 항상 작은 힙입니다. 루트 노드에는 항상 최대값 또는 최소값이 저장되어 있어 최대값/최소값을 한 번에 찾을 수 있습니다.O(1) 시간 복잡도 최대값/최소값 검색: O(1) 삽입/삭제: O(logn) 용도 우선순위 큐(priority queue) 구현 힙 정렬(heap sort) 구현 구현 최대 ..

  Read More
• 스택(Stack)

  자료구조 2021. 12. 26. 23:06

  특징 끝에서만 접근 가능한 자료 구조. 가장 마지막에 넣은 자료부터 꺼낼 수 있습니다. 이 때문에 LIFO(Last In First Out), 후입선출 구조라고 불립니다. 함수 호출 시 콜 스택에 사용됨. 웹 페이지 히스토리, ctrl+z 로 이전 작업 취소 등에 사용됩니다. 장점 (배열로 구현할 경우)구현이 쉽습니다. 단점 맨 마지막 데이터로만 접근하고 작업할 수 있기 때문에 특정 요소를 검색, 조회하는데 불리한 구조입니다. 구현 배열(Array)로 구현 class StackByArray { constructor() { // JS 배열 메소드를 배제하기 위해 object로 구현 this.arr = {}; this.top = 0; } // 맨 마지막 데이터 확인 peek() { return this.ar..

  Read More
• 가변 배열(ArrayList)

  자료구조 2021. 12. 24. 01:06

  특징 배열의 장점인 index 조회를 사용하기 위해 크기 고정의 약점을 극복한 자료 구조 크기 제한에 걸릴 때, 메모리 공간 확보 + 기존 데이터 이관 작업을 별도로 해줄 필요 없음 구현 package arraylist.implementation; import java.util.ListIterator; public class ArrayList { // private 은 비공개 접근자 private int size = 0; private Object[] elementData = new Object[100]; public boolean addFirst(Object element) { return add(0, element); } public boolean addLast(Object element) { ele..

  Read More
• 연결리스트(Linked List)

  자료구조 2021. 12. 22. 02:31

  특징 선형구조(하나의 자료 뒤에 하나의 자료만 존재한다, 데이터가 순차적으로 나열된 형태) 파편화된 메모리 공간 활용 가능 데이터와 다음 노드로의 연결 정보로 구성된 노드들의 집합으로 이루어진 자료구조 배열 크기가 제한되어 있지 않다. 단일, 이중, 원형 연결 리스트의 3가지 종류가 존재합니다. 장점 요소의 삽입과 제거가 효율적입니다. 요소들의 메모리 공간이 연속적이지 않기 때문에 삽입, 제거 후의 메모리 재배치가 필요하지 않기 때문입니다. 배열의 크기가 동적입니다. 단점 index로 한 번에 요소에 접근하는 것이 불가능합니다. 첫 번째 노드부터 순차적으로 접근해야 합니다. 다음 노드로의 연결 정보 때문에, 배열보다 많은 메모리 공간을 필요로 합니다. 시간복잡도 단방향 연결리스트 조회(인덱스를 통한 접근..

  Read More
• 배열(Array)

  자료구조 2021. 12. 21. 22:24

  개요 index(번호)와 그에 대응하는 데이터로 이루어진 순차적인 자료구조 특징 일반적인 배열(다른 프로그래밍 언어의 배열) 동일한 크기의 메모리 공간이 빈틈없이 연속적으로 나열된 자료 구조 크기가 고정 배열의 요소는 같은 타입이며, 연속적으로 인접 물리적으로도 즉, 메모리 상에서도 연속적으로, 순차적으로 저장된다. 자바스크립트의 배열 각 요소를 위한 메모리 공간의 크기는 동일하지 않아도 된다. 각 메모리 공간은 연속적으로 이어지지 않아도 된다. (희소 배열, sparse array) 일반적인 배열의 동작을 흉내내어 만든 특수 객체 장점 일반 배열 임의의 요소로 접근하는 과정(random access)이 매우 빠르고 효율적이다. index를 통해 단 한번의 연산으로 접근 가능하기 때문이다. 조회가 많은 ..

  Read More