도서 리뷰 시리즈 - 자바스크립트로 하는 자료 구조와 알고리즘

 

 

출처

『자바스크립트로 하는 자료 구조와 알고리즘』 배세민 저/김무항 역 | 에이콘출판사 | 2019년 08월 30일

 

 

한 줄 리뷰

자바스크립트로 자료 구조와 알고리즘을 쉽게 학습해 볼 수 있는 도서

 

 

9장 집합

가장 근간이 된 자료 구조 중 하나

유한하고 구분되는 객체들의 그룹

정렬되지 않는 유일한 항목들의 그룹

const set = new Set();
set.add(1);
set.delete(1);
set.add(2);
console.log(set.has(1), set.has(2)); // false true

 

 

교집합

const intersectSets = (setA, setB) => {
  const intersection = new Set();
  for (const elem of setB) {
    if (setA.has(elem)) {
      intersection.add(elem);
    }
  }
  return intersection;
};

console.log(
  intersectSets(
     new Set([1, 2, 3, 4]),
     new Set([2, 3]),
  )
); // Set {2, 3}

 

 

합집합

const unionSets = (setA, setB) => {
  const union = new Set(setA);
  for (const elem of setB) {
    union.add(elem);
  }
  return union;
};
// 또는
const unionSets = (setA, setB) => {
  return new Set([...setA, ...setB]);
};

console.log(
  unionSets(
     new Set([1, 2, 3, 4]),
     new Set([2, 3]),
  )
); // Set {1, 2, 3, 4}

 

 

차집합

const differenceSets = (setA, setB) => {
  const difference = new Set(setA);
  for (const elem of setB) {
    difference.delete(elem);
  }
  return difference;
};

console.log(
  differenceSets(
     new Set([1, 2, 3, 4]),
     new Set([2, 3]),
  )
); // Set {1, 4}

 

 

18장 고급 문자열

트라이(접두사 트리)

문자열을 검색해 저장된 문자열 중 일치하는 문자열이 있는 지 확인하는데 주로 사용되는 특별한 종류의 트리이다.

각 단계에서 노드는 단어를 완성하기 위해 가지를 친다.

각 마지막 노드에는 endOfWord라는 불리언 플래그가 있다.

이는 어떤 단어가 해당 경로에서 종료되는지 여부를 나타낸다.

예를 들어 Sam에서 m은 endOfWord는 true로 설정된다.

트라이는 중첩 객체를 사용해 구현된다. 이때 각 노드는 자신과 직접 연결된 자식들을 지니는 데 이 자식들은 키 역할을 한다.

트라이는 루트 노드가 존재한다.

[삽입] 신규 노드를 삽입할 때 해당 노드가 루트의 자식으로 존재하지 않는 경우 해당 노드를 루트의 자식으로 생성해야 한다.

 

 

ES6로 작성한 예제

class TrieNode {
  constructor() {
    this.children = {}
    this.endOfWord = false
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode()
  }
  insert(word) {
    let current = this.root
    Array.from(word).forEach(ch => {
      let node = current.children[ch]
      if (!node) {
        node = new TrieNode()
        current.children[ch] = node
      }
      current = node
    })
    current.endOfWord = true
  }
  search(word) {
    let current = this.root
    for(const ch of Array.from(word)) {
      const node = current.children[ch]
      if (!node) {
        return false
      }
      current = node
    }
    return current.endOfWord
  }
  delete(word) {
    this.deleteRecursively(this.root, word, 0)
  }
  deleteRecursively(current, word, index) {
    if (index === word.length) {
      if (!current.endOfWord) {
        return false
      }
      current.endOfWord = false
      return Object.keys(current.children).length === 0
    }
    const ch = word[index]
    const node = current.children[ch]
    if (!node) {
      return false
    }
    const shouldDeleteCurrentNode = this.deleteRecursively(node, word, index + 1)
    if (shouldDeleteCurrentNode) {
      delete current.children[ch]
      return Object.keys(current.children).length === 0
    }
    return false
  }
}

const trie = new Trie()
trie.insert('sammie')
trie.insert('simran')
console.log(trie.search('simran'))
trie.delete('sammie')
trie.delete('simran')
console.log(trie.search('sammie'))
console.log(trie.search('simran'))

 

 

OOP로 작성한 예제

class TrieNode {
  constructor() {
    this.children = new Map()
    this.endOfWord = false
  }
  addChild(key) {
    this.children.set(key, new TrieNode())
  }
  getChild(key) {
    return this.children.get(key)
  }
  removeChild(key) {
    delete this.children.delete(key)
  }
  hasChild(key) {
    return this.children.has(key)
  }
  hasChildren() {
    return !!this.children.size
  }
  isEndWord() {
    return this.endOfWord
  }
  setEndWord() {
    this.endOfWord = true
  }
  resetEndWord() {
    this.endOfWord = false
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode()
  }
  insert(word) {
    let current = this.root
    Array.from(word).forEach(ch => {
      if (!current.hasChild(ch)) {
        current.addChild(ch)
      }
      current = current.getChild(ch)
    })
    current.setEndWord()
  }
  search(word) {
    let current = this.root
    for (const ch of Array.from(word)) {
      if (!current.hasChild(ch)) {
        return false
      }
      current = current.getChild(ch)
    }
    return current.isEndWord()
  }
  delete(word) {
    this.deleteRecursively(this.root, word, 0)
  }
  deleteRecursively(current, word, index) {
    if (index === word.length) {
      if (current.isEndWord()) {
        current.resetEndWord()
        return !current.hasChildren()
      }
    } else {
      const ch = word[index]
      if (current.hasChild(ch)) {
        const shouldDeleteCurrentNode = this.deleteRecursively(
          current.getChild(ch),
          word,
          index + 1
        )
        if (shouldDeleteCurrentNode) {
          current.removeChild(ch)
          return !current.hasChildren()
        }
      }
    }
    return false
  }
}

console.group('trie-oop')
const trie = new Trie()
trie.insert('sammie')
trie.insert('simran')
trie.insert('sam')
trie.insert('sarada')
trie.insert('apple')
console.log(trie.search('simran') === true)
console.log(trie.search('sam') === true)
console.log(trie.search('sarada') === true)
console.log(trie.search('apple') === true)
trie.delete('sammie')
trie.delete('simran')
console.log(trie.search('sammie') === false)
console.log(trie.search('simran') === false)
console.groupEnd('trie-oop')

 

 

보이어-무어 문자열 검색

문자열 내에서 패턴을 검색할 때 인덱스를 건너 뜀으로써 선형 시간에 검색이 가능하다.

인덱스의 문자열이 패턴에 존재하는 경우 앞으로 건너뜀으로써 문자열 비교 횟수를 줄이는 최적화된 반복 방식을 확인 할 수 있다.

건너뛰기 규칙을 구현하기 위해 불일치 표 구조를 만들 수 있다.

 

ES6로 작성한 예제

const buildBadMatchTable = str => {
  const table = {}
  const {length} = str

  for (let i = 0; i < length - 1; i++) {
    table[str[i]] = length - 1 - i
  }

  if (table[str[length - 1]] === undefined) {
    table[str[length - 1]] = length
  }
  return table
}

console.log(
  buildBadMatchTable('data')
)
console.log(
  buildBadMatchTable('struct')
)
console.log(
  buildBadMatchTable('roi')
)
console.log(
  buildBadMatchTable('jam')
)

const boyerMoore = (str, pattern) => {
  const badMatchTable = buildBadMatchTable(str)
  let offset = 0
  let patternLastIndex = pattern.length - 1
  let scanIndex = patternLastIndex
  let maxOffset = str.length - pattern.length

  while (offset <= maxOffset) {
    scanIndex = 0
    while(pattern[scanIndex] === str[scanIndex + offset]) {
      if (scanIndex === patternLastIndex) {
        return offset
      }
      scanIndex++
    }
    const badMatchString = str[offset + patternLastIndex]
    if (badMatchTable[badMatchString]) {
      offset += badMatchTable[badMatchString]
    } else {
      offset += 1
    }
  }
  return -1
}

console.log(
  boyerMoore('jellyjam', 'jam')
)
console.log(
  boyerMoore('jellyjam', 'jelly')
)
console.log(
  boyerMoore('jellyjam', 'sam')
)

 

 

---

 

 

도서 리뷰 시리즈 - 자바스크립트로 하는 자료 구조와 알고리즘