자바스크립트로 하는 자료 구조와 알고리즘(웹 프로페셔널)

자바스크립트는 1995년 넷스케이프(NetScape)의 브렌던 아이크(Brendan Eich)가 개발했다. 넷스케이프는 역사상 첫 번째 웹 브라우저 중 하나인 넷스케이프 브라우저를 개발하던 곳이었다. 그리고 오늘날 자바스크립트는 어디서나 가장 인기 있는 프로그래밍 언어로 널리 쓰이고 있다.

예를 들어 우버(Uber)의 차량 관리 시스템은 Node.js로 초당 2백만 개 이상의 원격 프로시저 호출(RPC)을 실행하고 있다. 페이스북(Facebook)의 리액트 네이티브(React Native)는 웹과 휴대폰에 동일한 코드를 작성할 수 있도록 한다. 나사(NASA)에서도 Node.js를 사용해서 우주복 자료 시스템(spacesuit systems data)을 관리하고 있다.

실리콘밸리에서 일하며 자바스크립트의 인기가 높아지는 것을 지켜봐왔다. 자바스크립트는 4년 동안 깃허브(Github)에서 제일 인기 많은 프로그래밍 언어 중 하나다. 그리고 이제는 자바(Java)와 마찬가지로 마이크로소프트(Microsoft)의 타입스크립트(TypeScript)로 자바스크립트를 객체지향 언어처럼 사용할 수 있다. 자바스크립트는 다양하고 강력한 프로그래밍 언어이고 응용하는 데 제한이 없어 현재 그 어떤 프로그래밍 언어보다 사용하기 적절하다.



★ 옮긴이의 말 ★

HTML의 등장과 함께, 자바스크립트는 웹 브라우저 내에서 사용되는 클라이언트 사이드(client-side) 프로그래밍 언어로 많은 사랑을 받았다. 기존에 자바스크립트는 주로 웹 브라우저 내에서 사용되며 클라이언트 사이드 프로그래밍을 위해 사용됐다. 전 세계의 웹 브라우저 중 자바스크립트를 지원하지 않는 웹 브라우저를 찾기 힘들 만큼 많은 사랑을 받았다. 하지만 Node.js의 등장과 함께 최근에는 서버 사이드(server-side) 프로그래밍 언어로 많은 인기를 끌고 있으며, 모바일 앱 등의 개발에도 널리 사용되고 있다.

이렇게 자바스크립트의 활용도가 늘어나고 더 복잡한 애플리케이션 개발에 사용됨에 따라 전통적으로 자바, C++, C# 프로그래머에게 중요한 자료 구조와 알고리즘이 자바스크립트 프로그래머에게도 중요해졌다. 이 책은 이러한 흐름에 맞춰 기존 자바스크립트 프로그래머가 자료 구조와 알고리즘의 개념을 이해하고 이를 실제로 자바스크립트로 구현할 수 있도록 돕는다.

연결 리스트와 같은 기초적인 자료 구조부터 동적 프로그래밍에 이르기까지 핵심 자료 구조와 알고리즘을 다루고 있으며, 이를 실제로 자바스크립트로 구현해보고 배운 내용을 실전에서 활용할 수 있도록 구성돼 있다.

아직까지 자바스크립트로 구현한 자료 구조와 알고리즘 책이 시중에 많지 않은 상황에서 이론과 구현을 겸비한 이 책은 자바스크립트 프로그래머로서 수준을 한 단계 높이고자 하는 독자들에게 단비와 같은 책이다.

지은이 소개

한국어판 출간에 부쳐

감사의 글

기술 감수자 소개

옮긴이 소개

옮긴이의 말

들어가며



1장. 빅오 표기법

__빅오 표기법 기초

____일반적인 예

__빅오 표기법 규칙

____계수 법칙: "상수를 제거하라"

____합의 법칙: "빅오를 더하라"

____곱의 법칙: "빅오를 곱하라"

____다항 법칙: "빅오의 k승"

__요약

__연습 문제

____정답



2장. 자바스크립트의 독특한 특징

__자바스크립트 범위

____전역 선언: 전역 범위

____var를 사용해 선언하기: 함수 범위

____let을 활용한 선언: 블록 범위

__등가와 형

____변수형

____참/거짓 확인

____=== 대 ==

____객체

__요약



3장. 자바스크립트 숫자

__숫자 체계

__자바스크립트 숫자 객체

____정수 반올림

____NumberEPSILON

____최대치

____최소치

____무한

____크기 순서

____숫자 알고리즘

____소인수 분해

__무작위 수 생성기

__연습 문제

__요약



4장. 자바스크립트 문자열

__자바스크립트 문자열 기본

____문자열 접근

____문자열 비교

____문자열 검색

____문자열 분해

____문자열 바꾸기

__정규 표현식

____기본 정규 표현식

____자주 사용하는 정규 표현식

____숫자를 포함하는 문자

____숫자만 포함하는 문자

____부동소수점 문자

____숫자와 알파벳만을 포함하는 문자

____질의 문자열

__인코딩

__Base64 인코딩

__문자열 단축

__암호화

____RSA 암호화

__요약



5장. 자바스크립트 배열

__배열 소개

____삽입

____삭제

____접근

__반복

____for (변수; 조건; 수정)

____for ( in )

____for ( of )

____forEach( )

__도움 함수

____slice(begin,end)

____splice(begin,size,element1,element2)

____concat( )

____length 속성

____전개 연산자

__연습 문제

__자바스크립트 함수형 배열 메소드

____map

____filter

____reduce

__다차원 배열

__연습 문제

__요약



6장. 자바스크립트 객체

__자바스크립트 객체 속성

____프로토타입 활용 상속

__생성자와 변수

__요약

__연습 문제



7장. 자바스크립트 메모리 관리

__메모리 누수

____객체에 대한 참조

____DOM 메모리 누수

____window 전역 객체

____객체 참조 제한하기

____delete 연산자

__요약

__연습 문제



8장. 재귀

__재귀 소개

__재귀의 규칙

____기저 조건

____분할 정복 방식

____대표적인 예: 피보나치 수열

____피보나치 수열: 꼬리 재귀

____파스칼의 삼각형

__재귀의 빅오 분석

____점화식

____마스터 정리

__재귀 호출 스택 메모리

__요약

__연습 문제



9장. 집합

__집합 소개

__집합 연산

____삽입

____삭제

____포함

__기타 유틸리티 함수

____교집합

____상위 집합 여부 확인

____합집합

____차집합

__요약

__연습 문제



10장. 검색과 정렬

__검색

____선형 검색

____이진 검색

__정렬

____거품 정렬

____선택 정렬

____삽입 정렬

____빠른 정렬

____빠른 선택

____병합 정렬

____계수 정렬

____자바스크립트 내장 정렬

__요약

__연습 문제



11장. 해시 테이블

__해시 테이블 소개

__해싱 기법

____소수 해싱

____탐사

____재해싱/이중 해싱

__해시 테이블 구현

____선형 탐사 사용하기

____이차 탐사 사용하기

____선형 탐사를 활용해 이중 해싱 사용하기

__요약



12장. 스택과 큐

__스택

____들여다보기

____삽입

____삭제

____접근

____검색

__큐

____들여다보기

____삽입

____삭제

____접근

____검색

__요약

__연습 문제



13장. 연결 리스트

__단일 연결 리스트

____삽입

____값에 의한 삭제

____헤드 항목 삭제

____검색

__이중 연결 리스트

____헤드에 항목 삽입하기

____테일에 항목 삽입하기

____헤드의 항목 삭제하기

____테일의 항목 삭제하기

____검색

__요약

__연습 문제



14장. 캐싱

__캐싱 이해하기

__LFU 캐싱

__LRU 캐싱

__요약



15장. 트리

__일반적인 트리 구조

__이진 트리

__트리 순회

____선순위 순회

____중순위 순회

____후순위 순회

____단계순위 순회

____트리 순회 요약

__이진 검색 트리

____삽입

____삭제

____검색

__AVL 트리

____단일 회전

____오른쪽 회전

____이중 회전

____트리 균형 잡기

____삽입

____AVL 트리 예제 종합

__요약

__연습 문제



16장. 힙

__힙에 대한 이해

____최대 힙

____최소 힙

__이진 힙 배열 인덱스 구조

____삼투: 위로 아래로 이동

____삼투 구현하기

____최대 힙 예

__최소 힙 구현 완성

__최대 힙 구현 완성

__힙 정렬

____오름차순 정렬(최소 힙)

____내림차순 정렬(최대 힙)

__요약

__연습 문제



17장. 그래프

__그래프 기본

__무지향성 그래프

____간선과 정점 추가하기

____간선과 정점 삭제하기

__지향성 그래프

__그래프 순회

____너비 우선 검색

____깊이 우선 검색

__가중치가 있는 그래프와 최단 경로

____가중치가 있는 간선을 지닌 그래프

____다익스트라의 알고리즘: 최단 경로

__위상 정렬

__요약



18장. 고급 문자열

__트라이(접두사 트리)

__보이어-무어 문자열 검색

__커누스-모리스-플랫 문자열 검색

__라빈-카프 검색

____라빈 지문

____실생활 적용 예

__요약



19장. 동적 프로그래밍

__동적 프로그래밍의 필요성

__동적 프로그래밍의 규칙

____중복 부분 문제

____최적 부분 구조

____예: 걸음 수를 채우는 방법

__대표적인 동적 프로그래밍 예

____배낭 문제 알고리즘

____최장 공통 부분 수열 알고리즘

____동전 교환 알고리즘

____편집 거리 알고리즘

__요약



20장. 비트 조작

__비트 연산자

____AND

____OR

____XOR

____NOT

____왼쪽 이동

____오른쪽 이동

____오른쪽 이동 후 0으로 채우기

__숫자 연산

____덧셈

____뺄셈

____곱셈

____나눗셈

__요약



찾아보기

배세민 옐프(Yelp)에서 근무 중인 데이터 엔지니어다. 엔비디아(NVIDIA)의 데이터 플랫폼 엔지니어링 팀에서 일한 바 있다. 스마트 테크놀로지스(SMART Technologies)에서 인턴 생활을 하면서 자바스크립트에 깊은 관심을 갖게 됐다. 스마트 테크놀로지스에서 보드 드라이버와 웹 애플리케이션 간 직렬 포트 통신을 위한 Node.js 기반 자바스크립트 API를 개발했다. 자바스크립트가 최신 소프트웨어 엔지니어링 산업에 밀접한 영향을 미침에도 이 책을 제외하고는 자바스크립트를 사용해 알고리즘과 자료 구조를 가르치는 책이 없다. 이러한 알고리즘과 자료 구조와 같은 컴퓨터 과학 개념이 얼마나 어려운지 잘 이해하고 있다. 이 책의 목표는 어려운 개념을 명확하고 간결하게 설명하는 것이다.