👩🏻‍💻TIL13. 자료 구조 (Data Structure)

이 글은 Boostcourse 모두를 위한 컴퓨터 과학을 수강하고 위키피디아를 참고하여 작성했습니다.

Data Structure, 자료 구조란 컴퓨터 메모리를 효율적으로 관리하기 위해 정의한 자료의 구조체, 조직을 말한다. 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 해준다. 자료구조는 메모리의 레이아웃이라고 할 수 있다. 목적에 맞는 자료구조는 알고리즘의 효율성을 높여주기 때문에 중요하다.

다양한 자료 구조 중

• 배열
• 연결리스트
• 이진 탐색 트리
• 해시 테이블

를 간단하게 살펴보겠다.

📚 배열 (array)

같은 자료형으로 된 데이터를 연속적으로 저장한다.

💡 인덱스를 이용해 원하는 값에 바로 접근이 가능하다.

📚 연결리스트 (Linked list)

메모리 덩어리 여러개를 포함한 데이터구조, 노드(node)를 단위로 한다. 자료와 바로 다음 자료의 주소 (포인터)로 구성되어 있다.

단일 연결 목록 (Rune Magnussen, 위키피디아)

💡 장점

원래 있었던 메모리의 위치를 보존하면서 리스트를 추가할 수 있다.

💡 단점

배열과 같이 임의 접근이 불가하다.

📚 이진 탐색 트리 (Binary search tree)

이진검색(Binary search)와 연결리스트(Linked list)가 결합된 데이터 구조이다. 각 노드들은 일정한 층에 속하며, 다음 층의 노드들을 가리키는 포인터를 갖는다. 가장 높은 층에서 트리가 시작되는 노드를 root라고 한다.

• 각 노드에 값이 있다.
• 값들은 전순서가 있다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

💡 검색 실행 시간과 노드 삽입 시간 모두 O(log n)이다.

📚 해시테이블 (Hash table)

배열과 연결리스트가 결합된 데이터 구조이다. 각 자료들은 해시함수를 통해 어떤 바구니에 속할지 정해진다.

💡 만약 바구니에 1개의 값씩만 들어있다면 검색시간은 O(1)이다. 하지만 그렇지 않은 경우에는 단 하나의 바구니에 모든 값들이 담겨서 O(n)이 될 수도 있다.

일반적으로는 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에 거의 O(1)에 가깝다고 볼 수 있다.

이 외에도 다양한 자료구조들이 있고 심화 내용들은 추후 보충해가며 학습하도록 해야겠다. 화이팅!🐱‍👓