JavaScript 주요 문법 (4) - 자료구조&알고리즘

조혜준·2023년 10월 24일

프로그래머스 프론트엔드 미니 데브코스

목록 보기

11/14

[1] 자료구조와 알고리즘이 중요한 이유

1) 자료구조와 알고리즘이란?

요리에 비유를 했을 때 요리는 재료 선택 > 도구 선택 > 레시피를 선택하는 프로세스를 거침
요리사를 개발자로 바꿨을 때, 재료는 데이터, 도구는 자료구조, 레시피는 알고리즘, 요리는 결과물, 즉 만들어진 소프트웨어라고 생각하면 됨
->> 자료구조 + 알고리즘 = 프로그램

자료구조

메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로 상황에 따라 유용하게 사용할 수 있는 특정 구조를 이루고 있음
Stack, Queue, Graph, Tree, ...

알고리즘

특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표
정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것
Binary Search, Shortest Path, ...

2) 자료구조와 알고리즘이 중요한 이유

실무에서 중요하게 생각하는 3가지

기초 코딩 능력 < 자료구조와 알고리즘을 공부하면 능력up

= 문재해결 능력
전문 분야 지식

= 특화된 전문 지식. 깊이 알수록, 최신 트렌드를 알수록 좋음
기본 CS 지식

= 학문적인 지식. CS지식이 탄탄할수록 업무상 발생하는 것의 예외상황에 빠르게 대처 가능

문제 해결 능력

논리적 사고
- 해결 방법이 말이 되는가?
전산화 능력
- 현실에 있는것을 소프트웨어로 구현하는 능력(컴퓨터적인 사고가 가능한가?)
엣지 케이스 탐색
- 예외상황 얼마나 잘 찾는가?

[2] 자료구조의 종류

자료구조

메모리를 효율적으로 사용하며 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표로 상황에 따라 유용하게 사용할 수 있는 특정 구조를 이루고 있음
Stack, Queue, Graph, Tree, ...

자료구조는 일차원인 컴퓨터 메모리를 현실에 대응되도록 구조를 만든 것이라고 할 수 있음
-> 자료구조의 종류

선형 구조

한 원소 뒤에 하나의 원소만이 존재하는 형태로, 자료들이 선형으로 나열되어있는 구조를 가짐
선형 구조에 해당되는 자료구조는 배열, 연결 리스트, 스택, 큐 등이 있음

비선형 구조

원소 간 다대다 관계를 가지는 구조로, 계층적 구조나 망형 구조를 표현하기에 적절
비선형 구조에 해당되는 자료구조는 트리와 그래프 등이 있음

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

[3] 시간 복잡도

프로그램의 성능을 정확히 파악하는 것은 불가능
-> 상대적인 비교법 (시간 복잡도)

빅오표기법 Big-O notation
-> O(1) < O(log n) < O(n) < O(nlog n) < O(n²) < O(2ⁿ) < O(n!)

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

// O(log n)
for(let i = 1; i <= n; i *= 2) {
  //...
}

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

// O(n²)
for(let i = 0; i < n; i += 1) {
  for(let j = 0; j < n; j += 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) {
  //...
}

곱의 법칙

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) {
    //...
  }
}

다항 법칙

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

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

>> 상수항은 무시. 가장 큰 항 외엔 전부 무시!

성능 측정 방법
: Date 객체를 이용

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

// ...

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

[4] 배열

배열

연관된 데이터를 연속적인 형태로 구성된 구조를 가짐
배열에 포함된 원소는 순서대로 번호(Index)가 붙음

배열의 특징

고정된 크기를 가지며, 일반적으론 동적으로 크기를 늘릴 수 없음
- 자바스크립트처럼 대부분의 스크립트 언어는 동적으로 크기가 증감되도록 만들어져 있음
원하는 원소의 index를 알고있다면 O(1)으로 원소를 찾을 수 있음
원소를 삭제하면, 해당 index에 빈자리가 생김

배열 요소 삭제

요소 삭제 후 빈 공간으로 남겨두는 게 아니라 뒤의 요소들을 앞당겨줌
삭제 후 순서를 맞추려면 O(n)이 소요됨

배열 요소 추가

마지막 요소부터 뒤로 한칸씩 밀고 원하는 자리에 요소를 추가해줌
중간에 요소를 추가하고 싶다면 O(n)이 소요됨

>> 따라서, 추가와 삭제가 반복되는 로직이라면, 배열 사용을 권하지 않음!

JavaScript에서 사용법

배열 생성

// 빈 Array를 생성할 수 있음
let arr1 = [];
console.log(arr1);

// 미리 초기화된 Array를 생성할 수 있음
let arr2 = [1, 2, 3, 4, 5];
console.log(arr2);

// 많은 값을 같은 값으로 초기화할 경우 fill을 사용할 수 있음
let arr3 = Array(10).fill(0);
console.log(arr3);

// 특정 로직을 사용하여 초기화할 경우, from을 사용할 수 있음
let arr4 = Array.from({ length: 100 }, (_, i) => i);
console.log(arr4);

배열 요소 추가/삭제

const arr = [1, 2, 3];
console.log(arr);
// 4가 끝에 추가됨
arr.push(4);
// 여러개를 한꺼번에 추가 가능
arr.push(5, 6);
console.log(arr);

// 3번 인덱스에 128을 추가
arr.splice(3, 0, 128);
console.log(arr);

// 3번 인덱스를 제거
arr.splice(3, 1);
console.log(arr[3]);

특이점

// 자바스크립트의 Array는 다른 언어의 Array와는 조금 다름
// 자바스크립트의 Array는 동적
const arr = [];
console.log(arr);

arr.push(1);
arr.push(1);
arr.push(2);
arr.push(3);
console.log(arr);

// 자바스크립트의 Array는 HashMap에 더 가까움
console.log(arr.length);
// index가 number가 아니어도 됨
arr["string"] = 10;
arr[false] = 0;
console.log(arr);
console.log(arr.length);
arr[4] = 5;
console.log(arr.length);

[5] 연결 리스트

추가와 삭제가 반복되는 로직이라면 연결리스트를 사용

연결 리스트

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조
각 요소는 노드라고 부르며 데이터 영역과 포인터 영역으로 구성됨

연결 리스트의 특징

메모리가 허용하는 한 요소를 제한없이 추가할 수 있음
탐색은 O(n)이 소요됨
요소를 추가하거나 제거할 때는 O(1)이 소요됨
Singly Linked List, Doubly Linked List, Circular Linked List가 존재

배열과의 차이점

메모리 차이

배열 요소 삭제/추가

연결 리스트의 요소 추가

연결 리스트의 요소 삭제

Singly Linked List

Head에서 Tail까지 단방향으로 이어지는 연결 리스트
가장 단순한 형태의 연결 리스트

핵심 로직
1. 요소 찾기
2. 요소 추가
3. 요소 삭제

'4'를 찾는다면?
> 선형 시간이 소요됨
'3'을 중간에 추가한다면?

'2'를 삭제한다면?

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  
  find(value) {
    let currNode = this.head;
    while (currNode.value !== vlaue) {
      currNode = currNode.next;
    }
    return currNode;
  }
  
  append(newValue) {
    const newNode = new Node(newValue);
    if(this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
  
  insert(node, newValue) {
    const newNode = new Node(newValue);
    newNode.next = node.next;
    node.next = newNode;
  }
  
  remove(value) {
    let prevNode = this.head;
    while (prevNode.next.value !== value) {
      prevNode = prevNode.next;
    }
    
    if(prevNode.next !== null) {
      prevNode.next = prevNode.next.next;
    }
  }
  
  display() {
    let currNode = this.head;
    let displayString = "[";
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.substr(0, displayString.length - 2);
    displayString += "]";
    console.log(displayString);
  }
}

const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(2);
linkedList.append(3);
linkedList.append(5);
linkedList.display();
console.log(linkedList.find(3));
linkedList.remove(3);
linkedList.display();
linkedList.insert(linkedList.find(2), 10);
linkedList.display();