📝 오늘 한 것

1. 프로그래머스 문제 풀이 - 문자열 내 마음대로 정렬하기 / Array.sort()

2. 노드 기반 자료 구조 / 연결 리스트 / 이중 연결 리스트 / 이중 연결 리스트를 기반으로 하는 큐 구현

📖 학습 자료

1. 책 '누구나 자료 구조와 알고리즘'

📚 배운 것

1. 프로그래머스 문제 풀이

1) Level 1 문제

(1) 문자열 내 마음대로 정렬하기

🔎 처음 작성한 풀이

• 테이스트 케이스는 모두 통과했으나 실제 채점에서 통과를 못했다.

function solution(strings, n) {
  const arr = [];
  for (let i = 0; i < strings.length; i++) {
    arr.push(strings[i].substring(n));
  }
  arr.sort();

  const answer = [];
  
  for (let i = 0; i < arr.length; i++) {
    const subString = arr[i];
    for (let j = 0; j < arr.length; j++) {
      if (subString === strings[j].substring(n)) {
        answer.push(strings[j]);
        break;
      }
    }
  }
  return answer;
}

🔎 두 번째 작성한 풀이

• 처음 풀이는 없는 조건을 내 맘대로 추측해서 끼워넣은 잘못된 풀이였다. 수정할 게 아니라 아예 갈아엎어야 할 거 같아서 그냥 방향을 바꿨다.

• sort(비교 함수) 활용

  비교 함수의 return 값 (1 : b 먼저 / -1 : a 먼저 / 0 : 그대로)

function solution(strings, n) {
  const answer = strings.sort((a, b) => {
    if(a[n] > b[n]) {
      return 1;
    } else if (a[n] < b[n]) {
      return -1;
    } else {
      if(a > b) {
        return 1;
      } else if(a < b) {
        return -1;
      } else {
        return 0;
      }
    }
  });

  return answer;
}

11장. 노드 기반 자료 구조

📌 알고리즘뿐 아니라 자료 구조도 재귀적일 수 있다. 대표적으로 연결 리스트, 이진 트리, 그래프 등이 있다.

📌 연결 리스트는 노드 기반 자료 구조이다.

1) 연결 리스트(Linked List)

(1) 배열 VS 연결 리스트

[ 공통점 ]

• 둘 다 항목의 리스트를 표현하는 자료 구조이다

[ 차이점 ]

• 배열

1. ✔ 메모리 내의 '연속된' 셀 그룹을 말한다.
2. ✔ 컴퓨터는 셀 그룹의 길이와 셀이 시작하는 주소를 알고 있으므로 어떤 인덱스든 한번에 찾아갈 수 있다.

• 연결 리스트

1. ✔ 메모리 내의 '연속되지 않은' 셀 그룹을 말한다.
2. 서로 인접하지 않은 셀(첫 번째 셀+두 번째 셀)을 노드라고 부른다.
3. 각 노드의 첫 번째 셀에는 데이터를, 두 번째 셀에는 다음 노드의 메모리 주소를 저장해야 한다.
4. 마지막 노드의 두 번째 셀은 null이다.
5. 연결 리스트를 다루는 코드는 항상 첫 번째 노드가 메모리의 어디에서 시작하는지를 알아야 한다. 그래야 각 노드의 두 번째 셀의 링크들을 타고 들어가서 리스트를 조합할 수 있다.
6. ✔ 서로 인접하지 않은 여러 셀에 데이터를 저장할 수 있으므로 데이터를 저장할 때 굳이 나란히 이어진 빈 셀 묶음을 찾지 않아도 된다.

(2) 코드 구현

pp.219 ~ 220
Ruby로 구현된 코드 → JavaScript로 변환

Node 클래스 구현

• 노드 class를 이용해 연결 리스트를 만들 수 있다.

• 그러나, 연결 리스트의 각 노드는 인접하지 않기 때문에 프로그램이 연결 리스트의 데이터에 접근하기 위해서는 링크를 타고 타고 들어가야 한다. 하지만, 노드 class만으로는 연결 리스트가 어디서 시작하는지를 알 수 없다.

// 노드 class
class Node {
  constructor (data) {
    this.data = data;
    this.next_node = null;
  }
}

// 노드 4개짜리 연결 리스트 생성 ❗
const node_1 = new Node('once');
const node_2 = new Node('upon');
node_1.next_node = node_2;
const node_3 = new Node('a');
node_2.next_node = node_3;
const node_4 = new Node('time');
node_3.next_node = node_4;

console.log(node_1); // Node {data: 'once', next_node: Node}
console.log(node_2); // Node {data: 'upon', next_node: Node}
console.log(node_3); // Node {data: 'a', next_node: Node}
console.log(node_4); // Node {data: 'time', next_node: null}

LinkedList 클래스 추가

• list 변수는 연결 리스트의 첫 번째 노드를 가리킨다.

• 따라서, 연결 리스트 class를 사용하면, 프로그램에게 연결 리스트가 어디서부터 시작하는지 알려줄 수 있다.

class Node {
  constructor (data) {
    this.data = data;
    this.next_node = null;
  }
}

const node_1 = new Node('once');
const node_2 = new Node('upon');
node_1.next_node = node_2;
const node_3 = new Node('a');
node_2.next_node = node_3;
const node_4 = new Node('time');
node_3.next_node = node_4;

// LinkedList 클래스 추가 ❗
class LinkedList {
  constructor (first_node) {
    this.first_node = first_node;
  }
}

const list = new LinkedList(node_1);
console.log(list); // LinkedList {first_node: Node}

(3) 연결 리스트 연산

• 연결 리스트 class 안에 읽기, 검색, 삽입, 삭제 메서드 추가

pp.221 ~ 229
Ruby로 구현된 코드 → JavaScript로 변환

// 💡 노드 class
class Node {
  constructor (data) {
    this.data = data;
    this.next_node = null;
  }
}

// 노드 4개짜리 연결 리스트 생성
const node_1 = new Node('once');
const node_2 = new Node('upon');
node_1.next_node = node_2;
const node_3 = new Node('a');
node_2.next_node = node_3;
const node_4 = new Node('time');
node_3.next_node = node_4;



// 💡 연결 리스트 class
class LinkedList {
  constructor (first_node) { // 객체 생성 시 연결 리스트의 첫 번째 노드를 적어줌
    this.first_node = first_node;
  }

  // 읽기 ❗
  read(index) {
    curr_node = this.first_node;
    curr_index = 0;
    
    while (curr_index < index) {
      curr_node = curr_node.next_node;
      curr_index++;
    }
    
    return curr_node.data;
  }

  // 검색 ❗
  index_of(value) {
    let curr_node = this.first_node;
    let curr_index = 0;

    if (curr_node.data === value) {
      return curr_index;
    }

    while (curr_node.data !== value && curr_node.next_node !== null) {
      curr_node = curr_node.next_node;
      curr_index++;
    }

    return curr_node.data === value ? curr_index : null;
  }

  // 삽입 ❗
  insert_at_index(index, value) {
    let curr_node = this.first_node;
    let curr_index = 0;

    while (curr_index < index - 1) { // 🙋‍♀️
      curr_node = curr_node.next_node;
      curr_index++;
    }

    const new_node = new Node(value);
    new_node.next_node = curr_node.next_node;

    curr_node.next_node = new_node;
  }
  
  // 삭제 ❗
  delete_at_index(index) {
    let curr_node = this.first_node;
    let curr_index = 0;

    while (curr_index < index - 1) {
      curr_node = curr_node.next_node;
      curr_index++;
    }

    curr_node.next_node = curr_node.next_node.next_node;
  }
}



const list = new LinkedList(node_1);

const forthData = list.read(3);
console.log(forthData); // time

const indexOfValue = list.index_of('메롱');
console.log(indexOfValue); // null

list.insert_at_index(2, '헤이');
console.log(list);
// 인덱스 2에(연결 리스트의 3번째 노드로) '헤이'라는 데이터를 가진 노드가 추가됨
// 연결 리스트 데이터 : once upon 헤이 a time

list.delete_at_index(2);
console.log(list);
// 위에서 추가되었던 노드가 삭제됨
// 연결 리스트 데이터 : once upon a time

🙋‍♀️ Q1. 책에는 여기에 -1이 안 쓰여 있다. 근데 -1을 안 써주면, insert_at_index(2, '헤이')를 실행하면, 인덱스 3에 '헤이'라는 데이터를 가진 노드가 추가된다. index라는 매개변수에 2를 써주면 인덱스 2에 새 노드가 추가되어야 하는 거 아닌가. 검색해 보니까 원래는 연결 리스트 class의 생성자 함수에 head 포인터를 설정해 주던데 이 책에서는 바로 node_1을 넣어줬다. 그것 때문에 꼬인 건가 싶은데 내가 괜히 이상한 데 꽂힌 건지 맞게 파악한 건지 잘 모르겠다.
(보니까 뒤에 '삭제' 코드 부분에선 같은 설명 아래 -1이 쓰여 있다. '삽입' 코드에 오타가 난 건가?)

(4) 빅 오

1. 읽기

   최악의 시나리오는 연결 리스트의 마지막 인덱스를 찾아보는 것이다.
   따라서, 연결 리스트 읽기의 효율성은 O(N)이다.

   +) 배열 읽기의 효율성인 O(1)에 비해 매우 좋지 않다.

2. 검색

   최악의 시나리오는 검색하는 값이 마지막 셀에 있거나 아예 리스트에 없는 것이다.
   따라서, 연결 리스트 검색의 효율성은 O(N)이다.

   +) 배열 검색의 효율성인 O(N)과 같다.

3. 삽입

   최선의 시나리오는 새로운 노드를 연결 리스트의 맨 앞에 삽입하는 것이다.
   최악의 시나리오는 새로운 노드를 연결 리스트의 맨 끝에 삽입하는 것이다.

   최선의 시나리오의 경우, 효율성은 O(1)이다.
   최악의 시나리오의 경우, 효율성은 O(N)이다.

   새로운 노드를 추가할 인덱스 이전의 노드(curr_node)를 연결 리스트 처음부터 순서대로 찾은 후에, 그 노드의 링크(curr_node.next_node)가 새 노드(new_node)를 가리키도록 해야 하기 때문이다.

   +) 배열 삽입과 연결 리스트 삽입은 최선과 최악의 시나리오가 반대이다.

4. 삭제

   최선과 최악의 시나리오, 효율성이 삽입과 똑같다.
   맨 앞을 삭제할 때 효율성은 O(1), 맨 끝을 삭제할 때 효율성은 O(N)이다.

   +) 배열 삭제와 연결 리스트 삭제 또한 최선과 최악의 시나리오가 반대이다.

정리하면,

[ 배열 VS 연결 리스트 ]

연산	배열	연결 리스트
읽기	O(1)	O(N)
검색	O(N)	O(N)
삽입	O(N)(끝에서 하면 O(1))	O(N)(앞에서 하면 O(1))
삭제	O(N)(끝에서 하면 O(1))	O(N)(앞에서 하면 O(1))

이렇게만 보면, 연결 리스트가 배열보다 나은 게 없어 보인다.

(5) 연결 리스트가 배열보다 효율적인 경우

한 리스트를 검사해서 많은 원소를 삭제해야 할 때, 연결 리스트가 배열보다 훨씬 효율적이다.

ex) 이메일 주소 리스트를 검토해 유효하지 않은 형식의 이메일을 모두 삭제하고자 할 때

배열이든 연결 리스트든, 전체 리스트를 처음부터 하나씩 살펴보면서 검사해야 하므로 일단 기본적으로 N단계가 걸린다.

그러나, 배열의 경우, 각 값을 삭제할 때마다 그 값 이후의 모든 값들이 시프트된다. 즉, 각 값이 삭제될 때마다 'N단계'가 추가로 더 걸린다.

반면에, 연결 리스트의 경우, 리스트를 처음부터 하나씩 살펴보다가 삭제할 값을 발견하면 링크가 가리키는 값을 바꿔주기만 하면 된다. 즉, 각 값이 삭제될 때마다 '1단계'가 추가로 더 걸릴 뿐이다.

1000개의 이메일 중 100개의 유효하지 않은 메일이 있다고 했을 때
배열의 경우, 1000 + (100 x 1000) 단계가 걸리지만
연결 리스트의 경우, 1000 + (100 x 1) 단계가 걸릴 뿐이다.

2) 이중 연결 리스트(Doubly Linked List)

(1) 설명

• 이중 연결 리스트의 각 노드에는 2개의 링크가 있다.
  한 링크는 다음 노드를 가리키고, 다른 한 링크는 앞 노드를 가리킨다.
  cf. 연결 리스트: 다음 노드를 가리키는 1개의 링크

• 이중 연결 리스트는 처음과 마지막 노드를 모두 기록한다.
  cf. 연결 리스트: 처음 노드만 기록

(2) 코드 구현

p.232
Ruby로 구현된 코드 → JavaScript로 변환

// 노드 class (2개의 링크를 가짐)
class Node {
  constructor (data) {
    this.data = data;
    this.next_node = null;
    this.prev_node = null;
  }
}

// 이중 연결 리스트 class (처음과 마지막 노드 모두 기록)
class DoublyLinkedList {
  constructor (first_node = null, last_node = null) {
    this.first_node = first_node;
    this.last_node = last_node;
  }
}

(3) 이중 연결 리스트의 맨 끝에 삽입 → O(1)

• 연결 리스트에서, 새 노드를 맨 끝에 삽입할 때의 효율성은 O(N)인 반면,
  이중 연결 리스트에서, 새 노드를 맨 끝에 삽입할 때의 효율성은 O(1)이다.

  이중 연결 리스트에서는 기록해놓은 마지막 노드에 바로 접근할 수 있고, 각 노드가 바로 앞 노드를 가리키는 링크를 가지고 있기 때문이다.

p.233
Ruby로 구현된 코드 → JavaScript로 변환

// 💡 노드 class
class Node {
  constructor (data) {
    this.data = data;
    this.next_node = null;
    this.prev_node = null;
  }
}

// 노드 4개짜리 연결 리스트 생성
const node_1 = new Node('my');
const node_2 = new Node('name');
node_1.next_node = node_2;
node_2.prev_node = node_1;
const node_3 = new Node('is');
node_2.next_node = node_3;
node_3.prev_node = node_2;
const node_4 = new Node('syong');
node_3.next_node = node_4;
node_4.prev_node = node_3;



// 💡 이중 연결 리스트 class
class DoublyLinkedList {
  constructor (first_node = null, last_node = null) {
    this.first_node = first_node;
    this.last_node = last_node;
  }

  // 이중 연결 리스트 맨 끝에 새 노드 삽입 ❗
  insert_at_end(value) {
    const new_node = new Node(value); // 새 노드 생성

    if (!this.first_node) { // 리스트에 아직 노드가 없을 때
      this.first_node = new_node;
      this.last_node = new_node;
    } else { // 리스트에 노드가 있을 때
      new_node.prev_node = this.last_node;
      this.last_node.next_node = new_node;
      this.last_node = new_node; // 꼭 마지막 노드를 '새 노드'로 바꿔줄 것!!
    }
  }
}



const list = new DoublyLinkedList(node_1, node_4);
console.log(list); // DoublyLinkedList {first_node: Node, last_node: Node}

list.insert_at_end('😁');
console.log(list);
// 리스트 마지막에 '😁'라는 데이터를 가진 노드가 추가됨
// my name is syong 😁

(4) 이중 리스트를 기반으로 하는 큐(queue)

큐(queue)란 데이터를 끝에서만 삽입할 수 있고, 앞에서만 삭제할 수 있는 항목들의 리스트를 말한다.

배열(Array)을 큐의 기반으로 사용하면,
(맨 끝) 삽입 시 효율성은 O(1)이 되고, (맨 앞) 삭제 시 효율성은 O(N)이 된다.

연결 리스트(Linked List)를 큐의 기반으로 사용하면,
(맨 끝) 삽입 시 효율성은 O(N)이 되고, (맨 앞) 삭제 시 효율성은 O(1)이 된다.

한편, 이중 연결 리스트(Doubly Linked List)를 큐의 기반으로 사용하면,
(맨 끝) 삽입과 (맨 앞) 삭제 시 효율성이 모두 O(1)이 된다.

// 💡 노드 class
class Node {
  constructor (data) {
    this.data = data;
    this.next_node = null;
    this.prev_node = null;
  }
}



// 💡 이중 연결 리스트 class
class DoublyLinkedList {
  constructor (first_node = null, last_node = null) {
    this.first_node = first_node;
    this.last_node = last_node;
  }

  // 맨 끝에 삽입
  insert_at_end(value) {
    const new_node = new Node(value);

    if (!this.first_node) {
      this.first_node = new_node;
      this.last_node = new_node;
    } else {
      new_node.prev_node = this.last_node;
      this.last_node.next_node = new_node;
      this.last_node = new_node;
    }
  }

  // 맨 앞에서 삭제
  remove_at_front() {
    const remove_node = this.first_node;
    this.first_node = this.first_node.next_node;
    return remove_node;
  }
}



// 💡 큐 class
class Queue {
  constructor () {
    this.queue = new DoublyLinkedList(); // = 이중 연결 리스트를 큐의 기반으로 한다는 뜻
  }

  enque(value) {
    this.queue.insert_at_end(value);
  }

  deque(value) {
    const remove_node = this.queue.remove_at_front(value);
    return remove_node.data;
  }

  tail() {
    return this.queue.last_node.data;
  }
}

const queue = new Queue(); // 이후에 아무것도 삽입 안 하면, 처음과 마지막 노드 모두 기본값 null

queue.enque('첫 번째로 삽입');
queue.enque('두 번째로 삽입');
queue.enque('세 번째로 삽입');

console.log(queue);
// Queue {queue: DoublyLinkedList}
// 첫 번째로 삽입 두 번쨰로 삽입 세 번쨰로 삽입

const remove_data = queue.deque();
console.log(remove_data); // 첫 번째로 삽입 → ∵ 무조건 처음 노드가 삭제됨

✨ 내일 할 것

1. 프로그래머스 문제 풀이

2. 책 계속 읽기