• 컴퓨터/IT > 컴퓨터공학 > 알고리즘/자료구조

2020/9 컴퓨터/IT 100위 | 현재 컴퓨터/IT 100위 |

출판사 리뷰

지은이의 말 ★

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

★ 옮긴이의 말 ★

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

1장. 빅오 표기법
빅오 표기법 기초
일반적인 예
빅오 표기법 규칙
계수 법칙: “상수를 제거하라”
합의 법칙: “빅오를 더하라”
곱의 법칙: “빅오를 곱하라”
다항 법칙: “빅오의 k승”
요약
연습 문제
정답

2장. 자바스크립트의 독특한 특징
자바스크립트 범위
전역 선언: 전역 범위
var를 사용해 선언하기: 함수 범위
let을 활용한 선언: 블록 범위
등가와 형
변수형
참/거짓 확인
\u003d\u003d\u003d 대 \u003d\u003d
객체
요약

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