자료구조와 알고리즘 with 파이썬 (독학 8일차)

 

자료구조의 분류. 검색하면 이런 이미지를 많이 보게 된다

자료구조란 

대량의 데이터를 효율적으로 관리(생성, 삭제, 수정)할 수 있는 데이터의 구조 

(1) 자료 구조의 종류

(2) 파이썬에서 구현되는 방법

 

(1) 과 (2) 가 1: 1 매칭이 아니라는게 나한테는 헷갈리는 지점이었다.

 

---

 

배열 : 크기가 같은, 같은 종류의 데이터를 순차적으로 = 연속된 공간에 = 선형적으로 저장하는 형태

           >> 따로따로 흩어져있는 변수를 하나로 묶어 편리하게 사용할 수 있다. 

특징 

1) 구현이 쉽다.

2) index 기반의 직접 접근 가능 = 빠르다 

3) 검색에 용이하다 

단점

1) 데이터 추가와 삭제가 어려움 

2) 용량이 고정됨

 

선형 자료구조의 종류

data type	자료구조	in python	예시	특징
배열 Array	스택 stack	리스트 List	my_list = [123, 456, 'abc']	LIFO(후입선출) : 마지막에 들어온 값이 제일 위에 있음
		튜플 Tuple	my_tuple = (123, 456, 'abc')	리스트와 달리 중간에 값을 변경할 수 없다.
	큐 queue	queue 큐  deque 덱	import queue 또는  from collections import deque	FIFO(선입선출) : 일이 발생한 순서대로 처리됨
	리스트
연결된 구조	리스트

숫자, 문자열을 포함한 어떤 자료든지 저장할 수 있다 (큐나 트리도 마찬가지)

 

---

Stack : 데이터의 추가와 삭제가 맨 위에서만 이루어짐, 용량이 정해져있음

파이썬에서 스택을 구현하기 위해...

1) Class를 이용해서 stack 을 구현할 수도 있지만 

2) 더 쉽게 하는 방법으로... list 를 이용한다.

즉 list의 한 쪽(대개 뒤쪽)을 stack의 상단으로 생각하고 그쪽으로만 자료를 넣거나 빼는 것이다. 

3) queue 모듈에서 Queue, LifoQueue(스택),PriorityQueue(우선순위큐) 등의 클래스 제공함 

 

Stack 연산 in Python

연산	ArrayStack	파이썬 List
삽입	push(e)	L.append(e)
삭제	pop()	L.pop()
요소의 수	size()	len(L)
공백 상태 검사	isEmpty()	len(L) == 0
포화 상태 검사	isFull()	False	파이썬에서 list의 용량의 제한이 없음. 따라서 항상 False 출력
상단 들여다보기	peek()	L[len(L)-1]  또는 L[-1]

---

Que : 일이 일어난 순서대로 처리됨, 용량이 정해져있음

ex. 매표소 : 줄 선 순서대로 표를 살 수 있다. 

ex. 컴퓨터 cpu의 빠른 속도와 다른 주변장치와의 속도 차이를 극복하기 위한 임시 기억장치 (버퍼)

삽입이 일어나는 곳 : 후단 (rear)

삭제가 일어나는 곳 : 전단 (front)

 

선형 큐

: 전단의 데이터가 삭제되면 공백으로 남는다 = 자리 차지만 하고있음

: 후단에 새로운 데이터가 들어갈 자리가 없음 > 큐의 요소를 모두 앞으로 옮겨서 후단의 자리 확보 필요 : 비효율적

원형 큐 : 이러한 선형 큐의 문제점을 해결하는 방법

: 값이 호출되면 rear를 한칸 회전시키고 그 위치에 다른 값을 삽입함

-> 링 버퍼 (ring buffer)로 활용 (오래된 자료를 버리고 항상 최근의 자료를 유지함 & 계속 포화 상태로 유지)

 

Deque 덱 (Double-Eneded-Queue)

: 전단과 후단에서 모두 삽입/삭제가 가능한 큐 but 중간에서는 불가 

: 스택과 큐의 연산을 모두 갖는다

: 원형 덱으로 활용 

 

파이썬에서 큐/덱를 구현하기 위해...

1) 클래스로 구현

2-1) queue 모듈의 Queu 클래스 사용하기

2-2) collections 모듈의 deque 클래스 사용하기 

---

List : 가장 자유로운 선형 자료구조

: 각 자료는 순서 또는 위치(position)을 갖는다.

: 임의의 위치에서 삽입/삭제/수정이 가능하다.

: 어느 위치에 요소가 삽입되면 뒤의 모든 자료가 한칸씩 밀린다. (<-> 삭제도 마찬가지)

집합(set)

: 원소 사이의 순서가 없음 -> 선형 자료구조라고 볼수 없음 / 원소의 중복을 허용하지 않는다 

 

배열 vs 연결된 구조

배열 : 흩어진 요소를 메모리의 연속적인 공간에 저장함

연결된 구조 : 요소들을 모으기를 포기한다. 대신 각 node를 링크(link)로 연결해 관리한다 = linked structure

리스트는 배열, 연결된 구조 두가지로 구현될 수 있다. 

특장점	배열	연결된 구조
k번째 요소에 대한 접근	1. 모든 요소의 크기가 같고 연속된 메모리 공간에 존재함  2. 배열의 시작 주소와 요소 하나의 크기를 알고 있다.	1. 배열의 시작 주소만 알고 있음
	k만 알면 됨 (곱셈 & 덧셈 각 1번씩)	링크를 따라 (k-1) 번 이동해야함
용량	용량이 고정됨 → 너무 작으면 포화상태가 되어 새로운 요소를 넣지 못함. / 너무 크게 할당하면 메모리 낭비	용량이 고정되어있지 않음  → 필요한 크기만큼 새로 할당하여 사용 = 메모리 효율적 사용 (작으면 작은 만큼만 사용, 컴퓨터 메모리 내에서 필요한 만큼 사용가능)
삽입 연산 (삭제연산)	중간에 자료를 삽입하면 그 이후의 모든 요소가 한칸씩 이동해야 삽입이 가능하다.	삽입할 위치의 바로 전 노드의 링크만 변경하면 됨

 

파이썬의 리스트는 배열 구조로 구현되어있다.  but 용량 제한은 없음

 

연결 리스트의 종류

1) 단순 연결 리스트

2) 원형 연결 리스트

3) 이중 연결 리스트

---

Tree 트리 : 비선형구조

 

 

참고 도서. 자료구조와 알고리즘 with 파이썬 _ 최영규 저. (생능북스)