2024년 8월 27일 TIL

오늘 아침에는 특강에서 LinkedList를 이용한

Stack과 Queue의 일부 기능을 구현해봤고

삽입 정렬을 구현해봤다.

 

Stack의

 

psuh(value)는

push(value) {

    const newNode = new Node(value);

    // 새 node 생성

    newNode.next = this.head;

    // 새 node.next로 기존 head가

    // 가리키는 node를 전달하고

    this.head = newNode;

    // head는 새로운 node를 가리키게 한다.

  }

방식으로 마지막에 들어온 Node가

먼저 사용될 수 있게 만들어줬다.

 

pop()은

pop() {

    if (this.head !== null) {

      // head가 null인지 여부 확인

      const returnNode = this.head;

      // head가 가리키는

      // return할 Node를

      // 변수에 담은 후

      this.head = this.head.next;

      // head = head.next로 다음 노드를

      // 가리키게 만든다.

      return returnNode;

    }

    return null;

    //값이 없을 경우

  }

방식으로 head가 가리키고 있는

노드를 제거해야 하기 때문에

head가 가리키는 다음 노드를

head가 가리키게 해야했다.

 

Queue의 

 

dequeue() {

    const returnNode = this.head;

    // head에서 노드를 가져오고

    this.head = returnNode.next;

    // 가져온 노드의 다음 노드를

    // head가 가리키게 만들어야 했다.

    return returnNode !== null ? returnNode : null;

    //노드가 null인지 여부 확인

}

Queue는 먼저 들어온 Node가 먼저 나가기 때문에

head가 가리키는 노드를 가져와서

그 노드의 다음 노드를 head가 가리키게 만든 후

반환해야했다.

 

const insertSort = array => {

  for (let i = 1; i < array.length; i++) {

    //i가 1부터 array의 길이 만큼 반복하면서

    for (let j = i - 1; j >= 0; j--) {

        // i 이전 index를 순회한다.

      if (array[i] < array[j]) {

        // 만약 array[i]보다

        // 큰 array[j]가 있다면

        let temp = array[i];

        array[i] = array[j];

        array[j] = temp;

        i--;

        // array[i] 보다 작은 값이

        // 나타나기 전 까지 앞으로

        // 위치를 옮겨나가는 방식이었다.

      } else break;

      // 만약 array[i]가 크다면 반복문 탈출

    }

  }

  return array;

};

let num = [2, 6, 4, 9, 1];

console.log(...insertSort(num));

 

위와 같은 반복으로 다른 정렬 알고르즘과 비교해서 시간복잡도가

 적은 정렬 알고리즘을 만들 수 있었다.

(운이 좋으면 Ω(n), 일반적인 상황에서는 O(n^2))

 

https://kagan-draca.tistory.com/224

3-3 Challenge

https://kagan-draca.tistory.com/225

4-2 Challenge 요소를 모두 더한 배열에서 k 번지 값 찾기(flat과 flatMap)

 

3-3 Challenge 문제를 바탕으로

자료형을 잘 조합해 복합한 문제를

간단한? 알고리즘으로 풀 수 있었고,

 

4-2 Challenge 문제를 풀어보면서

flat과 flatMat 기능을 알게 됐다.

 

(네트워크 시간에 배운 내용은 내일 정리하겠습니다...)