프로그래머스 데브코스 TIL - Day 3

 

✅ 학습 목차

- [Day 3] JavaScript 주요 문법 (3)

 

✅ 새롭게 학습한 부분

- 시간복잡도

- 연결리스트

 

---

 

시간복잡도란?

알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한 것

Big-O 표기법

 Big O 표기법은 최악의 경우를 고려하며, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다.

 

Big-O 표기법의 종류

O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!)

 

O(1) 상수 시간 (Constant time)

입력값이 증가하더라도 시간이 늘어나지 않는다.

 

O(log n) : 로그 시간 (Logarithmic time)

원하는 값을 탐색할 때 경우의 수를 절반으로 줄여가며 탐색을 하는

Binary Search Tree의 탐색이 O(log n)의 시간 복잡도를 가지고 있다.

 

O(n) 선형 시간 (Linear time)

입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것

대표적으로 for문이 O(n)에 해당되며 배열요소의 추가 삭제도 O(n)이다.

function algorithm(n) {
  for (let i = 0; i < n; i++) {
   //
  }
}

 

O(n log n) 선형로그시간 (Log Linear time)

입력 값이 증가할수록 처리 시간이 로그(log) 만큼 늘어나는 알고리즘

대표적 알고리즘으로는 병합 정렬 알고리즘, 퀵 정렬 알고리즘이 있다.

 

O(n2): 2차 시간 (Quadratic time) 

입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가

대표적으로 이중 for문이 O(n2)의 시간복잡도를 가지고 있다.

function algorithm(n) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      // 
    }
  }
}

 

O(2n) 지수 시간 (Exponential time)

Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

2n에 비례하여 연산수가 증가하는 피보나치 수 알고리즘이 해당된다.

function algorithm (n) {
  if (n <= 1) {
    return 1;
  }
  return func(n-1) + fun(n-2);
}

 

---

 

연결리스트 (Linked List)

Head에서 tail까지 단방향으로 이어지는 연결리스트.

Linked List는 배열과는 다르게 메모리상에 index에 의한 물리적 배치를 하지 않고,
node를 생성 후 해당 node의 pointer에 의해 다음 node를 연결한다.

 

연결리스트의 Big-O

 

Insert - O(1)

Delete - O(1)

Search - O(n)

 

* 탐색과정을 거친다면 O(n)이 된다.

 

이중 연결 리스트(Doubly linked list)

 

양방향으로 이어지는 연결리스트.

노드를 탐색하는 방향이 양쪽으로 가능하다.

 

연결리스트의 코드를 토대로 이중연결리스트를

과제로 받아서 코드를 작성해보았다.

 

node

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

양방향으로 전달되는 것이기 때문에  prev를 추가하였다.

 

상단부분

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
  }
  find(value) {
    let currNode = this.head;
    while (currNode.value !== value) {
      currNode = currNode.next;
    }
    return currNode;
  }

기존의 연결리스트 코드와 동일하게 진행했다.

 

append

append(newValue) {
    const newNode = new Node(newValue);
    //
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
  }

tail은 늘 마지막을 가르키기 때문에 새로 추가될 newNode.prev에 tail을 담아주었다.

 

insert

  insert(node, newValue) {
    const newNode = new Node(newValue);

    if (node.next === null) {
    // 맨 뒤의 노드인지 체크
      newNode.next = null;
      this.tail = newNode;
    } else {
      newNode.next = node.next;
    }
    newNode.prev = node;
    node.next = newNode;
  }

특정 node의 뒤로 추가가 되는 코드이기 때문에 맨 앞에 올 수 없다.

해당 node의 next는 그대로 newNode의 next이고

newNode의 prev는 전달받은 node가 된다.

 

remove

  remove(value) {
    let removeNode = this.head;
    while (removeNode.value !== value) {
      removeNode = removeNode.next;
    }

    if (!removeNode.prev && !removeNode.next) {
      this.head = null;
      this.tail = null;
      return;
    }

    if (!removeNode.prev) {
      // 첫 번째 노드인지 체크
      this.head = removeNode.next;
      removeNode.next.prev = null;
    } else if (!removeNode.next) {
      // 마지막 노드인지 체크
      this.tail = removeNode.prev;
      removeNode.prev.next = null;
    } else {
      removeNode.next.prev = removeNode.prev;
      removeNode.prev.next = removeNode.next;
    }
  }

처음에 기존 연결리스트의 코드에서 수정하는 식으로 구현했다가

코드가 복잡해져서 기준을 prevNode에서 removeNode로 바꾸었다.

맨앞이나 맨 뒤위 요소를 삭제할 경우 에러가 발생해서 체크하는 코드를 추가했다.

 

size

size() {
    let nodes = this.head;
    let nodeSize = 1;
    if (this.head == null) {
      return 0;
    }
    while (nodes.next !== null) {
      nodeSize++;
      nodes = nodes.next;
    }
    return nodeSize;
  }

노드가 비어있을 경우 0을 반환하고

사이즈를 카운트 해서 

 

display

  display() {
    let currNode = this.head;
    let displayString = "[";
    while (currNode !== null) {
      displayString += `${currNode.value}, `;
      currNode = currNode.next;
    }
    displayString = displayString.length > 1 ? displayString.substring(0, displayString.length - 2) : displayString;
    displayString += "]";
    console.log(displayString);
  }

currNode가 없을경우 console에 "]"만 노출되어서 해당부분의 코드만 수정했다.

 

---

✍ 느낀점

 

코딩테스트 문제풀이 댓글에서 시간복잡도에 관련된 내용들이 자주 등장해서

간단하게 O(n), O(n2)정도만 알고있었는데 이번기회에 복잡도의 단계에 대해 좀 더 알게 되었다.

알고리즘의 중요함은 알지만 많은 문제를 접하지 않아서 그런지 조금 어렵게 느껴졌었다.

강의에서 누워서 읽는 알고리즘이라는 책을 추천해주셨는데 제목이 마음에 들기도하고🤣

구입해서 읽어볼 생각이다. (정말로 누워서 볼 생각)

그리고 연결리스트는 처음 알게된 개념이였는데 이렇게도 리스트를 관리할 수 있다는 것에 대해

알게 되었다. 재미있게 과제를 했는데 하고나서 검색해보니 추가할 기능들이 더 있었지만

시간조절을 위해서 넘어가야 해서 저것까지 밖에 못해보는 것이 아쉬웠다.

 

 

 

시간복잡도