도서 리뷰 시리즈 - 자바스크립트로 하는 자료 구조와 알고리즘
출처
『자바스크립트로 하는 자료 구조와 알고리즘』 배세민 저/김무항 역 | 에이콘출판사 | 2019년 08월 30일
한 줄 리뷰
자바스크립트로 자료 구조와 알고리즘을 쉽게 학습해 볼 수 있는 도서
9장 집합
- 가장 근간이 된 자료 구조 중 하나
- 유한하고 구분되는 객체들의 그룹
- 정렬되지 않는 유일한 항목들의 그룹
js
const set = new Set();
set.add(1);
set.delete(1);
set.add(2);
console.log(set.has(1), set.has(2)); // false true교집합
js
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}합집합
js
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}차집합
js
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로 작성한 예제
js
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로 작성한 예제
js
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로 작성한 예제
js
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')
)