Data Structure & Algorithm
-
객체Data Structure & Algorithm 2022. 3. 21. 21:17
객체 여러 값을 키-값 형태로 결합시킨 복합 타입 사물함에 비유 가능 Javascript 에서 객체 생성 const obj1 = new Object(); const obj2 = {}; const obj3 = { name: "kim", age: 15}; console.log(obj1); // {} console.log(obj2); // {} console.log(obj3); {name: 'kim', age: 15} 객체에 키-값 추가/삭제 const obj = new Object(); obj['name'] = 'kim'; obj.age = 16; console.log(obj); // {name: 'kim', age: 16} delete obj.age; console.log('name' in obj); //..
-
배열Data Structure & Algorithm 2022. 3. 20. 23:45
정의 연관된 데이터를 연속적인 형태로 저장하는 자료구조 특징 배열에 포함된 원소는 순서대로 번호(index)가 붙음 원하는 원소의 index를 알고 있다면 배열 내의 원소를 찾을 수 있음 배열 내 원소를 삭제하면 해당 index에 빈자리가 생김 고정된 크기를 가지며 일반적으로는 동적으로 크기를 변경할 수 없음 => JS 등의 스크립트 언어에서는 배열의 크기가 가변적인 경우가 많음 배열에 원소 추가/삭제 시 O(n) 이 소요됨 => 추가/삭제가 반복되는 로직에는 배열 사용이 권장되지 않음 탐색이 많은 경우에 유리 Javascript 에서 배열 사용 시 유의할 점 배열 내 원소의 추가/삭제 시 사용되는 splice 의 경우 O(n) 의 시간복잡도를 가짐 배열의 크기가 가변적 자바스크립트의 배열은 기본적으로 ..
-
Big-O 표기법Data Structure & Algorithm 2022. 3. 20. 23:32
Big-O 표기법이란? 시간복잡도를 나타내는 방법 중 하나 Big-O 복잡도 O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) n이 모두 같은 수일 때 위의 순서로 복잡도가 높아지며 수행 시간이 늘어남(성능이 떨어짐) Big-O 표기법 4법칙 Big-O 표기법은 점근적 표기법을 따름 따라서 상수를 더하거나 곱하는 등의 표기를 따로 하지 않음 물론 실제 계산에서는 상수에 따라 성능이 달라질 수 있음 계수 법칙 n이 무한에 가까울수록 상수(k)의 의미가 없어지기 때문에 계수를 생략 합의 법칙 Big-O 간 합산 가능 곱의 법칙 Big-O 간 곱셈 가능 다항 법칙 특정 함수가 3차 다항식이면 해당 함수의 Big-O 복잡도는 O(n³) 이 됨 정리 아래 ..
-
자료구조란?Data Structure & Algorithm 2022. 3. 20. 23:11
정의 메모리를 효율적으로 사용하여 빠르고 안정적으로 데이터를 처리하는 것을 목표로 상황에 따라 유용하게 사용될 수 있는 특정 구조 종류 1. 단순 구조 정수 실수 문자열 논리 2. 선형 구조 > 한 원소 뒤에 하나의 원소만 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조 배열 연결 리스트 스택 큐 3. 비선형 구조 > 원소 간 다대 다 관계를 가지는 구조로 계층적 구조나 망형 구조 등으로 표현 트리 그래프 주의사항 완벽한 자료구조는 없으며 특정 상황에 가장 유용한 자료구조가 있을 뿐이므로 상황에 맞게 적절한 자료구조를 선택하는 것이 중요