자료구조 공부 목표
- 자료구조 개념 및 설명
- stack, queue, tree, graph 개념 이해
- 기본 개념과 구조를 파악 및 목적을 이해
- 상황에 맞는 자료구조를 떠올릴 수 있다.
- tree 및 graph 탐색 기법 이해
- BST 이해
- BFS, DFS 개념 이해
자료구조란?
쉽게 말해 데이터들의 구조이다.
수많은 데이터들을 어떻게 저장하고, 어떻게 위치를 새우냐에 따라 사용하는 방법이 다를 것이다.
데이터 : 문자, 숫자, 그림, 영상 등 다양한 정보의 집합
자료구조 종류
자료구조
-
단순구조
- 정수 / 실수
- 문자 / 문자열
- 2진수
-
선형구조 (선 모양으로 생긴 자료 구조)
- 리스트(배열)
- 연결 리스트
- 단순 / 이중 / 원형
- 덱 / 스텍 / 큐
-
비선형구조
- 트리
- 일반 트리 / 이진 트리
- 그래프
- 방향 그래프 / 무방향 그래프
- 트리
STACK
데이터를 순서대로 쌓는 자료구조
스텍을 쉽게 설명하기 위해서 엘리베이터에 들어가는 사람들로 이해하면 쉽다.
엘리베이터에 먼저 탄 사람이 나중에 탄 사람보다 반드시 늦게 나와야 한다는 조건 하에
엘리베이터에 사람들이 들어가면 나중에 타는 사람부터 빠져나와야 처음 탄 사람이 엘리베이터에서 내릴 수 있다.
스텍의 개념
스텍은 FILO 특징을 가지고 있다.
FILO: First In Last Out 먼저 들어간 input값은 마지막에 나온다.
스텍과 정확히 반대 되는 개념이 Queue이다.
QUEUE
큐는 지하철 개찰구를 생각하면 쉽다.
앞사람이 개찰구로 들어가야만 다음사람이 들어갈 수 있다.
큐이 개념
큐는 FIFO OR LILO 특징을 가지고 있다.
FIFO: First in First out 먼저 들어간 input값은 먼저 출력 된다.
새롭게 알아 가는 것
데이터를 장치들이 주고 받을 때, 장치 사이에 존재하는 속도, 시간 등의 차이를 극복하기 위해 임시 기억 장치에 Queue 형태로 사용합니다. 이것을 통틀어 버퍼(Buffer) 라고 합니다.
GRAPH
자료구조에서 그래프는 비선형구조로 순서가 없고, 서로 복잡하게 연결되어 있는 자료구조 이다.
정점 : 하나의 점을 정점이라고 말한다.
간선 : 점과 점을 이어주는 선을 간선이라고 한다.
트리 용어
무방향 그래프
진입차수 / 진출차수
인접
자기루프
사이클
