[그림으로 배우는 알고리즘] 2. 자료구조

 

자료구조

대량 데이터를 효율적으로 관리하는 구조 ex. 우편번호

 

자료구조 종류

 

1. 배열(Array) : 데이터를 빈틈없이 나열한 자료구조

2. 리스트(List) : 데이터를 순서대로 나열한 자료구조

3. 스택(Stack) : 데이터를 넣는 순서와 반대의 순서로 데이터를 꺼내는 데이터 관리 방법

4. 큐(Queue, 대기행렬) : 데이터를 넣는 순서대로 데이터를 꺼내는 데이터 관리 방법

5. 트리(Tree) : 나뭇가지가 나뉘듯 퍼져나가는 자료구조 

 

스택(Stack)

데이터를 쌓아서 관리하는 방식

데이터를 넣는(쌓는) 작업 : PUSH

데이터를 꺼내는 작업 : POP

 

마지막에 입력한 데이터가 먼저 출력

LIFO(Last In, First Out) 또는 FILO(First in, Last Out) 라고 부른다.

 

큐(Queue)

먼저 입력한 데이터가 먼저 출력되는 특징을 가진 자료구조

FIFO(First in, First Out) 또는 LILO(Last In, Last Out) 라고 부른다.

 

리스트(List)

배열처럼 순서가 있는 데이터 관리할 때 사용

 

1차원 배열 : 데이터들은 차례대로 빈틈없이 나열. 데이터들이 뒤섞여 버리면 순서를 파악할 수 없게 됨

리스트 : 데이터들은 모두 차례로 떨어져 있지만 끈으로 묶여 있다. 데이터의 위치에 구애받지 않는다.

 

단방향 리스트

리스트 안에서 앞쪽에서 뒤쪽을 가리키는 방향성을 가진 끈으로 순서가 있는 데이터를 연결하는 방식

 

구성요소

1. 데이터 : 리스트에서 관리하고자 하는 값

2. 다음 요소를 가리키는 포인터(NEXT 포인터) 

 - 다음 요소가 어디에 있는지를 나태나는 위치 정보가 저장

 - 마지막 요소의 NEXT포인터에는 종료 정보가 저장

3. 첫 번째 요소를 가리키는 포인터 (HEAD 포인터)
 - 리스트에 데이터가 하나도 없을 경우, HEAD 포인터에 '종료 정보'가 저장됨

 

→ 단방향 리스트는 HEAD포인터가 가리키는 요소에서 시작해 NEXT포인터가 종료 정보를 저장한 요소에서 끝난다.

 

양방향 리스트

구성요소

1. 데이터 : 리스트에서 관리하고자 하는 값

2. 다음 요소를 가리키는 포인터(NEXT 포인터) 

 - 바로 다음 요소를 잇는 끈의 역할

 - 마지막 요소의 NEXT포인터에는 종료 정보가 저장

3. 이전 요소를 가리키는 포인터(PREV 포인터)

 - 바로 이전 요소를 잇는 끈의 역활

4. 첫 번째 요소를 가리키는 포인터 (HEAD 포인터)

5. 마지막 요소를 가리키는 포인터(TAIL 포인터)

 

→ 리스트가 비어 있을 때 HEAD포인터와 TAIL포인터 모두에 '종료 정보'가 저장된다.

→ 1번째 요소에서 출발하여 뒷 방향으로 데이터를 추적할 경우 HEAD포인터가 가리키는 요소에서 시작,

NEXT 포인터를 사용하여 다음 요소, 그 다음 요소를 추적할 수 있다.

 

🌈 N번째 요소 조회하는 작업

배열에서는 요소 번호를 사용하면 바로 찾아낼 수 있다.

리스트에서는 1번째 데이터부터 차례대로 찾아가야 한다.

∴ N번째 요소를 참조할 때는 배열이 리스트보다 훨씬 더 효율적이다.

 

🌈 데이터의 삽입, 삭제

1. 데이터 삽입

 배열 : 삽입할 데이처 다음에 존재하는 모든 데이터를 뒤로 이동

 리스트 : 삽입하는 데이터의 앞뒤 데이터를 연결하고 있는 끈을 잘라 새로운 데이터에 연결

 

2. 데이터 삭제

 배열 : 삭제된 데이처 다음에 존재하는 모든 데이터를 앞으로 이동

 리스트 : 삭제하고자 하는 데이트의 끈을 자른 후 앞뒤 데이터를 이어 붙이기만 하면 된다.

 

∴ 데이터를 삽입,삭제할 때는 리스트가 배열보다 효율적이다.

 

이진트리

- 다음 요소를 가리키는 포인터를 2개 가진 단방향 리스트

- 이진트리의 구성요소들을 노드라고 한다.

노드는 부모 노드, 자식 노드, 뿌리(루트) 노드(부모 노드가 없는 노드), 리프(잎, 자식 노드가 없는 노드)가 있다.

 

해시 테이블

해시테이블은?

1. N개의 요소를 가진 루트 배열이라는 이름의 배열

2. 루트 배열의 각 요소들이 가리키는 리스트 

위의 2개의 자료구조가 조합된 것

 

해시 함수에 데이터를 입력해서 구한 값이 루트 배열의 요소 번호가 된다.

 

충돌 : 같은 배열 요소에 그룹화된 데이터가 여러 개 나오는 상황

 

🌈 해시 테이블이 관리하는 특정 데이터 찾기

1. 찾고자 하는 데이터 해시 값부터 정하기

2. 찾고자 하는 데이터가 속한 그룹 찾기

3. 해당 그룹 리스트 안의 데이터만 순서대로 검색한다.

 

그래프

2개 이상 항목이 어떤 관계를 맺고 있는지를 그림으로 표현

그래프에서는 표현하는 항목을 정점(노드)라고 부르고, 각 항목들의 관계를 표현하는 것을 간선(Edge)라고 한다.

→ 그래프는 장점과 간선으로 데이터의 연결 관계를 표현하는 자료구조이다.

 

방향성이 있는 간선을 가진 그래프 → 방향 있는 그래프

방향성이 없는 간선을 가진 그래프 → 방향 없는 그래프

 

 

책 - 그림으로 배우는 알고리즘 Basic 공부하면서 정리했습니다.