자료구조

전상욱·2020년 1월 10일

알고리즘/자료구조

목록 보기

1/6

자료구조 기초

비전공자 개발자..
꼭 알아야할 운영체제, 알고리즘, 자료구조, 네트워크 등등
부족한 부분이 정말 많다.
따라잡는다.

Array, 배열
List, 리스트
Queue, 큐
stack, 스택
Graph, 그래프
Tree, 트리

선형구조 : 배열, 리스트, 큐, 스택

비선형구조: 그래프, 트리

일반적으로 자료구조를 구분할 때 선형과 비선형 구조로 구분하기도 합니다. 각각 선의 형태를 띄는 것과 그렇지 않은 것으로 풀어 말할 수 있으며, 선형 구조는 배열, 리스트, 큐, 스택을 말하고 비선형 구조는 그래프와 트리를 말합니다.

자료구조가 중요한 이유

자료구조는 적은 수의 데이터를 관리하기 위해 고안된 것이 아닙니다. 가령 1개의 데이터를 처리하는데 1초가 걸리는 크기 1의 구조가 있다고 하면, 이 구조를 이용해 1000개의 데이터를 처리하려면 1000의 크기와 1000초가 필요하게 됩니다.
이때 자료구조는 1개의 데이터를 처리하는 시간과 크기를 줄여 데이터를 처리하는데 더 적은 크기와 더 적은 시간이 필요하게끔 하는 역할을 합니다.

따라서 자료구조가 중요한 이유는 프로그램 내에서 자료를 가장 효율적으로 처리하기 위함이고, 그것을 통해 보다 성능 좋은 프로그램을 만들기 위함입니다.

Array, 배열

여러 데이터를 그룹핑해서 관리하기 위한 자료구조
배열안에 여러 정보를 담을수 있고, 반복문과 결합 하면 정보 효율적 관리
크기가 정해져 있다.
인덱스로 식별 /조회 가능

배열의 한계

배열은 길이를 바꿀 수 없다. 가변 배열과 같이 길이가 변경 가능한 배열은 리소스 낭비가 크다.
배열은 인덱스에 따라서 값을 유지하기 때문에, 엘리먼트가 삭제되어도 빈자리가 남게 된다(불필요한 메모리 차지)
삭제한 데이터를 뒤에 위치한 엘리먼트로 메꾸면 데이터가 순서에 따라서 빈틈없이 연속적으로 배치 가능 -> 리스트(list) 라 한다.
- 인덱스가 중요 -> 배열
- 인덱스가 중요 X -> 리스트

List , 리스트

리스트는 배열이 갖는 인덱스 구조의 장점을 버린 대신 각 데이터의 빈틈을 없애는 방법을 선택했습니다. 따라서 데이터의 삽입과 삭제에 대한 데이터 낭비 줄고, 검색 시간이 길어 졌다는 특징

빈틈없는 데이터의 적재
순서가 있는 데이터의 모임
리스트에서 인덱스는 몇번째 데이터인가 정도
순차성을 보장하지 않는다.

리스트에는 Array List와 Linked List가 존재한다. 둘의 큰 차이는 '데이터 연결구조' 다. Array Lists는 배열을 이이용해 Javascript 의 배열 구조처럼 리스트를 구현한 것을 말한다.

Array List
- 내부적으로 배열을 사용하기 때문에 인덱스를 이용해 데이터에 접근이 가능하다
- 데이터 조회 속도 증가 / 데이터를 추가 하거나 삭제하게 되면 각 순서가 일정하게 변경되어야 하기 때문에 데이터의 삽입과 삭제에 상대적으로 오랜시간 소요
Linked List
- 배열을 사용하지 않고, 하나의 데이터에 다음 엘리먼트의 위치정보를 포함
- 특정 데이터를 조회하는 인덱스가 존재하지 않기 때문에 조회하는 속도가 느림
- 데이터 추가 or 삭제시 다른 데이터에 영향을 주지 않기 때문에 상대적으로 빠름
- 노드 : 데이터 + 포인터(주소..)
- 포인터 : 각 노드안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간
  ex)

class Node:
    def __init__ (self, data,next = None):
        self.data = data
        self.next = next

def add(data):
    node = head
    # linked list 에 데이터가 추가 되려면, 맨 끝에 있는 노드로 찾아가야한다.
    while node.next:
        node = node.next
    node.next = Node(data)

node1 = Node(1)
head = node1
for index in range(2, 10):
    add(index)

node = head
while node.next:
    print(node.data)
    node = node.next
print(node.data)

두 List 구조는 장단점을 가지고 있습니다. 일반적으로 고정된 데이터의 검색이 필요하면 Array List사용 하며, 검색이 필요없는 가변적인 데이터가 필요한 경우에는 Linked List를 사용합니다.

Queue, 큐

'줄', '줄을 서서 기다리다'라는 뜻을 가지고 있다. 일상생활을 비유해서 많이 설명되고 있다.'은행창구에서 번호표를 뽑아 기다리기', '신호를 기다리는 차들.. etc' 일종의 큐 구조에 해당된다고 할수 있다. 이러한 큐 구조에 공통적으로 적용되는 특징이 있는데, FIFO & LILO 즉 먼저들어간 사람이 먼저나오고 나중에 들어간 사람이 나중에 나온다.

이러한 큐 구조는 컴퓨터 과학 전반에 자주 쓰이는 자료구조이다. 가장 대표적인 예로 '버퍼(Buffer)'를 들 수 있다.

일반적인 큐는 선형이지만 크기가 제한되어 있고 빈 공간을 사용하려면 모든자료를 꺼내거나 자료를 한 칸씩 옮겨야 한다는 단점이 있기 때문에 순환큐를 구현해 선형 큐의 문제점을 보완할수도 있다. (순환큐- 추후 공부)

(추가)

가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조.
Enqueue: 큐에 데이터를 넣는 기능
Dequeue: 큐에서 데이터를 꺼내는 기능

파이썬 queue 라이브러리

FIFO
1) import queue
2) put : 넣는다
3) get : 출력 (얻는다)

import queue
data_queue = queue.Queue()
data_queue.put('넣는다')
data_queue.put('넣는다2')
data_queue.get()  # get은 당연히 없지 처음들어가는 값 순서대로 출력된다 

>>> 넣는다

LIFO

import queue
data_queue = queue.LifoQueue()

PriorityQueue() : 순서와 상관없이 우선순위를 부여해서 꺼내는..

import queue
data_queue = queue.PriorityQueue()
data_queue.put((10,'apple'))
data_queue.put((3,'macbook'))
data_queue.get()

>>> macbook

Stack, 스택

흔히 스택을 쌓는다고 이야기하는 것처럼 스택은 하나의 바구니에 데이터들이 순차적으로 담겨져있는 형태를 가집니다. LIFO (Last In First Out)으로 데이터가 쌓이게 됩니다. ex) 웹 브라우저의 '앞으로가기' '뒤로가기'

pop(): 스택에서 가장 위에 있는 항목을 제거한다.
Push(item): item 하나를 스택의 가장 윗 부분에 추가한다.
peek(): 스택의 가장 위에 있는 항목을 반환한다.
isEmpty(): 스택이 비어 있을 때에 true를 반한한다.

(추가)

데이터를 제한적으로 접근할 수 있는 구조
* 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조
가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조

def recursive(data):
	if data < 0:
    	print('end')
    else:
    	print(data)
        recursive(data - 1)
        print('returned', data)

구조가 단순해서, 구현하기 쉽다.
데이터 저장/읽기 속도가 빠르다.
데이터 최대 갯수를 정해야 한다. (Python 재귀함수 1000번 까지 호출)

# append : push 
# pop(): pop

data_list = []

def push(data):
    data_list.append(data)
    return 

def pop():
    data = data_list[-1]
    del data_list[-1]
    return 

for i in range(10):
    push(i)

pop()

Graph, 그래프

단순히 노드와 그 노드를 연결하는 엣지를 하나로 모아 놓은 자료구조. 즉, 연결되어 있는 객체간의 관계를 표현할 수 있는 자료구조. 예를들면 지도, 지하철 노선도 최단경로,전기 회로, 도로, etc 그리고 그래프는 여러 개의 고립된 부분 그래프로 구성될 수 있다.

방향성:
- 방향그래프 (Directed) : 간선을 통해 양 방향으로 갈 수 있다.ex) 양방향 도로
- 무방향 그래프(Undirected) : 간선에 방향성이 존재 ex) 일반 통행
사이클:
- 사이클(Cycle)가능 : 단순 경로의 시작 정점과 종료 정점이 동일
- 자체 간선(self-loop)가능
- 순환 그래프(Cyclic)
- 비순환 그래프(Acyclic) : 사이클이 없는 그래프
루트노드 개념없음
부모-자식의 개념이 없음
네트워크 모델