3장 자료구조

자료구조는 대량의 데이터를 효율적으로 관리하는 구조

• 우편번호 체계를 사용한 주소와 출석 번호를 사용한 학생 관리 또한 자료구조이다.
• 알고리즘을 작성할 때 사용하는 자료구조에는 다양한 종류가 있다. (배열, 리스트, 스택, 큐, 트리 등)

스택

책처럼 쌓이는 자료구조

데이터를 쌓는 작업을 push
데이터를 꺼내는 작업을 pop
LIFO, FILO

큐 (대기행렬)

계산대 앞에 줄을 서듯 먼저 입력한 데이터가 먼저 출력되는 자료구조

FIFO, LILO

리스트

끈으로 엮어서 데이터를 관리하는 것

1차원 배열

데이터들은 차례대로 빈틈없이 나열
데이터들은 모두 떨어져 있지만, 끈으로 묶여있다.
리스트는 떨어진 위치에 있는 데이터들을 끈으로 묶어서 순서를 관리하고, ‘다음 데이터가 없음’을 통해 데이터의 끝을 표현한다.

단방향 리스트

리스트 안에서 앞쪽에서 뒷쪽을 가리키는 방향성을 가진 끈으로 순서가 있는 데이터를 연결하는 방식
데이터, 다음 요소를 가리키는 포인터(NEXT 포인터)로 이루어진다.

양방향 리스트

앞에서부터 뒤를 가리키는 끈과 뒤에서 앞을 가리키는 끈 2개를 사용하여 순서가 있는 데이터들을 연결하는 방법
양방향 리스트에는 첫번째 요소와 마지막 요소를 가리키는 포인터가 필요하다.
각 요소는 데이터, 다음 요소를 가리키는 포인터(NEXT 포인터), 이전 요소를 가리키는 포인터(PREV 포인터) 세가지 항목을 가지고 있다.
N번째 요소를 조회할 때, 배열은 첨자를 사용해서 매우 빠르게 찾을 수 있지만, 리스트는 1번째 요소부터 차례대로 찾아가야 하므로 시간이 걸린다.
데이터의 삽입, 삭제가 리스트에서는 포인터 조작만으로 끝나기 때문에 효율적이지만 배열에서는 데이터의 이동이 발생하므로 시간적 비용이 크다.

링 버퍼

배열의 마지막 요소와 1번째 요소를 연결시킨 자료구조이다.
마지막 요소의 다음 요소는 배열의 1번째 요소가 된다.

이진 트리

다음 요소를 가리키는 포인터를 두 개 가진 단방향 리스트의 일종.
부모 1개 자식 2개라는 관계를 활용하여 데이터를 관리하는 것이 이진트리이다.
부모 없는 노드를 뿌리(루트 노드), 자식 없는 노드를 잎(리프)이라 부른다.

힙

각 노드의 값이 다음 조건을 충족하도록 관리되는 이진트리를 뜻한다.
부모 노드의 값은 항상 하위 노드의 값보다 작다. (혹은 크다)
최소값을 구할 때 적합한 힙은 부모 노드의 값이 항상 하위 노드의 값보다 작은 이진트리 이다.

해시 테이블

N개의 요소를 가진 루트 배열이라는 이름의 배열, 루트 배열이 각 요소들이 가리키는 리스트 라는 2개의 자료구조가 조합된 것.
해시 함수에 데이터를 입력해서 구한 값이 루트 배열의 요소 번호가 된다.

그래프

2개 이상의 항목이 어떤 관계를 맺고 있는지 주목하고 그 관계를 그림으로 표현한 것.
그래프에서 표현하는 항목을 정점(노드)라고 부르고, 각 항목들의 관계를 표현하는 선을 간선(Edge)라고 부른다.