- 자료구조가 무엇인지 설명할 수 있다.
- 여러가지 자료구조들을 설명할 수 있다.
- 각 자료구조의 장/단점과 사용목적에 대해 설명할 수 있다.
- 시간/공간 복잡도가 무엇인지 설명할 수 있다.
- Big-O 표기법에 대해 설명할 수 있다.
"문자,숫자,소리,그림,영상,단어 등의 형태로 된 의미단위이다.
자료를 의미있게 정리하면, '정보(information)'가 된다."
0과 1, 전기가 통하면 1, 안통하면 0.
-> 이 언어를 인간은 알아먹을 수 없기떄문에 '컴파일러'를 이용해 번역하기 시작.
8비트 = 1byte = 65라는 값
8비트 = 1byte = 66이라는 값
그러나 저 두 값은 a,b가 되기도 함.
=> 즉,
데이터타입: 하나의 데이터를 어떻게 해석할지 정의한것
vs
자료구조: 여러 데이터의 묶음을 어떻게 저장하고 '사용'할지 정의한것.
ex) 배열. 차례차례 데이터들을 저장해놓은 자료구조. 스택,트리 등..
예) 우리에게 천만개의 데이터가 있는데, 그 중 우리가 원하는 데이터를 찾아야하는데,
그거를 배열에 넣어놨다면, 우리는 천만번의 검색을 통해 찾아야 함.
- 개념의 이해뿐만 아니라, 직접 자료구조를 구현해야 한다면, 어떻게 작성해야할지 생각해보기.
- 자료구조의 모양 추상적으로 그림 그려보기.
- 해당 자료구조가 갖고있는 property, method 찾아보기.
- 각 method는 어떻게 동작되고있는것인지 알아보고, 의사코드 작성해보기
- 블로그 플랫폼등에 TIL형식으로 기록하기
쌓여있는 접시더미와 같이 작동한다. LIFO의 구조. === 후입선출의 구조.
자료구조 가져오기 추가하기 삭제하기
stack O(n) O(1) O(1)
놀이공원에서 서는 줄과 같이 작동한다.
사람들이 맨 끝에 줄을 서고, 맨 앞에서부터 놀이기구에 탑승하는것과 같다,
즉 FIFO구조. === 선입선출 구조
function calc(expression) {
// 1. 문자를 하나씩 검사한다.
// 2. 숫자를 만나면 숫자를 스택에 푸시한다.
// 3. 연산자를 만나면 스택에서 팝을 두 번 하고, 두 개의 숫자를 가지고 연산한다.
// 4. 3의 연산 결과를 다시 스택에 푸시한다.
// 5. 문자열이 끝날 때 까지 반복한다.
// 6. 문자열이 끝나면 연산 결과 값을 리턴한다.
}
const result = calc("9 3 * 15 5 / + 2 -")
console.log(result);
- 9와 3을 넣고 *을 만나서 9, 3 pop되고, 스택에 27 들어가고,
- 5, 5를 넣고, 그리고 /를 만나서 15, 5가 pop되고, 3이 스택에 들어가고,
- 27과 3이 stack에 있는 상태에 거기에 +를 만나서, 27,3이 pop되고, 30이 스택에 들어가고,
- 2가 숫자라서 stack에 들어가서 현재 stack에는 30, 2 가 들어있는데, 거기서 -를 만나서,
- 30-2=28이 되어서, 30, 2 pop되고, 28이 들어가게된다. 최종결과값은 그래서 28이 됨.
Q) 그런데 어쩔때, 맨 앞 front index가 2일수가 있는 것이죠?
A) 예를들어 0, 1을 pop해서 맨 앞 fromt index가 2인 경우인 것이다..!
꼭 pop의 경우가 아니더라도 어찌됐든 앞의 두 요소가 삭제돼버려서 뒤의 요소부터 있게된경우다!!
그러므로 예를 들어 0,1,2,3,4,5,6 이 들어있다면
맨 앞 front index가 2인 '2' 요소부터,
2 3 4 5 6 총 5개가 남는것이다..!
오늘의 achivement
우선순위 큐 === 트리 ..? 검색해봐야 할 듯.