누구나 자료 구조와 알고리즘 개정2판
더북(TheBook)

누구나 자료 구조와 알고리즘 개정2판

사칙 연산으로 복잡한 알고리즘을 쉽게 이해해보자
수학 용어와 전문 용어가 아니어도 이해한다

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

«누구나 자료 구조와 알고리즘 개정2판»은 1~3장을 공개합니다.

목차

  • 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 연습 문제
  • 13장 속도를 높이는 재귀 알고리즘
  • 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 연습 문제
  • 16장 힙으로 우선순위 유지하기
  • 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.2 최대 부분 합
  • 20.5.3 탐욕스러운 주가 예측
  • 20.5.1 배열 최댓값
  • 20.6 자료 구조 변경
  • 20.6.1 애너그램 검사기
  • 20.6.2 그룹 정렬
  • 20.7 요약
  • 20.8 작별 인사
  • 20.9 연습 문제
  • 부록 연습 문제 해답
신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.