회고
하루하루 강의를 듣고 TIL을 적다보니 블로그를 작성하는데 시간이 너무 많이 소요된다. 이렇게 모든것을 공개블로그 TIL로 작성하는 방식이 어느순간부터는 절대 제시간안에 하지 못할 것이라는 직감이 들었다.😥😥 그래서 데브코스의 커피챗을 통해 이 문제점에 대해 조언을 구했다. 멘토님께서 TIL은 누군가에게 알려주기보단 내가 어떤 공부를 했는지 간단하게 정리하는 목적이라는 얘기를 해주셨고 이 조언이 생각을 고치는데 많은 도움이 되었다. 앞으로는 그날의 TIL은 간단한게 내가 알아볼 수 있는 정도로 작성하고 추가학습을 해야하는건 따로 일주일에 1번정도씩 주제를 정해 올리려한다. 이렇게 해야 나도 지치지 않고 계속해서 기록을 유지할 수 있을 것 같다😊😊
자료구조와 알고리즘의 의미
자료구조란?
메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로
상황에 따라 유용하게 사용될 수 있는 특정 구조이다. 즉 자료구조는 일차원적인 컴퓨터 메모리를 현실에 대응되도록 구조를 만든것이라 할 수 있다.
알고리즘이란?
특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표로
일련의 절차나 방법을 공식화한 형태로 표현한 것을 말한다.
문제 해결 능력에서 중요한 것
- 논리적 사고
- 전산화 능력 = 논리를 조합하여 컴퓨터적인 사고가 가능한지에 대한 능력
- 엣지 케이스 탐색 능력 = 예외 상황을 얼마나 잘 찾는지에 대한 능력
시간복잡도
📌 우리는 프로그램의 성능을 정확히 알 수 있는가?
고려할 것 : 입력 크기, 하드웨어 성능, 운영체제 성능, 컴파일러 최적화, 비동기 로직 등등
고려할 것이 너무 많아 성능을 정확하게 파악하는 것은 불가능하다. 그래서 컴퓨터 과학자들은 대략적인 성능을 비교하기 위한 상대적인 표기법인 빅오표기법을 만들었다.
빅오표기법
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!)
📌 빅오 표기법에 식에 계수가 있거나 상수를 더하는 경우가 없는 이유
그 이유는 빅오 표기법은 점근적 표기법을 따르기 때문. 점근적 표기법이란 함수의 증감추세를 비교하는 방법을 말한다.
빅오표기법에서 2가지만 기억해야 할것
-
상수항은 무시, 가장 큰 항 회엔 무시
-
js에서 실제 성능 측정 방법
- Date 객체를 이용(로직이 작동하는 시간 구하기)
console.log("Start");
const start = new Date().getTime();
const N = 1000000000;
let total = 0;
for (let i = 0; i<N; i+=1){
total += i;
}
const end = new Date().getTime();
console.log(end - start); //1114
console.log("Finish")배열
- 연관된 데이터를 연속적인 형태로 구성된 구조를 가진다.
- 배열에 포함된 원소는 순서대로 index가 붙는다.
- 고정된 크기를 가지며 일반적으로 동적으로 크기를 늘릴 수 없다.
- js처럼 대부분의 스크립트 언어는 동적으로 크기가 증감되도록 만들어져 있다.
- 원하는 원소의 index를 알고 있다면 O(1)로 원소를 찾을 수 있다.
- 원소를 삭제하면 해당 index에 빈자리가 생긴다 ex)출석번호
배열의 요소 삭제
삭제 후 순서를 맞추려면 최악의 경우 O(n)이 소요된다.
배열의 요소 추가
배열 중간에 새로운 요소를 추가해야 할 때 추가 후 순서를 맞추려면 최악의 경우 O(n)이 소요된다.
따라서 추가와 삭제가 반복되는 로직이라면 배열 사용을 권장하지 않는다. 배열은 탐색이 많은 경우에 유리한 자료구조다.
연결리스트
추가와 삭제가 반복되는 로직이라면 어떻게 해야할까? ⇒ 연결리스트 사용!!
연결리스트란?
각 요소를 포인터로 연결하여 관리하는 선형 자료구조다. 각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성된다.
연결리스트의 특징
- 메모리가 허용하는 한 요소를 제한없이 추가할 수 있다.
- 탐색은 O(n)이 소요된다.
- 요소를 추가하거나 제거할 때는 O(1)이 소요된다.
- Singly Linked List, Doublt Linked List, Circular Linked List가 존재한다.
배열과의 차이점
-
메모리의 차이
배열 : 메모리를 순차적으로 사용한다.
연결리스트: 포인터를 통해 메모리 영역을 참조한다. -
요소 삭제 및 추가
배열 : 선형시간 O(n) 소요
연결리스트: O(1) 소요
Singly Linked List 단일 연결 리스트
Head에서 Tail까지 단방향으로 이어지는 연결리스트. 가장 단순한 형태인 연결 리스트다.
Doubly Linked List 이중 연결리스트
양방향으로 이어지는 연결리스트이다. 포인터가 2개 존재하며 단일연결 리스트보다 자료구조의 크기가 조금 더 크다.
Circular Linked List
단일 혹은 이중 리스트에서 Tail이 Head로 연결되는 연결리스트이다.
메모리를 아껴쓸 수 있으며 원형 큐등을 만들 때도 사용된다.
스택
Last in First Out 개념을 가진 선형 자료구조다. 바닥이 막힌 상자(프링글스 통)를 생각하면 편하다.
-
push(추가) pop(삭제) Top(스택 맨 위에 있는 값)
-
스택을 이용하는 대표적인 것이 스택 메모리다.
스택메모리 = 함수가 호출되면 생성되는 지역변수, 매개변수가 저장되는 메모리 영역
스택을 배열로 표현하면?
const stack = [];
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();
console.log(stack[stack.length-1]);//Top 구하기