추가 적립 안내

핵심 자료 구조 및 알고리즘을 이해하고 구현하기 위한 입문서

자료 구조와 알고리즘의 개념을 이해하고 이를 자바스크립트로 구현하기 위한 책이다. 자바스크립트 프로그래머라면 제대로 된 애플리케이션을 만들기 위해 알아야 할 핵심 자료 구조와 알고리즘을 다룬다.
해시 테이블, 연결 리스트, 큐, 트리, 그래프 등의 핵심 자료 구조와 검색, 정렬, 재귀, 동적 프로그래밍, 비트 연산 등의 핵심 알고리즘을 배우고 이를 실제 자바스크립트로 구현해본다. 이러한 과정을 통해 자료 구조와 알고리즘에 대한 이해도를 높일 수 있을 뿐만 아니라 자바스크립트 구현 능력도 키울 수 있다.

자바스크립트는 1995년 넷스케이프(NetScape)의 브렌던 아이크(Brendan Eich)가 개발했다. 넷스케이프는 역사상 첫 번째 웹 브라우저 중 하나인 넷스케이프 브라우저를 개발하던 곳이었다. 그리고 오늘날 자바스크립트는 어디서나 가장 인기 있는 프로그래밍 언어로 널리 쓰이고 있다.
예를 들어 우버(Uber)의 차량 관리 시스템은 Node.js로 초당 2백만 개 이상의 원격 프로시저 호출(RPC)을 실행하고 있다. 페이스북(Facebook)의 리액트 네이티브(React Native)는 웹과 휴대폰에 동일한 코드를 작성할 수 있도록 한다. 나사(NASA)에서도 Node.js를 사용해서 우주복 자료 시스템(spacesuit systems data)을 관리하고 있다.
실리콘밸리에서 일하며 자바스크립트의 인기가 높아지는 것을 지켜봐왔다. 자바스크립트는 4년 동안 깃허브(Github)에서 제일 인기 많은 프로그래밍 언어 중 하나다. 그리고 이제는 자바(Java)와 마찬가지로 마이크로소프트(Microsoft)의 타입스크립트(TypeScript)로 자바스크립트를 객체지향 언어처럼 사용할 수 있다. 자바스크립트는 다양하고 강력한 프로그래밍 언어이고 응용하는 데 제한이 없어 현재 그 어떤 프로그래밍 언어보다 사용하기 적절하다.

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으로 채우기
숫자 연산
- 덧셈
- 뺄셈
- 곱셈
- 나눗셈
요약

이 책을 쓰게 된 것은 자바스크립트로 작성된 자료 구조와 알고리즘에 관한 자료가 부족하기 때문이었다. 오늘날, 소프트웨어 개발과 관련한 많은 일자리가 자바스크립트 지식을 필요로 한다는 점을 고려하면 이렇게까지 자료가 부족한 것은 개인적으로 이상하다고 생각했다. 특히 자바스크립트는 프론트엔드, 모바일(네이티브, 하이브리드) 플랫폼, 백엔드를 포함해 전체 스택을 작성하는 데 사용 가능한 유일한 언어다. 자바스크립트 개발자가 자료 구조가 어떤 식으로 동작하고, 애플리케이션을 만들기 위해 알고리즘을 어떤 식으로 설계해야 할지 이해하는 것은 매우 중요하다.
따라서 이 책의 목적은 컴퓨터 과학의 자료 구조와 알고리즘 개념을 좀 더 일반적인 자바나 C++가 아닌 자바스크립트에 맞춰 알려주는 것이다. 상속 패턴을 따르는 자바와 C++와 달리, 자바스크립트는 프로토타입 활용 상속 패턴을 따르기 때문에 자바스크립트로 자료 구조를 작성할 때는 약간의 변경이 필요하다. 기존의 상속 패턴의 경우 청사진과 같은 형태를 생성해야 하며, 상속 시 객체가 해당 형태를 따라야 한다. 하지만 프로토타입 활용 상속 패턴은 객체를 복사한 다음, 해당 복사된 객체의 속성을 변경하는 것을 의미한다.
이 책은 우선 빅오(Big-O) 분석에 관한 기초적인 수학을 다룬다. 그러고 나서 기본 객체와 기본형과 같은 자바스크립트 기초를 다룬다. 그 뒤 연결 리스트와 스택, 트리, 힙, 그래프와 같은 기본적인 자료 구조에 관한 구현과 알고리즘을 알아본다. 마지막으로 효율적인 문자열 검색 알고리즘과 캐싱 알고리즘, 동적 프로그래밍 문제와 같은 고급 주제를 자세히 살펴본다.
('지은이의 말' 중에서)

HTML의 등장과 함께, 자바스크립트는 웹 브라우저 내에서 사용되는 클라이언트 사이드(client-side) 프로그래밍 언어로 많은 사랑을 받았다. 기존에 자바스크립트는 주로 웹 브라우저 내에서 사용되며 클라이언트 사이드 프로그래밍을 위해 사용됐다. 전 세계의 웹 브라우저 중 자바스크립트를 지원하지 않는 웹 브라우저를 찾기 힘들 만큼 많은 사랑을 받았다. 하지만 Node.js의 등장과 함께 최근에는 서버 사이드(server-side) 프로그래밍 언어로 많은 인기를 끌고 있으며, 모바일 앱 등의 개발에도 널리 사용되고 있다.
이렇게 자바스크립트의 활용도가 늘어나고 더 복잡한 애플리케이션 개발에 사용됨에 따라 전통적으로 자바, C++, C# 프로그래머에게 중요한 자료 구조와 알고리즘이 자바스크립트 프로그래머에게도 중요해졌다. 이 책은 이러한 흐름에 맞춰 기존 자바스크립트 프로그래머가 자료 구조와 알고리즘의 개념을 이해하고 이를 실제로 자바스크립트로 구현할 수 있도록 돕는다.
연결 리스트와 같은 기초적인 자료 구조부터 동적 프로그래밍에 이르기까지 핵심 자료 구조와 알고리즘을 다루고 있으며, 이를 실제로 자바스크립트로 구현해보고 배운 내용을 실전에서 활용할 수 있도록 구성돼 있다.
아직까지 자바스크립트로 구현한 자료 구조와 알고리즘 책이 시중에 많지 않은 상황에서 이론과 구현을 겸비한 이 책은 자바스크립트 프로그래머로서 수준을 한 단계 높이고자 하는 독자들에게 단비와 같은 책이다.
('옮긴이의 말' 중에서)