[TIL] 211023

Lee Syongยท2021๋…„ 10์›” 23์ผ
0

TIL

๋ชฉ๋ก ๋ณด๊ธฐ
66/204
post-thumbnail

๐Ÿ“ ์˜ค๋Š˜ ํ•œ ๊ฒƒ

  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. ์ฑ… ๊ณ„์† ์ฝ๊ธฐ

profile
๋Šฅ๋™์ ์œผ๋กœ ์‚ด์ž, ํ–‰๋ณตํ•˜๊ฒŒ๐Ÿ˜

0๊ฐœ์˜ ๋Œ“๊ธ€