디노문경

이진 탐색 트리(binary search tree)는 자료 구조의 하나로, 그래프의 트리 구조를 사용합니다. 이진 탐색 트리에서는 각 노드에 데이터가 저장됩니다. - 책 알고리즘 도감 1. 이진 탐색 트리의 구조와 특징 이 그림은 이진 탐색 트리의 예입니다. 각 노드에 적혀 있는 숫자가 데이터입니다. 여기에서는 같은 숫자는 존재하지 않는다고 가정하고 설명하겠습니다. 이진 탐색 트리는 두 가지 특징을 가지고 있습니다. 첫 번째 특징은, 모든 노드는 왼쪽 가지에 포함되는 어떤 숫자보다도 큰 숫자가 된다는 것입니다. 예를 들어, 노드 9는 그 왼쪽에 있는 가지의 모든 숫자보다 큽니다. 마찬가지로, 노드 15는 그 왼쪽 가지에 있는 어떤 숫자보다 큽니다. 두 번째 특징은, 모든 노드는 그 노드의 오른쪽 가지에 ..

힙(heap)은 그래프의 트리 구조 중 하나로, '우선순위 큐(priority queue)'를 구현할 때 사용됩니다. 우선순위 큐는 자료 구조의 하나로서 데이터를 자유롭게 추가할 수 있습니다. 반면, 데이터를 추출할 때는 최소값부터 순서대로 선택됩니다. 추가는 자유롭게 하고 추출할 때는 작은 값부터 꺼내는 것이 우선순위 큐입니다. 또한, 힙을 표현하는 트리 구조에서는 각 정점을 '노드(node)'라고 부릅니다. 힙에서는 각 노드에 데이터가 저장됩니다. - 책 알고리즘 도감 1. 기본 구조와 개념 이것은 힙의 한 예입니다. 힙의 각 노드에 적혀 있는 숫자가 저장돼 있는 데이터입니다. 이 노드들은 최대 두 개의 자식 노드를 가집니다. 그리고 트리의 모양은 데이터의 개수에 의해 정해집니다. 또, 노드는 위에서..

해시 테이블(hash table)은 자료 구조의 하나입니다. '해시 함수'와 함께 데이터 검색을 효율적으로 하기 위해 사용되는 구조입니다. - 책 알고리즘 도감 해시 테이블은 키(Key)와 값(Value)이 한 쌍을 이루는 데이터를 저장합니다. 이 예에서는 각 사람의 성별을 데이터로 저장하고 있으며, 이름을 키로, 성별을 값으로 저장하고 있습니다. 해시 테이블의 특징을 비교하기 위해 먼저 데이터를 '배열'에 저장하는 경우를 생각해 보겠습니다. 6개의 상자로 이루어진 배열을 준비해서 데이터를 저장합니다. 여기서 Ally의 성별을 알고 싶다고 가정해봅시다. Ally가 배열의 몇 번째 상자에 저장돼 있는지 모르므로 앞에서부터 차례대로 확인해야 합니다. 이 처리를 '선형 탐색'이라고 합니다. 이처럼 선형 탐색은..

큐(Queue)는 자료 구조의 하나로, 리스트, 배열, 스택과 마찬가지로 데이터를 1열로 나열한 구조입니다. 스택과 비슷하지만 큐는 추가하는 측과 삭제하는 측이 반대입니다. 큐는 '대기 행렬'이라고 불립니다. 명칭처럼 줄 서 있는 행렬을 생각하면 이해하기 쉽습니다. 행렬에서는 새롭게 온 사람이 가장 뒤에 서며, 가장 앞에 있는 사람부터 순서대로 처리됩니다. - 책 알고리즘 도감 큐에 데이터를 추가하는 작업을 '인큐(enqueue)'라고 합니다. 큐에서 데이터를 꺼내는 작업을 '디큐(dequeue)'라고 합니다. 큐와 같이 먼저 넣은 것을 먼저 꺼내는 선입선출 구조를 'First In First Out'이라고 하며, 앞글자만 따서 'FIFO'라고도 합니다. 스택과 마찬가지로 데이터를 조작할 수 있는 위치가..

스택(stack)은 자료 구조의 하나로서 데이터를 1열로 나열하지만, 서류를 쌓아 놓은 경우처럼 새롭게 추가한 데이터에만 접근할 수 있습니다. 새로운 서류가 도착하면 현재 서류 더미의 가장 위에 올려두고 서류를 꺼낼 때는 가장 위에서부터 꺼내는 것과 같습니다. - 책 알고리즘 도감 스택에 데이터를 추가하는 작업을 푸시(push)라고 합니다. 스택에서 데이터를 꺼내는 경우 가장 위, 즉 가장 최근에 추가된 데이터부터 꺼냅니다. 여기서는 'Red'가 꺼내집니다. 다시 팝(pop)을 하면 이번에는 'Green'이 꺼내집니다. 스택처럼 나중에 넣은 것을 먼저 꺼내는 후입선출 구조를 'Last in First Out'이라고 하며, 앞글자만 따서 'LIFO'라고도 합니다. 리스트나 배열과 마찬가지로 스택도 데이터를..

배열은 자료 구조의 하나로, 데이터를 1열로 나열한 것입니다. 앞 절의 리스트와는 대조적으로 데이터에 접근하기는 쉽지만 추가나 삭제에 시간이 걸립니다. 이것은 '[자료 구조] 자료 구조란?'에서 설정한 가나다순의 전화번호부와 비슷한 구조입니다. - 책 알고리즘 도감 배열에서 데이터는 연속된 메모리 영역에 순서대로 저장됩니다. 연속된 영역에 저장돼 있기 때문에 인덱스를 사용해서 메모리의 주소를 계산할 수 있습니다. 따라서 각 데이터에 바로 접근할 수 있습니다. 이것을 '임의 접근(random access)'이라고 합니다. 예를 들어, 'Red'에 접근하고 싶다고 합시다. 이 때 리스트의 경우는 앞에서부터 포인터를 따라 가야 합니다. 하지만 배열의 경우는 a[2]라고 지정하기만 하면 직접 'Red'에 접근할..

리스트(list)는 자료 구조의 하나로, 데이터를 일직선으로 나열한 형태를 가지고 있습니다. 데이터 추가나 삭제는 쉽지만, 원하는 데이터에 접근하려면 시간이 많이 걸립니다. - 책 알고리즘 도감 리스트에서는 데이터가 메모리상의 연속된 위치에 저장되지 않아도 되며, 일반적으로 떨어진 영역에 흩어져서 저장됩니다. 또한, 각 데이터에는 '포인터(pointer)'가 있으며, 다음 데이터의 메모리 위치를 가리킵니다. 흩어져 저장돼 있으므로 포인터를 처음부터 순서대로 따라가야만 원하는 데이터에 접근할 수 있습니다.(이것을 순차 접근 또는 시퀀셜 엑세스(sequential access)라고 합니다.) 예를 들어, 'Red'에 접근하고 싶은 경우는 먼저 'Blue'에 접근한 다음 포인터를 따라 'Yellow'에 가야만..

데이터의 순서나 위치 관계를 정한다. 컴퓨터 안에서 데이터는 메모리에 저장되고, 메모리는 아래 그림과 같이 상자가 일렬로 나열된 형태를 하고 있습니다. 그리고 하나의 상자 안에 하나의 데이터를 저장합니다. 이때, 데이터를 메모리에 저장할 때 데이터의 순서나 위치 관계 등을 정하는 것이 '자료 구조'입니다. 전화번호부의 자료 구조 이해하기 쉽게 전화번호부에 대해 생각해봅시다. 그리고 우리가 직접 종이에 적으면서 전화번호부를 관리한다고 해봅시다. 첫 번째 방법으로는 단순하게 아래에 이어서 추가하는 방법이 있을 것입니다. 하지만, 만약 '김짱구'라는 사람을 찾아 전화하고 싶을 때, 짱구를 찾으려면 시간이 오래 걸릴 것입니다.(전화번호부에 사람이 많이 있을수록 오래 걸리겠죠?) 두 번째 방법으로는 가나다순으로 ..