오늘배운것
- 자료구조란?
- Stack
- Queue
- Graph
- Tree
- Binary Tree / Binary Search Tree
- 추가적인 사항
1.Array.prototype.findIndex()
2.fill()
자료구조
여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의해준것.
선형구조(스택, 큐) : 데이터를 일렬로 저장하는 방식
비선형구조(트리, 그래프) : 데이터를 일렬로 저장하지 않음
Stack
데이터를 순서대로 쌓는 구조.
가장 먼저 들어간 데이터는 가장 나중에 나장 나중에 나갈 수 있다.
LIFO(last in first out) 또는 FILO 라고도 말한다.
ex) 브라우저의 뒤로가기,앞으로가기,새창열기
1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관합니다.
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는,
현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를
현재 페이지로 가져옵니다.
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는,
Next Stack의 가장 마지막으로 보관된 페이지를 가져옵니다.
4. 마지막으로 현재 페이지를 Prev Stack에 보관합니다.
//////////////////////////////
push();
pop();Queue
데이터를 줄세우는 구조
가장 먼저 들어간 데이터가 가장 먼저 나갈 수 있다
FIFO LILO
ex) 프린트하는 과정
컴퓨터(출력 버튼) -(임시 기억 장치의) Queue에 하나씩 들어옴 -Queue에 들어온 문서를 순서대로 인쇄
//컴퓨터와 프린터 처럼, 각 장치사이에 존재하는 처리속도(시간) 차이를 극복하기 위해,
//임시기억장치의 자료구조로 Queue를 사용한다 ===> Buffer버퍼.
1.CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든다.
2.이 데이터를 인쇄 작업 Queue에 저장하고 다른 작업을 수행합니다.
3.프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄합니다.
////////////////////////
push();
shift();
Graph
그래프 : 여러개의 점들이 복잡하게 연결되어있는 관계를 표현한 자료구조
- 정점vertex
- 간선edge (단방향, 양방향)
직접적인 관계라면, 두 정점을 이어주는 선이 존재하고,
간접적인 관례라면, 몇개의 점과 선에 걸쳐 이어지게 된다.
- 무(방)향그래프
- 진입차수/진출차수: 한 정점에 진입하고 진출하는 간선이 몇개인지
- 인접(adgacency): 두 정점간에 간선이 이어져 있는경우, 두 정점의 관계은 인접
- 자기루프: 정점에서 진출하는 간선이 자기자신에게 진입하는 경우. 다른정점을 거치지 않음!!
- 사이클: 한 정점에서 출발하여 해당 정점으로 돌아갈 수 있는 경우를 사이클이 있다고 표현
인접행렬
가장 빠른경로를 찾을때. 두 정점사이에 관계여부 확인
인접리스트
순서는 보통 중요하지 않다.(예외 존재) / 메모리의 효율적인 사용 가능
Tree
그래프의 여러 구조중 무방향으로 연결된 계층적 자료구조
데이터를 순차적으로 나열시키지 않았고, 하나의 데이터 뒤에 여러개 데이터가 존재하는비선형구조
루트라는 하나의 꼭짓점데이터를 시작으로 여러개의 데이터를 간선으로 연결함
- 노드(Node) : 트리 구조를 이루는 모든 개별 데이터
- 루트(Root) : 트리 구조의 시작점이 되는 노드
- 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
- 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
- 리프(Leaf) : 트리 구조의 끝지점이고, 자식 노드가 없는 노드
- depth : 루트의 깊이는 0, 그 자식노드들의 깊이는 1
- level : 같은 깊이를 가지고 있는 높이를 묶어 레벨로 표현.
depth0인 루트 -> level1 - height : 리프노드 - 루트 까지의 높이. 리프노드의 H:0(레벨과 차이가 있다)
h,i,j,f,g : H가 0
d,e : H가 1 - subtree
Binary Search Tree
이진트리는 자식노드가 최대 2개인 노드들로 구성되어있다.
- 정 이진트리 : 각 노드가 0개 혹은 2개의 자식 노드를 가진다.
- 완전 이진트리 : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 한다.
마지막 노드는 전부 차있지 않아도 되지만, 왼쪽은 차 있어야 한다. - 포화 이진 트리 : 모든 리프노드의 레벨이 동일. 모든 레벨이 가득 채워져있어야 한다.
이진탐색트리는 모든 왼쪽자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가진다
추가적인 사항
- findIndex()
let arr = [6,2,3,5,2,9,2,4];
let result = arr.findIndex((el) => {
return el > arr[0]
});
console.log(result); //5
//배열의 요소들을 순회하며, el이 arr[0]보다 크다면,
//해당 el의 인덱스를 반환한다.
//또한 해당값이 없다면 -1을 반환해준다. - fill()
const array1 = [1, 2, 3, 4];
// fill with 0 from position 2 until position 4
console.log(array1.fill(0, 2, 4));
// expected output: [1, 2, 0, 0]
// fill with 5 from position 1
console.log(array1.fill(5, 1));
// expected output: [1, 5, 5, 5]
console.log(array1.fill(6));
// expected output: [6, 6, 6, 6]
///////////////////////사용예시///////////////////
let newArr = Array(3).fill(0); // [0,0,0] 배열안에 3자리를 만들어서 모두 0으로 채움정리 및 느낀점
자료구조는 데이터의 표현 및 저장방법을 말하고,
알고리즘은 자료를 대상으로 하는 문제의 해결방법을 말한다.
예를들어, 배열의 선언은 자료구조적인 코드,
배열에 저장된 요소의 합을 구하는 반복문의 구성은 알고리즘적인 코드이다.
즉, 자료구조가 결정되어야 그에 따른 효율적인 문제해결이 가능하기 때문에 둘은 매우 밀접하다고 한다......................
그리고 트리구조는 새 포스트로 따로 정리해야겠다.
이미지출처 by sehongpark
