TIL-2018-12-11-TUE

요즘 컴퓨터 사이언스 with 부트캠프 라는 책을 읽으면서 조금 더 공학적으로 생각할 수 있게 된다.

지금은 속독으로 1회 완독을 목표로 하고 있고, 총 15장 중에서 13장까지는 어느정도 이해한 상태가 되었다.

1독이 완료되면 부트캠프 책을 다시 읽어보면서 틈틈히 자료구조 책도 읽어볼 예정이다.

(참조: 컴퓨터 사이언스 with 부트캠프, 위키백과)

자료구조

- 자료를 효율적으로 이용할 수 있도록 데이터를 검색, 변경, 삭제할 수 있도록 저장, 관리하는 방법

자료 구조의 분류(구현에 따라)

배열 - 메모리 상에 같은 타입의 자료가 연속적으로 저장, 메모리에 순서대로 할당되므로 캐시 히트가 일어날 확률이 매우 높음

튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조

연결 리스트 - 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝

원형 연결 리스트 - 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트

이중 연결 리스트 - 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다

해시 테이블 - 개체가 해시값에 따라 인덱싱

배열과 연결리스트는 쓰임새가 다르다

배열(Array)

데이터 검색은 빈번하게 일어나는데 반해 새로운 데이터 삽입이 없다

연결리스트(Linked List)

데이터 검색에 비해 새로운 데이터 삽입이나 기존 데이터 삭제가 자주 발생

자료 구조의 분류(형태에 따라)

선형 구조

스택, 큐, 덱

비선형 구조

그래프, 트리(이진트리 등)

스택

push, pop 과 같은 동작이 발생함

맨 마지막에 입력한 데이터를 맨 먼저 출력하는 구조(LIFO, 후입선출)

보통 접시쌓기에 비유하며, 어렸을 때 했던 놀이인 샌드위치 게임(한명이 누우면 다른 사람이 그 위에 눕고, 그 위에 또 눕는..)도 같은 구조이다. 

큐

enqueue, dequeue 와 같은 동작이 발생함

제일 먼저 들어온 데이터가 가장 먼저 나가게 됨(FIFO, 선입선출)

편의점, 마트 등에서 유통기한 때문에 먼저 들어온 것을 먼저 판매하는 구조과 큐와 같은 구조이다.