자료구조와 알고리즘
- 자료구조 : 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표!
- 알고리즘 : 문제를 효율적이고 빠르게 해결하는것이 목표이며, 정해진 방법을 공식화한 형태로 표현합니다.
문제해결 능력의 핵심 3가지
- 논리적 사고 : 해결 방법 절차가 말이 되는지 ?
- 전산화 능력 : 컴퓨터적 사고가 가능한지 ?
- Edge Case Search : 예외처리를 얼마나 잘 생각 해내는지 ?
자료구조
자료구조는 단순 구조, 선형 구조, 비선형 구조가 있습니다.
-
단순 구조
정수, 실수, 문자열 등이 있습니다. -
선형 구조
데이터 항목 간에 하나의 선행자와 하나의 후행자가 있습니다만,
예시로는 Array, Linked List, Stack, Queue 등이 있습니다. -
비선형 구조
항목이 여러 개의 선행자 또는 후행자를 가질 수 있습니다.
예시로는 Graph, Tree 등이 있습니다.
배열
어떤 배열에 값을 추가하려고 합니다.
ㅁㅁㅁㅁㅁ
// 위 배열에 2번 index에 0 을 추가해보겠습니다.
ㅁㅁ0ㅁㅁㅁ
//이때, 2번 index부터 arr.at(-1)까지의 원소들이 모두 오른쪽으로 한 칸 이동합니다.이처럼 배열의 삽입은 시간복잡도 O(n)가 소요됩니다.
위 배열에서 0을 제거한다면, 0 이후의 모든 원소들이 이번에는 왼쪽으로 한 칸 이동합니다.
배열 요소 삭제도 마찬가지로 시간복잡도 O(n)가 소요됩니다.
한 번에 O(n)의 시간이 소요되니, 반복문 내부에서 배열 요소의 삽입/삭제가 일어난다면,
많은 시간이 소요될 것 같습니다.
그렇기 때문에 배열보다는 다른 자료구조를 사용하는 것이 좋아보이는데요.
이때 사용하면 좋은 Linked List가 있습니다.
Linked List
Linked list의 경우 삽입/삭제의 시간복잡도가 O(1), 상수시간이 소요됩니다.
다만, 탐색은 O(n)입니다.
배열의 경우 연속적인 메모리 공간에 원소를 저장하지만,
Linked list는 연속적인 메모리 공간에 값을 저장하진 않습니다.
각 요소가 데이터와 다음 요소를 가리키는 포인터(참조)로 이루어져 있기에, 굳이 연속적으로 있지는 않습니다.
때문에 배열의 경우, index를 안다면 상수시간이 소요되겠지만
Linked List의 경우, 원하는 요소를 찾기 위해 처음부터 순회해야하고, 이에 시간복잡도가 O(n)가 소요됩니다.
O(log n)
Big-O 에 관한 내용 중, O(log n)은 아래와 같은 상황에서~
for(let i=0; i<n; i *= 2) { ~ }
// 2를 계속 곱해가는 상황.과제
Linked list 구현
https://velog.io/@meow_tarae/JS-Linked-List-%EA%B5%AC%ED%98%84-%EC%97%B0%EC%8A%B5
