영벨롭 개발 일지

1. 룩업 Lookup(조회) 룩업은 다음과 같은 작업을 의미합니다. 특정 원소가 컨테이너에 있는지 확인 컨테이너에서 특정 키(key)에 해당하는 값(value)을 찾음 2. Why Hash? 선형 검색은 O(N)의 시간 복잡도를 갖습니다. 만약 데이터의 개수가 매우 많아질 경우 선형 검색은 성능면에서 매우 느리겠죠? 더 나은 방법으로 BST(이진검색트리)와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하는 것입니다. 이 경우 시간 복잡도가 O(log N)으로 줄어 선형 검색보다는 훨씬 빨라집니다. 하지만 이 방법 역시 데이터의 개수가 매우 많아질수록 시간이 매우 오래 걸립니다. 이러한 상황에서 더욱 효율적인 방법으로 해시(hash)를 사용합니다. 해시는 자료의 크기에 상관없이 모든 키의 데이터 값..

트리 vs 그래프 Tree 자료구조는 계층적 데이터를 표현하는 좋은 방법이지만, 하나의 노드에서 다른 노드로 이동하는 경로가 하나만 존재하기 때문에 원형 또는 순환적인 종속성을 표현할 수 없습니다. Graph 자료구조는 원형 속성을 사용하여 다양한 경로를 표현할 수 있습니다. 그래프의 종류 그래프는 노드(vertex) 데이터뿐만 아니라 노드 사이의 에지 데이터도 저장해야 합니다. G = (V, E) V = vertex, 노드 E = vetex의 쌍으로 표현됨(일대일 관계) 비가중 그래프(unweighted graph) 비가중 그래프는 각 노드에 다른 어떤 노드들이 연결되어 있는지에 대한 정보를 가지며 에지에 가중치를 부여하지 않습니다. 즉, 모든 에지가 동일한 값을 갖습니다. 가중 그래프(weighted..

1. 힙 Heap이란? 힙(heap)은 우선순위 큐(priority queue)라고도 부르며, 컨테이너에서 가장 작은 또는 가장 큰 원소에 빠르게 접근할 수 있는 자료구조 입니다. 연산 시간 복잡도 원소 접근 O(1) 원소 삽입 O(log N) 원소 삭제 O(log N) 원소 삽입/삭제 연산에 대해 O(log N)의 시간 복잡도를 만족하기 위해선 완전 이진 트리 구조를 사용해야 합니다. 완전 이진 트리는 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식 노드가 있고, 마지막 레벨에서는 왼쪽부터 차례대로 노드가 있는 트리입니다. 완전 이진 트리는 트리의 데이터를 배열을 이용하여 저장할 수 있습니다. 배열을 이용한 완전 이진 트리 표현은 다른 노드를 가리키는 포인터를 저장할 필요가 없기 때문에 메모리 사용..

오늘은 트리에 대해 공부하겠습니다. 본격적으로 트리에 대해 알아보기 전에, 선형 자료구조에는 배열, 연결 리스트, 스택, 큐 등이 있는데요! 선형 자료구조는 최대 두 가지 방향(순방향과 역방향)으로만 자료를 순회할 수 있습니다. 때문에 문제를 해결하기에 매우 제한적이며 복잡한 문제에는 적용할 수 없는데요. 그래서 우리는 비선형 자료구조를 사용하여 좀 더 복잡한 문제를 해결할 수 있습니다. 그 중 하나가 바로 트리입니다. 1. 트리 Tree 란? 트리는 노드와 노드 사이를 부모-자식 관계로 연결하여 계층을 구성하는 자료구조입니다. 트리의 중심이 되는 노드를 루트 노드(root node)라고 부르고, 트리 내의 연산은 이 root 노드를 통해 접근합니다. 트리 자료 구조의 연산에는 크게 검색, 삽입, 삭제가..

프로그래머는 데이터를 메모리에 저장하기 위해 여러 자료 구조를 사용할 수 있습니다. 어떠한 자료 구조를 선택하느냐에 따라 시간 복잡도(time complexity)가 결정되는데, 이것은 특정 작업을 수행하는 데 걸리는 시간을 데이터 크기에 대한 수식으로 표현하는 방식입니다. 이러한 자료 구조는 크게 연속된 자료 구조와 연결된 자료 구조가 있습니다. 연속된 자료 구조(Array) data_type arr[size]; index 0 1 2 3 ... 원소 data[0] data[1] data[2] data[3] ... 대표적인 연속된 자료 구조에는 배열(array)가 있습니다. 배열은 메모리에 배열의 크기(size)보다 더 큰 공간이 있을 때 연속적으로 할당된 기억 공간입니다. [ 배열의 특징 ] 1. in..