Jul's 개발일지 Jul's 개발일지

트라이 자료구조란 단어나 문자를 검색할 때 사용이 됩니다. 그렇다고 Hash를 쓰면 되는데 왜 트라이 자료구조를 사용하는가? 문자열은 데이터 사이즈가 숫자에 비해 크다 1억 개의 데이터를 HashMap으로 구현한다면 어마어마한 공간이 필요할 것입니다. 메모리를 줄여 문자열 간에 중복되는 문자를 최적화하는 것은 트라이의 목적입니다. 트라이는 Key Value로 트리 자료구조를 구현하며 문자열 길이가 m일 때 O(m)의 시간복잡도를 가지게 됩니다. 아래 [그림 1]은 apple 과 banana 문자를 트라이 자료구조로 구현했을 때입니다. 만약 단어를 추가하는데 이미 존재하는 단어 일 땐 다음과 같이 T/F로 표기합니다. apple 단어가 추가되어있을 때 app을 추가하면 apple의 e와 app의 마지막 p..

세그먼트 트리에 대해 알아봅시다. 세그먼트 트리란 구간의 합을 리프 노드에 저장하는 자료구조로 O(logN) 시간 복잡도를 가지고 연결된 데이터의 구간합을 구할 수 있습니다. 데이터 : 4 9 3 8 6 9 7 9 7 9 2 3 4 8 7 가 주어 질 때 구간의 합을 구하는 방법은 다음과 같습니다. 가장 단순하게 선형적으로 구하는 방법으로 시간 복잡도 O(n)가 나올 것입니다. 좀 더 개선하면 누적 합과 같이 각 행을 처음부터 해당 칸의 합을 저장해서 O(n) 이후 O(1)으로 계산할 수 있습니다. 누적합 4 13 16 24 30 39 46 55 62 71 73 76 80 88 95와 같이 저장될 것이며 O(n) 이 걸립니다. 이후 3번째부터 12번째 데이터 합은 인덱스 12번째 인덱스 - (3-1)번째..

오늘은 자료구조 이진 탐색 트리에 대해 정리해 보겠습니다. 다음 그림과 같이 데이터를 저장하는 자료구조를 Tree라고 합니다. 각각 데이터를 저장하고 있는 것을 Node라 할 때, 위와 같이 각 Node에 두 개의 Node가 저장되는 트리를 이진 트리라고 합니다. 이때 4,5,6,7 Node처럼 맨 아래에 있는 노드를 리프 노드라 합니다. 위와 같은 트리는 포화 이진트리 (리프노드를 제외한 노드가 두개의 노드를 가지는 트리) 또는 이진 트리(모든 노드가 두개의 노드를 가짐, 단 리프노드는 왼쪽에서부터 존재해야 함)라 합니다. 이진 탐색 트리는 부모노드의 왼쪽에 부모노드보다 작은 값, 오른쪽에는 큰 값을 저장합니다. add 하는 값의 순서에 따라 시간복잡도가 최악 O(N)이지만 O(logN)으로 값을 찾을..

저번 주에 면접일정 때문에 포스팅이 늦었어요 오늘은 ArrayList, LinkedList에 이은 Doubly Linked List에 대해 알아보려고 합니다. Doubly Linked List 는 Singly Linked List (LinkedList)에서 연장된 자료구조입니다. LinkedList에서는 단방향으로 데이터가 한 방향으로만 조회가 되었습니다. 하지만 Doubly Linked List에서는 양방향으로 이전의 데이터도 조회할 수 있게 하는 자료 구조입니다. Linked List 와 Doubly Linked List 차이점에 대해 알아봅시다. 이 같이 Doubly Linked List에는 이전의 Node의 data를 가리키는 previous Node를 가지고 있어야 합니다. 다음은 Doubly ..

자료구조 연결리스트(Array)와 단일연결리스트(LinkedList)에 대해 알아보자 두 자료구조의 차이점은 index의 유무라고 말할 수 있습니다. ArrayList에는 index가 존재하고 LinkedList에는 존재하지 않는다. 그림을 통해 알아봅시다. ArrayList의 빨간 글이 index이다. index로부터 객체를 참조할 수 있습니다. 반면 LinkedList에는 index가 존재하지 않기 때문에 4번째 값을 참조하기 위해서는 0번째 객체를 타고 1번째 > 2번째 > 3번째 > 4번째 방식으로 참조할 수 있습니다. 데이터를 조회하기에는 index로 접근하는 것이 효율적입니다. 그렇다면 삽입,삭제는 어떨까? 위의 그림과 비교해보자 만약 index 2를 제거한다면 3번째부터 마지막 객체에 접근해..