추가 적립 안내

사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자

수학 용어와 전문 용어가 아니어도 이해한다
이 분야의 책은 대부분 컴퓨터 공학 전공자를 대상으로 쓰였거나 고등학교 수학을 잘 안다고 가정하고 있다. 쉽게 설명했다는 책도 전문 용어로 가득하다. 비전공자나 수학적 기초가 약한 독자는 전문 용어에 두려움을 느끼며 이 주제를 이해할 만큼 자신이 똑똑하지 않다고 느끼며 이 주제를 회피한다. 그러나 자료 구조와 알고리즘은 대부분 상식선에서 이해할 수 있다. 엄밀한 수학적 분석이 아니어도 직관으로 이해할 수 있는 범위에서 상식이 통하는 설명으로 자료 구조와 알고리즘을 이해해보자.

프로그래밍의 핵심 스킬을 이해한다
자료 구조와 알고리즘은 프로그래밍의 핵심 스킬이다. 더 빠른 코드, 더 효율적인 코드를 작성하려면 반드시 알아야 하는 사고 방식이 자료 구조와 알고리즘에 담겨 있다. 추상적인 개념만 설명하는 대신 실생활에서 마주할 수 있는 상황을 제시하며 자료 구조와 알고리즘을 적용하는 방법을 보여준다. 자료 구조와 알고리즘은 개념만 이해하면 어떤 언어로도 구현할 수 있다는 것도 보여준다. 이 책에서는 자바스크립트, 루비, 파이썬으로 된 예제를 제시한다.

자료 구조와 알고리즘을 선택하는 방법을 배운다
전공 교재는 자료 구조와 알고리즘을 암기하고 시험만 볼 뿐이다. 입사 면접에서는 어떤 문제를 두고 배열, 연결 리스트, 해시 중에 무엇을 선택해야 하는지, 왜 그게 최적의 방법인지 묻는다. 자료 구조를 선택하는 방법, 선택한 자료 구조가 코드의 성능에 어떤 영향을 미치는지 설명하므로 암기된 단편적인 지식이 아닌 연결된 지식을 가르치고, 입사 면접을 준비할 때도 참고할 수 있게 했다.

2판에서 달라진 점
코딩 테스트에 출제 빈도가 높은 다이나믹 프로그래밍, 트라이(Trie)에 대한 내용을 추가로 담았다. 재귀를 사용한 재귀적 반복과 속도를 높이는 재귀 알고리즘에 더해 재귀 알고리즘을 작성하는 방법에서는 문제의 유형에 따라 재귀 알고리즘을 작성하는 방법을 장으로 추가하고 자세한 전략을 담았다. 코딩 면접에서 자주 묻는 구현 알고리즘 개선 문제에 대한 항목을 최적화 주제로 보강했고, 각 장에는 더 연습할 수 있는 문제를 추가로 수록했다.

[대상 독자]
● 이제 막 기초 프로그래밍을 배웠지만 컴퓨터 과학 기초를 배움으로써 더 나은 코드를 작성하고 프로그래밍 지식과 기술을 키우고 싶은 개발자
● 정규적인 컴퓨터 과학 수업을 받은 적이 없는 독학 개발자(또는 공부했지만 다 까먹은 개발자)면서 자료 구조와 알고리즘의 힘을 활용해 더 확장 가능하고 간결한 코드를 작성하고 싶은 개발자
● 자료 구조와 알고리즘을 쉽고 명확하게 설명한 교재를 원하는 컴퓨터 과학도. 어떤 “고전적인” 교재를 사용하든 이 책을 훌륭한 보조 교재로 사용할 수 있다.
● 경력상 활용한 적이 거의 없지만 다가올 기술 면접시험을 위해 자료 구조와 알고리즘 개념을 복습해야 하는 개발자

[관련도서]
모두의 알고리즘 with 파이썬
파이썬으로 배우는 자료 구조 핵심 원리
알고리즘(개정4판)

1장 자료 구조가 중요한 까닭
__1.1 자료 구조
__1.2 배열: 기초 자료 구조
____1.2.1 자료 구조 연산
__1.3 속도 측정
__1.4 읽기
__1.5 검색
__1.6 삽입
__1.7 삭제
__1.8 집합: 단 하나의 규칙으로 효율성이 달라진다
__1.9 마무리
__1.10 연습 문제

2장 알고리즘이 중요한 까닭
__2.1 정렬된 배열
__2.2 정렬된 배열의 검색
__2.3 이진 검색
____2.3.1 코드 구현: 이진 검색
__2.4 이진 검색 대 선형 검색
____2.4.1 깜짝 퀴즈
__2.5 마무리
__2.6 연습 문제

3장 빅 오 표기법
__3.1 빅 오: 원소가 N개일 때 몇 단계가 필요할까?
__3.2 빅 오의 본질
____3.2.1 빅 오의 본질 더 파고들기
____3.2.2 같은 알고리즘, 다른 시나리오
__3.3 세 번째 유형의 알고리즘
__3.4 로가리즘
__3.5 O(logN) 해석
__3.6 실제 예제
__3.7 마무리
__3.8 연습 문제

4장 빅 오로 코드 속도 올리기
__4.1 버블 정렬
__4.2 버블 정렬 실제로 해보기
____4.2.1 버블 정렬 구현
__4.3 버블 정렬의 효율성
__4.4 이차 문제
__4.5 선형 해결법
__4.6 마무리
__4.7 연습 문제

5장 빅 오를 사용하거나 사용하지 않는 코드 최적화
__5.1 선택 정렬
__5.2 선택 정렬 실제로 해보기
____5.2.1 선택 정렬 구현
__5.3 선택 정렬의 효율성
__5.4 상수 무시하기
__5.5 빅 오 카테고리
____5.5.1 실제 예제
____5.5.2 중요한 단계
__5.6 마무리
__5.7 연습 문제

6장 긍정적인 시나리오 최적화
__6.1 삽입 정렬
__6.2 삽입 정렬 실제로 해보기
____6.2.1 삽입 정렬 구현
__6.3 삽입 정렬의 효율성
__6.4 평균적인 경우
__6.5 실제 예제
__6.6 마무리
__6.7 연습 문제

7장 일상적인 코드 속 빅 오
__7.1 짝수의 평균
__7.2 단어 생성기
__7.3 배열 예제
__7.4 평균 섭씨 온도 구하기
__7.5 의류 상표
__7.6 1 세기
__7.7 팰린드롬 검사기
__7.8 모든 곱 구하기
____7.8.1 여러 데이터 세트 다루기
__7.9 암호 크래커
__7.10 마무리
__7.11 연습 문제

8장 해시 테이블로 매우 빠른 룩업
__8.1 해시 테이블
__8.2 해시 함수로 해싱
__8.3 재미와 이익, 특히 이익을 남길 유의어 사전 만들기
__8.4 해시 테이블 룩업
____8.4.1 단방향(one-directional) 룩업
__8.5 충돌 해결
__8.6 효율적인 해시 테이블 만들기
____8.6.1 훌륭한 충돌 조정
__8.7 해시 테이블로 데이터 조직
__8.8 해시 테이블로 속도 올리기
____8.8.1 배열 부분 집합
__8.9 마무리
__8.10 연습 문제

9장 스택과 큐로 간결한 코드 생성
__9.1 스택
__9.2 추상 데이터 타입
__9.3 스택 다뤄보기
____9.3.1 코드 구현: 스택 기반 코드 린터
__9.4 제약을 갖는 데이터 구조의 중요성
____9.4.1 스택 요약
__9.5 큐
____9.5.1 큐 구현
__9.6 큐 다뤄보기
__9.7 마무리
__9.8 연습 문제

10장 재귀를 사용한 재귀적 반복
__10.1 루프 대신 재귀
__10.2 기저 조건
__10.3 재귀 코드 읽기
__10.4 컴퓨터의 눈으로 바라본 재귀
____10.4.1 호출 스택
____10.4.2 스택 오버플로
__10.5 파일시스템 순회
__10.6 마무리
__10.7 연습 문제

11장 재귀적으로 작성하는 법
__11.1 재귀 카테고리: 반복 실행
____11.1.1 재귀 트릭: 추가 인자 넘기기
__11.2 재귀 카테고리: 계산
____11.2.1 두 가지 계산 방식
__11.3 하향식 재귀: 새로운 사고방식
____11.3.1 하향식 사고 절차
____11.3.2 배열 합
____11.3.3 문자열 뒤집기
____11.3.4 X 세기
__11.4 계단 문제
____11.4.1 계단 문제 기저 조건
__11.5 애너그램 생성
____11.5.1 애너그램 생성의 효율성
__11.6 마무리
__11.7 연습 문제

12장 동적 프로그래밍
__12.1 불필요한 재귀 호출
____12.1.1 max 재귀 분석
__12.2 빅 오를 위한 작은 개선
__12.3 재귀의 효율성
__12.4 하위 문제 중첩
__12.5 메모이제이션을 통한 동적 프로그래밍
____12.5.1 메모이제이션 구현
__12.6 상향식을 통한 동적 프로그래밍
____12.6.1 상향식 피보나치
____12.6.2 메모이제이션 대 상향식
__12.7 마무리
__12.8 연습 문제 25613장 속도를 높이는 재귀 알고리즘
__13.1 분할
____13.1.1 코드 구현: 분할
__13.2 퀵 정렬
____13.2.1 코드 구현: 퀵 정렬
__13.3 퀵 정렬의 효율성
____13.3.1 한눈에 보는 퀵 정렬
____13.3.2 빅 오로 나타낸 퀵 정렬
__13.4 퀵 정렬의 최악의 시나리오
____13.4.1 퀵 정렬 대 삽입 정렬
__13.5 퀵 셀렉트
____13.5.1 퀵 셀렉트의 효율성
____13.5.2 코드 구현: 퀵 셀렉트
__13.6 다른 알고리즘의 핵심 역할을 하는 정렬
__13.7 마무리
__13.8 연습 문제

14장 노드 기반 자료 구조
__14.1 연결 리스트
__14.2 연결 리스트 구현
__14.3 읽기
____14.3.1 코드 구현: 연결 리스트 읽기
__14.4 검색
____14.4.1 코드 구현: 연결 리스트 검색
__14.5 삽입
____14.5.1 코드 구현: 연결 리스트 삽입
__14.6 삭제
____14.6.1 코드 구현: 연결 리스트 삭제
__14.7 연결 리스트 연산의 효율성
__14.8 연결 리스트 다루기
__14.9 이중 연결 리스트
____14.9.1 코드 구현: 이중 연결 리스트 삽입
____14.9.1 앞과 뒤로 이동
__14.10 이중 연결 리스트 기반 큐
____14.10.1 코드 구현: 이중 연결 리스트 기반 큐
__14.11 마무리
__14.12 연습 문제

15장 이진 탐색 트리로 속도 향상
__15.1 트리
__15.2 이진 탐색 트리
__15.3 검색
____15.3.1 이진 탐색 트리 검색의 효율성
____15.3.2 log(N) 레벨
____15.3.3 코드 구현: 이진 탐색 트리 검색
__15.4 삽입
____15.4.1 코드 구현: 이진 탐색 트리 삽입
____15.4.2 삽입 순서
__15.5 삭제
____15.5.1 자식이 둘인 노드 삭제
____15.5.2 후속자 노드 찾기
____15.5.3 오른쪽 자식이 있는 후속자 노드
____15.5.4 완전한 삭제 알고리즘
____15.5.5 코드 구현: 이진 탐색 트리 삭제
____15.5.6 이진 탐색 트리 삭제의 효율성
__15.6 이진 탐색 트리 다뤄보기
__15.7 이진 탐색 트리 순회
__15.8 마무리
__15.9 연습 문제 34516장 힙으로 우선순위 유지하기
__16.1 우선순위 큐
__16.2 힙
____16.2.1 힙 조건
____16.2.2 완전 트리
__16.3 힙 속성
__16.4 힙 삽입
__16.5 마지막 노드 탐색
__16.6 힙 삭제
__16.7 힙 대 정렬된 배열
__16.8 다시 살펴보는 마지막 노드 문제
__16.9 배열로 힙 구현하기
____16.9.1 배열 기반 힙 순회
____16.9.2 코드 구현: 힙 삽입
____16.9.3 코드 구현: 힙 삭제
____16.9.4 대안 구현
__16.10 우선순위 큐로 쓰이는 힙
__16.11 마무리
__16.12 연습 문제

17장 트라이(trie)해 보는 것도 나쁘지 않다
__17.1 트라이
____17.1.1 트라이 노드
____17.1.2 트라이 클래스
__17.2 단어 저장
____17.2.1 별표(asterisk)의 필요성
__17.3 트라이 검색
____17.3.1 코드 구현: 트라이 검색
__17.4 트라이 검색의 효율성
__17.5 트라이 삽입
____17.5.1 코드 구현: 트라이 삽입
__17.6 자동 완성 개발
____17.6.1 단어 수집
____17.6.2 재귀 연습(walk-through)
__17.7 자동 완성 마무리
__17.8 값을 포함하는 트라이: 자동 완성 업그레이드
__17.9 마무리
__17.10 연습 문제

18장 그래프로 뭐든지 연결하기
__18.1 그래프
____18.1.1 그래프 대 트리
____18.1.2 그래프 용어
____18.1.3 기초 그래프 구현
__18.2 방향 그래프
__18.3 객체 지향 그래프 구현
__18.4 그래프 탐색
__18.5 깊이 우선 탐색
____18.5.1 깊이 우선 탐색 연습
____18.5.2 코드 구현: 깊이 우선 탐색
__18.6 너비 우선 탐색
____18.6.1 너비 우선 탐색 연습
____18.6.2 코드 구현: 너비 우선 탐색
____18.6.3 깊이 우선 탐색 대 너비 우선 탐색
__18.7 그래프 탐색의 효율성
____18.7.1 O(V + E)
__18.8 가중 그래프
____18.8.1 가중 그래프 코드
____18.8.2 최단 경로 문제
__18.9 데이크스트라의 알고리즘
____18.9.1 데이크스트라의 알고리즘 준비
____18.9.2 데이크스트라의 알고리즘 단계
____18.9.3 데이크스트라의 알고리즘 연습
____18.9.4 최단 경로 찾기
____18.9.5 코드 구현: 데이크스트라의 알고리즘
____18.9.6 데이크스트라의 알고리즘의 효율성
__18.10 마무리
__18.11 연습 문제

19장 공간 제약 다루기
__19.1 공간 복잡도의 빅 오
__19.2 시간과 공간 트레이드오프
__19.3 재귀에 숨겨진 비용
__19.4 마무리
__19.5 연습 문제

20장 코드 최적화 기법
__20.1 전제 조건: 현재 빅 오 파악하기
__20.2 시작점: 상상할 수 있는 최상의 빅 오
____20.2.1 상상의 나래 펼치기
__20.3 룩업 마법
____20.3.1 저자 룩업 마법
____20.3.2 자료 구조 추가하기
____20.3.3 두 수의 합(two-sum) 문제
__20.4 패턴 인식
____20.4.1 동전 게임
____20.4.2 예제 생성
____20.4.3 합 교환(sum swap) 문제
__20.5 탐욕 알고리즘
____20.5.1 배열 최댓값
____20.5.2 최대 부분 합
____20.5.3 탐욕스러운 주가 예측
__20.6 자료 구조 변경
____20.6.1 애너그램 검사기
____20.6.2 그룹 정렬
__20.7 요약
__20.8 작별 인사
__20.9 연습 문제

[저자 서문]
자료 구조와 알고리즘은 단순히 추상적인 개념이 아니다. 자료 구조와 알고리즘에 숙달하면 더 빠르게 실행되면서 메모리도 적게 소비하는 보다 효율적인 코드를 작성할 수 있다. 이는 모바일 플랫폼으로 넘어가며 갈수록 증가하는 데이터 크기를 감당해야 하는 오늘날의 소프트웨어 애플리케이션에서 특히 중요하다.
문제는 이러한 주제를 다루는 자료가 대부분 이해하기 어렵게 쓰였다는 점이다. 글은 수학 용어로 가득 차 있고 수학자가 아닌 이상 도무지 무슨 말인지 알기 어렵다. 심지어 “쉬운” 알고리즘을 표방하는 책마저 독자가 수학 석박사 학위를 취득했다고 가정한다. 결국, 무수한 독자들이 자신은 이러한 개념을 이해할 만큼 충분히 “똑똑하지” 않다고 생각하며 회피한다.
하지만 자료 구조와 알고리즘은 전부 본질적으로 상식선에서 이해할 수 있다. 수학 표기는 그저 특수한 언어이며, 어떤 수학이든 상식적인 용어로 설명할 수 있다. 이 책은 이러한 상식적인 언어로(더불어 많은 그림으로!) 개념을 단순하고 또 단언하건대 재미있게 설명한다.
자료 구조와 알고리즘을 이해했다면 효율적이고 빠르고 간결한 코드를 작성할 준비가 된 것이다. 여러 코드 대안의 장단점을 비교할 수 있으며, 지식을 바탕으로 주어진 상황에 어떤 코드가 가장 알맞은지 결정할 수 있다.
이 책에서는 오늘 바로 활용할 수 있는 아이디어를 엄선해서 개념을 실제적이고 실용적으로 만들고자 각별히 노력했다. 물론 그 과정에서 아주 근사한 컴퓨터 과학도 배운다. 하지만 이 책은 겉보기에는 추상적인 내용을 바로 실행할 수 있게 만드는 책이다. 끝까지 읽으면 더 뛰어난 코드, 더 빠른 소프트웨어를 작성하게 될 것이다.
_제이 웬그로우

[역자 서문]
자료 구조와 알고리즘은 모든 컴퓨터 공학 교육과정에서 가장 기본적으로 다루는 과목입니다. 하지만 기초를 쌓는 단계임에도 처음 접하는 학생은 누구나 당혹스러움을 감추지 못합니다. 생소한 용어와 난해한 개념, 아리송한 기호 속에서 헤매다가 무엇을 위해 무엇을 배우고 있는지 모르는 채 한 학기가 끝납니다.

이렇게 되면 실제 개발과 이론 간 큰 공백이 생깁니다. 어렵게 배운 내용을 실용적으로 써보지도 못할뿐더러 다른 사람이 작성한 코드를 이해하고 분석하는 데도 한계가 있습니다. 훌륭한 프로그래머가 되려면 문법과 API만 꿰뚫어서는 부족합니다. 어떤 운영 체제에서 어떤 프로그래밍 언어를 사용하든 좋은 프로그램은 항상 적절한 자료 구조와 효율적인 알고리즘을 바탕으로 합니다. 필요할 때마다 관련 책이나 웹 페이지만 뒤적여서는 실력을 쌓기 어렵습니다.

이 책의 저자가 밝혔듯이 자료 구조와 알고리즘은 전혀 어렵지 않습니다. 이 책처럼 얼마든지 재미있고 이해하기 쉽게 설명될 수 있습니다. 복잡한 수학 개념이 아니라 이미 알고 있는 지식과 자세한 예제면 충분합니다. 이 책은 비전공자도 쉽게 따라갈 수 있는 설명과 구성으로 핵심 개념을 소개합니다.

특히 개정판에서는 매 장에 연습 문제를 덧붙여 실제 문제를 해결해 보는 기회를 제공합니다. 더불어 널리 알려진 문제에 빅 오 카테고리를 적용해 보고, 1판보다 더욱 다양한 문제를 활용해 재귀적으로 작성하는 법을 단계적으로 설명합니다. 이 밖에도 동적 프로그래밍과 힙/트라이, 코드 최적화 기법까지 그 범위를 넓혔습니다.

이 책은 자료 구조와 알고리즘을 실제 개발에 적용해서 더욱더 효과적이고 간결한 코드를 작성할 수 있도록 도와줍니다. 초심자라면 심화 과정을 듣기 전에 기초를 다지기 좋고, 숙련된 개발자라면 가볍게 되새기기 좋은 책입니다. 목차를 한 번 읽어보세요. 그리고 흥미가 생기는 페이지로 가보세요. “누구나” 이해할 수 있습니다.
_심지현