Computer Science/Data Structures (5) 썸네일형 리스트형 트라이 ‘트라이’는 기본적으로 ‘트리’ 형태의 자료 구조입니다. 특이한 점은 각 노드가 ‘배열’로 이루어져있다는 것입니다. 예를 들어 영어 알파벳으로 이루어진 문자열 값을 저장한다고 한다면 이 노드는 a부터 z까지의 값을 가지는 배열이 됩니다. 그리고 배열의 각 요소, 즉 알파벳은 다음 층의 노드(a-z 배열)를 가리킵니다. 아래 그림과 같이 Hermione, Harry, Hagrid 세 문자열을 트라이에 저장해보겠습니다. 루트 노드를 시작으로 각 화살표가 가리키는 알파벳을 따라가면서 노드를 이어주면 됩니다. 위와 같은 트라이에서 값을 검색하는데 걸리는 시간은 ‘문자열의 길이’에 의해 한정됩니다. 단순히 문자열의 각 문자를 보며 트리를 탐색해나가기만 하면 되니까요. 일반적인 영어 이름의 길이를 n이라고 했을 때.. 해시 테이블 해시 테이블은 ‘연결 리스트의 배열’입니다. 여러 값들을 몇 개의 바구니에 나눠 담는 상황을 생각해 봅시다. 각 값들은 ‘해시 함수’라는 맞춤형 함수를 통해서 어떤 바구니에 담기는 지가 결정 됩니다. 각 바구니에 담기는 값들은 그 바구니에서 새롭게 정의되는 연결 리스트로 이어집니다. 이와 같이 연결 리스트가 담긴 바구니가 여러개 있는 것이 ‘연결 리스트의 배열’, 즉 ‘해시 테이블’이 됩니다. 쉬운 예로 아래 그림과 같이 사람의 이름이 해시 테이블에 저장되며, 해시 함수는 ‘이름의 가장 첫 글자’인 경우를 생각해 보겠습니다. 그 경우 알파벳 개수에 해당하는 총 26개의 포인터들이 있을 수 있으며, 각 포인터는 그 알파벳을 시작으로 하는 이름들을 저장하는 연결 리스트를 가리키게 됩니다. 만약 해시 함수가 .. 연결 리스트: 트리 트리는 연결리스트를 기반으로 한 새로운 데이터 구조입니다. 연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있습니다. 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 됩니다. 아래 그림은 트리의 한 예입니다. 나무가 거꾸로 뒤집혀 있는 형태를 생각하면 됩니다. 가장 높은 층에서 트리가 시작되는 노드를 ‘루트’라고 합니다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 합니다. 위 그림에 묘사된 트리는 구체적으로 ‘이진 검색 트리’ 입니다. 각 노드가 구성되어 있는 구조를 살펴보면 일정한 규칙을 알 수 있습니다. 먼저 하나의 노드는 두 .. 연결 리스트와 배열의 장단점 배열과 비교해서 연결 리스트는 새로운 값을 추가할 때 다시 메모리를 할당하지 않아도 된다는 장점이 있습니다. 하지만 이런 유동적인 구조는 그 대가가 따릅니다. 구조가 정적인 배열과 달리 연결 리스트에서는 임의 접근이 불가능합니다. 연결 리스트에 값을 추가하거나 검색하는 경우를 생각해 봅시다. 이를 위해서는 해당하는 위치까지 연결 리스트의 각 node들을 따라 이동해야 합니다. 따라서 연결 리스트의 크기가 n 일때 그 실행 시간은 O(n)이 됩니다. 배열의 경우 임의 접근이 가능하기 때문에 (정렬 되어 있는 경우) 이진 검색을 이용하면 O(log n)의 실행 시간이 소요 되는 것에 비해서 다소 불리합니다. https://www.boostcourse.org/cs112/lecture/119040?isDesc=.. 데이터 구조의 개념과 연결 리스트 컴퓨터 안의 메모리는 마치 사물함과 같은 구조입니다. 우리가 사용하고자 하는 사물함의 개수를 한 번 정한 이후에는, 공간이 모자란다고 해서 주변의 사물함을 마음대로 더 사용할 수는 없습니다. 이미 다른 목적으로 사용되고 있을 수도 있기 때문이죠. 데이터 구조는 우리가 컴퓨터 메모리를 더 효율적으로 관리하기 위해 새로 정의하는 구조체입니다. 일종의 메모리 레이아웃, 또는 지도라고 생각할 수 있습니다. 이번 강의에서는 데이터 구조중 하나인 연결 리스트에 대해 알아보겠습니다. 배열에서는 각 인덱스의 값이 메모리상에서 연이어 저장되어 있습니다. 하지만 꼭 그럴 필요가 있을까요? 각 값이 메모리상의 여러 군데 나뉘어져 있다고 하더라도 바로 다음 값의 메모리 주소만 기억하고 있다면 여전히 값을 연이어서 읽어들일 수.. 이전 1 다음
