cs-js-02-자료구조&알고리즘-자료구조의 종류

SeungWoo Yoo ·2023년 2월 7일

DataAlgo

JS-자료구조-알고리즘

목록 보기

2/16

1. 자료구조

1.1 자료구조

메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로
상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있다.

자주 등장하는 네 가지의 자료구조 = Stack, Queue, Tree, Graph

1.2 전산화

현실에 존재하는 영화 예매를 어떻게 컴퓨터로 옮길 것인가? 무엇을 고려해야 하는가?

현실에서 수행되는 프로세스는?
- 고객은 어떤 영화를 볼 지 고른다.
- 고객은 영화를 예매하기 위해 줄을 선다.
- 고객은 차례가 왔을 떄 좌석을 선택한다.
- 고객은 최종적으로 돈을 지불한다.
소프트웨어에서 어떻게 처리할 것인가?
- 영화를 검색한다. → Trie
- 고객이 많을 경우 줄을 서야한다. → Queue
- 고객은 좌석을 선택할 수 있어야 한다. → HashTable

결국 자료구조는 일차원인 컴퓨터 메모리를 현실에 대응되도록 구조를 만든 것이라 할 수 있다.

1.3 자료구조 종류

단순 구조
- 정수, 실수, 문자열, 트리
선형 구조
- 배열
- 연결리스트
- 스택
- 큐
비선형 구조
- 트리
- 그래프
파일구조
- 순차 파일, 색인파일, 직접 파일

1.3.1 선형 구조

한 원소 뒤에 하나의 원소 만이 존재하는 형태로 자료들이 선형으로 나열되어 있는 구조

Data Structure_2_1

1.3.2 비선형 구조

원소 간 다대다 관계를 가지는 구조로 계층적 구조나 망형 구조를 표현하기에 적절

Data Structure_2_2

1.4 완벽한 자료구조는 없다

더 좋고 더 나쁜 자료구조는 없다. 특정 상황에서 유용한 자료구조와 덜 유용한 자료구조가 존재할 뿐이다.
우리는 상황에 맞는 적절한 자료구조를 선택하면 된다.

2. 시간 복잡도

2.1 프로그램의 성능을 정학히 알 수 있는가?

고려할 것

입력 크기
하드웨어 성능
운영체제 성능
컴파일러 최적화
비동기 로직
...

프로그램의 성능을 정학히 파악하는 것은 불가능합니다.
그렇기 때문에 컴퓨터 과학자들은 대략적인 성능을 파악하기 위해 빅오 표기법을 도입했습니다.

2.2 Big-O Notation (빅오 표기법)

Data Structure_2_3

$O(1)$ : 상수 시간❌
- 각 인풋 공간에 변화가 없다.
- 그래서 constant(변함없는) time라 부름
$O(log\ n)$ : 로그 시간
- cf. 로그는 밑이 2
- e.g. 이진 탐색(binary search)
$O(n)$ : 선형 시간(linear time)
- 최악의 경우 n개의 연산을 수행해야 할 경우 적용
- 대부분 간단한 반복문 안에서 constant time연산을 하는 경우
$O(n\ log\ n)$ : 선형 로그 시간
- 실행시간이 입력크기의 로그에 비례
$O(n^2)$ : 2차 시간
$O(2^n)$ : 지수 시간❌
- e.g. 피보나치 수열
$O(n!)$ : 팩토리얼 시간❌

Ref

understanding big O notation with js

엔지니어 대한민국 유튜브 - 빅오표기법 완전정복

2.2.1 $O(n)$ : 선형 시간

for (let i = 0; i < n; i += 1) {
  // ...
}

2.2.2 $O(log\ n)$ : 로그 시간

for (let i = 0; i <= n; i += 2) {
  // ...
}

i = 2n의 값을 볼 수 있으므로 n번째 반복에서는 i = 2n
그러므로 이 결과를 추론할 수 있다.
- $2n < N$
- $log(2n) < log(N)$
- $n < log(N)$

2.2.3 $O(n\ log\ n)$ : 선형 로그 시간

for (let i = 0; i < n; i += 1) {
  for (let j = 1; j <= n; i += 2) {
    // ...
  }
}

2.2.4 $O(n^2)$ : 2차 시간

for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n; i += 1) {
    // ...
  }
}

O(n^2+126) = O(n^2)\\ O(3n-30) = O(n)\\ O(3\ log\ n) = O(log\ n)

빅오 표기법은 점근적 표기법을 따릅니다. 점근적 표기법은 함수의 증감 추세를 비교하는 방법입니다.

다음 그림처럼 c와 g가 양수라고 가정하고, n이 $n_0$ 를 넘어설 떄,
함수 $f$ 에는 함수 $g$ 에 한없이 가까워질 순 있지만, 넘을 수는 없습니다.
한마디로, 함수 g(n)에는 함수 f의 한계치라 할 수 있습니다.

Data Structure_2_4

2.3 빅오표기법 법칙

2.3.1 계수 법칙

상수 $k$ 가 0보다 클 떄 $f(n)=O(g(n))$ 이면 $kf(n)=O(g(n))$ 이다.
$n$ 이 무한에 가까울 수록 $k$ 의 크기는 의미가 없기 떄문이다.

// 두 루프는 같은 O(n)으로 표기된다.
for (let i = 0; i < n; i += 1) {
  // ...
}

for (let i = 0; i < n * 5; i += 1) {
  // ...
}

2.3.2 합의 법칙

$f(n)=O(h(n))$ 이고 $g(n)=O(p(n))$ 이면 $f(n)+g(n)=O(h(n))+O(p(n))$ 이다.
빅오는 더해질 수 있다.

// 두 루프를 합쳐 O(n + m)으로 표기할 수 있다.
// 계수 법칙에 의해 5는 사라진다.
for (let i = 0; i < n; i += 1) {
  // ...
}

for (let i = 0; i < m * 5; i += 1) {
  // ...
}

2.3.3 곱의 법칙

$f(n)=O(h(n))$ 이고 $g(n)=O(p(n))$ 이면 $f(n)*g(n)=O(h(n))*O(p(n))$ 이다.
빅오는 곱해질 수 있다.

// 두 루프를 곱해 O(n^2)으로 표기할 수 있다.
// 계수 법칙에 의해 5는 사라진다.
for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n * 5; j += 1) {
    // ...
  }
}

2.3.4 다항 법칙

$f(n)$ 이 $k$ 차 다항식이면 $f(n)$ 은 $O(n^k)$ 이다.

// 다음 루프는 O(n^3)으로 표기할 수 있다.
for (let i = 0; i < n * n * n; i += 1) {
  // ...
}

2.3.5 핵심

2가지만 기억하세요.

(1) 상수항은 무시

// 계수 법칙에 의해 계수는 무시된다.
// 그리하여 O(n + m)으로 표기된다.
for (let i = 0; i < n * 6; i += 1) {
  // ...
}

for (let i = 0; i < m * 3; i += 1) {
  // ...
}

(2) 가장 큰 항 외엔 무시

// O(n^2 + n)이지만 작은 항은 무시하여
// O(n^2)으로만 표기해도 된다.
for (let i = 0; i < n; i += 1) {
  // ...
}
for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n; j += 1) {
    // ...
  }
}

2.4 JS에서 성능 측정 방법

2.4.1 Date 객체를 이용

const start = new Date().getTime();

// ...

const end = new Date().getTime();
console.log(end - start);

2.4.2 예시

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);
console.log('Finish');
/* 결과
start
1063
Finish
*/

3. 자바스크립트 9가지 코드 트릭

3.1 구조 분해 할당을 이용한 변수 swap

ES6의 구조 분해 할당 문법을 사용하여 두 변수를 swap 할 수 있습니다.

let a = 5, b = 10;
[a, b] = [b, a];
console.log(a, b); // 10 5

3.2 배열 생성으로 루프 제거하기

보통 단순히 범위 루프를 돌고 싶다면 다음과 같이 코드를 작성합니다.

let sum = 0;
for (let i = 5; i < 10; i += 1) {
  sum += i; // 35 (5~9까지의 합)
}

만약 범위 루프를 함수형 프로그래밍 방식으로 사용하고 싶다면 배열을 생성해서 사용할 수 있습니다.

// (_, k) => k + 5
// _는 보통 사용하지 않는 변수, 파라메터 등에 이름을 붙일 때 사용
// 특별한 문법적인 기능이 있지는 않지만 관례상 사용되는 규칙
const sum = Array
  .from(new Array(5), (_, k) => k + 5) // 5부터 시작하는 유사 배열 생성
  .reduce((acc, cur) => acc + cur, 0);

💡 from() : 문자열 등 유사 배열(Array-like) 객체나 이터러블한 객체를 배열로 만들어주는 메서드
Array.from(복사할 배열, 복사하면서 수행할 function)

3.3 배열 내 같은 요소 제거하기

Set을 이용할 수 있습니다.

const names = ['Lee', 'Kim', 'Park', 'Lee', 'Kim'];
const uniqueNamesWithArrayFrom = Array.from(new Set(names));
const uniqueNamesWithSpread = [...new Set(names)];

3.4 Spread 연산자를 이용한 객체 병합

두 객체를 별도 변수에 합쳐줄 수 있습니다.

const person = {
  name: 'Lee Sun-Hyoup',
  familyName: 'Lee',
  givenName: 'Sun-Hyoup',
};

const company = {
  name: 'Cobalt. Inc.',
  address: 'Seoul',
};

const leeSunHyoup = { ...person, ...company };
console.log(leeSunHyoup);
// {
//   name: 'Cobalt. Inc.',
//   familyName: 'Lee',
//   givenName: 'Sun-Hyoup',
//   address: 'Seoul' 같은 키는 마지막에 대입된 값으로 정해진다.
// }

3.5 &&와 || 활용

&&와 ||는 조건문 외에서도 활용될 수 있습니다.

/// 📝 ||
// 기본값을 넣어주고 싶을 때 사용할 수 있습니다.
// participantName이 0, undefined, 빈 문자열, null일 경우 'Guest'로 할당됩니다.
let participantName,
  flag = 0;
const name = participantName || 'Guest';

/// 📝 &&
// flag가 true일 경우에만 실행됩니다.
flag && func();

// 객체 병합에도 이용할 수 있습니다.
const makeCompany = (showAddress) => {
  return {
    name: 'Cobalt. Inc.',
    ...(showAddress && { address: 'Seoul' }),
  };
};
console.log(makeCompany(false)); // { name: 'Cobalt. Inc.' }
console.log(makeCompany(true)); // { name: 'Cobalt. Inc.', address: 'Seoul' }

3.6 구조 분해 할당 사용하기

객체에서 필요한 것만 꺼내 쓰는 것이 좋습니다.

const person = {
  name: 'Lee Sun-Hyoup',
  familyName: 'Lee',
  givenName: 'Sun-Hyoup',
  company: 'Cobalt. Inc.',
  address: 'Seoul',
};

const { familyName, givenName } = person;

3.6.1 객체 생성시 키 생략하기

객체를 생성할 때 프로퍼티 키를 변수 이름으로 생략할 수 있습니다.

const name = 'Lee Sun-Hyoup';
const company = 'Cobalt';
const person = {
  name,
  company,
};
console.log(person); // { name: 'Lee Sun-Hyoup', company: 'Cobalt' }

3.7 비구조화 할당 사용하기

함수에 객체를 넘길 경우 필요한 것만 꺼내 쓸 수 있습니다.

const makeCompany = ({ name, address, serviceName }) => {
  return {
    name,
    address,
    serviceName,
  };
};
const cobalt = makeCompany({ name: 'Cobalt. Inc.', address: 'Seoul', serviceName: 'Present' });

3.8 동적 속성 이름

ES6에 추가된 기능으로 객체의 키를 동적으로 생성 할 수 있습니다.

const nameKey = 'name';
const emailKey = 'email';
const person = {
  [nameKey]: 'Lee Sun-Hyoup',
  [emailKey]: 'kciter@naver.com',
};
console.log(person); // { name: 'Lee Sun-Hyoup', email: 'kciter@naver.com' }

3.9 !! 연산자를 사용하여 Boolean 값으로 바꾸기

!! 연산자를 이용하여 0, null, 빈 문자열, undefined, NaN을 false로 그 외에는 true로 변경할 수 있습니다.

function check(variable) {
  if (!!variable) {
    console.log(variable);
  } else {
    console.log('잘못된 값');
  }
}
check(null); // 잘못된 값
check(3.14); // 3.14
check(undefined); // 잘못된 값
check(0); // 잘못된 값
check('Good'); // Good
check(''); // 잘못된 값
check(NaN); // 잘못된 값
check(5); // 5

SeungWoo Yoo

Front-end 공부 중... 책 읽는 걸 좋아합니다.

이전 포스트

cs-js-01-자료구조&알고리즘-시작

다음 포스트

cs-js-02-자료구조&알고리즘-자료구조의 종류

JS-자료구조-알고리즘

1. 자료구조

1.1 자료구조

1.2 전산화

1.3 자료구조 종류

1.3.1 선형 구조

1.3.2 비선형 구조

1.4 완벽한 자료구조는 없다

2. 시간 복잡도

2.1 프로그램의 성능을 정학히 알 수 있는가?

2.2 Big-O Notation (빅오 표기법)

2.2.1 $O(n)$ : 선형 시간

2.2.2 $O(log\ n)$ : 로그 시간

2.2.3 $O(n\ log\ n)$ : 선형 로그 시간

2.2.4 $O(n^2)$ : 2차 시간

2.3 빅오표기법 법칙

2.3.1 계수 법칙

2.3.2 합의 법칙

2.3.3 곱의 법칙

2.3.4 다항 법칙

2.3.5 핵심

2.4 JS에서 성능 측정 방법

2.4.1 Date 객체를 이용

2.4.2 예시

3. 자바스크립트 9가지 코드 트릭

3.1 구조 분해 할당을 이용한 변수 swap

3.2 배열 생성으로 루프 제거하기

3.3 배열 내 같은 요소 제거하기

3.4 Spread 연산자를 이용한 객체 병합

3.5 &&와 || 활용

3.6 구조 분해 할당 사용하기

3.6.1 객체 생성시 키 생략하기

3.7 비구조화 할당 사용하기

3.8 동적 속성 이름

3.9 !! 연산자를 사용하여 Boolean 값으로 바꾸기

cs-js-01-자료구조&알고리즘-시작

cs-js-03-자료구조-배열(Array) & 객체(Object)

0개의 댓글

cs-js-02-자료구조&알고리즘-자료구조의 종류

JS-자료구조-알고리즘

1. 자료구조

1.1 자료구조

1.2 전산화

1.3 자료구조 종류

1.3.1 선형 구조

1.3.2 비선형 구조

1.4 완벽한 자료구조는 없다

2. 시간 복잡도

2.1 프로그램의 성능을 정학히 알 수 있는가?

2.2 Big-O Notation (빅오 표기법)

2.2.1 O(n)O(n)O(n) : 선형 시간

2.2.2 O(log n)O(log\ n)O(log n) : 로그 시간

2.2.3 O(n log n)O(n\ log\ n)O(n log n) : 선형 로그 시간

2.2.4 O(n2)O(n^2)O(n2) : 2차 시간

2.3 빅오표기법 법칙

2.3.1 계수 법칙

2.3.2 합의 법칙

2.3.3 곱의 법칙

2.3.4 다항 법칙

2.3.5 핵심

2.4 JS에서 성능 측정 방법

2.4.1 Date 객체를 이용

2.4.2 예시

3. 자바스크립트 9가지 코드 트릭

3.1 구조 분해 할당을 이용한 변수 swap

3.2 배열 생성으로 루프 제거하기

3.3 배열 내 같은 요소 제거하기

3.4 Spread 연산자를 이용한 객체 병합

3.5 &&와 || 활용

3.6 구조 분해 할당 사용하기

3.6.1 객체 생성시 키 생략하기

3.7 비구조화 할당 사용하기

3.8 동적 속성 이름

3.9 !! 연산자를 사용하여 Boolean 값으로 바꾸기

cs-js-01-자료구조&알고리즘-시작

cs-js-03-자료구조-배열(Array) & 객체(Object)

0개의 댓글

2.2.1 $O(n)$ : 선형 시간

2.2.2 $O(log\ n)$ : 로그 시간

2.2.3 $O(n\ log\ n)$ : 선형 로그 시간

2.2.4 $O(n^2)$ : 2차 시간