책소개
이 책은 코딩 인터뷰(Coding Interview)를 준비하는 사람들을 위해 문제 모음과 이에 대한 전략적인 해결 방법을 소개하는 트레이닝 가이드북이다. 코딩 인터뷰는 주어진 문제를 해결하는 능력을 테스트하는 수단으로서 알고리즘 경시대회는 물론 SW 기업에서도 지원자의 문제 해결 역량을 테스트하는 척도로 도입하는 추세이다.
이 책은 프로그래밍 기초 개념부터 시작해 복잡도 표기법과 성장률 등등의 알고리즘의 기초 개념, 그리고 스택과 큐, 연결 리스트, 트리와 힙, 그래프에서부터 정렬과 선택, 분할 정복, 동적 계획법 까지 자료구조와 알고리즘 분야에서 자주 출제되거나 질문으로 물어보는 문제들을 소개하면서 이에 대한 해결 방법들도 자세하게 다루고 있다.
책 마지막 부분에는 면접 시 예상 질문과 최적의 해답, 그리고 네트워크, 데이터베이스 같은 주요 IT 기술 개념들을 소개하면서 코딩 인터뷰나 실무 테스트를 준비하는 독자들에게 문제 해결력과 논리력, 자신감을 단련시킬 수 있도록 폭넑고 다양한 주제를 다루었다.
목차
Chapter 01. 프로그래밍 기초
1.1 변수(Variables)
1.2 자료형(Data Types)
1.3 자료 구조(Data Structure)
1.4 추상 자료형(Abstract Data Types - ADTs)
1.5 메모리와 변수 (Memory and Variables)
1.6 포인터(Pointers)
1.7 파라미터 전달 기법(Parameter Passing Techniques)
1.8 바인딩(Binding)
1.9 스코프(Scope)
1.10 기억 영역 분류(Storage Classes)
1.11 기억 영역의 구성(Storage Organization)
1.12 프로그래밍 테크닉
1.13 프로그래밍 기초 문제
Chapter 02. INTRODUCTION
2.1 알고리즘이란 무엇인가?
2.2 왜 알고리즘 분석인가?
2.3 알고리즘 분석의 목표
2.4 실행 시간 분석(Running Time Analysis)이란 무엇인가?
2.5 어떻게 알고리즘을 비교하는가?
2.6 성장률(Rate of Growth)이란 무엇인가?
2.7 일반적으로 사용되는 성장률
2.8 분석 유형
2.9 점근적 표기(Asymptotic Notation)
2.10 Big-O 표기법(Big-O Notation)
2.11 Omega-Ω (빅오메가) 표기법
2.12 Theta-θ(빅세타) 표기법
2.13 왜 점근 분석(Asymptotic Analysis)이라고 불리는가?
2.14 점근 분석(Asymptotic Analysis) 지침
2.15 표기법의 속성(Properties of Notation)
2.16 흔히 사용되는 로그와 합산
2.17 분할 정복(Divide and Conquer)에 대한 마스터 정리(Master Theorem)
2.18 감산 정복 반복(Subtract and Conquer Recurrences)에 대한 마스터 정리
2.19 감산 정복(Subtract and Conquer) 마스터 정리의 변형
2.20 알고리즘 분석 문제
Chapter 03. 재귀와 역추적
3.1 소개
3.2 재귀(Recursion)란 무엇인가?
3.3 왜 재귀 방식인가?
3.4 재귀 함수의 형식
3.5 재귀와 메모리(Visualization)
3.6 재귀 vs 반복
3.7 재귀 방식에 대한 참고사항
3.8 재귀 알고리즘의 예
3.9 재귀 방식의 문제
3.10 역추적이란 무엇인가?
3.11 역추적 알고리즘의 예
3.12 역추적 문제
Chapter 04. 연결 리스트
4.1 연결 리스트란 무엇인가?
4.2 연결 리스트 추상 데이터 형(ADT)
4.3 왜 연결 리스트인가?
4.4 배열의 개요
4.5 배열과 동적 배열 그리고 연결 리스트 비교
4.6 단일 연결 리스트(Singly Linked List)
4.7 이중 연결 리스트 (Doubly Linked List)
4.8 환형(또는 환상) 연결 리스트
4.9 메모리 최적화(Memory-Efficient) 이중 연결 리스트
4.10 연결 리스트 문제
Chapter 05. 스택
5.1 스택이란 무엇인가?
5.2 스택은 어떻게 사용하는가?
5.3 스택 추상 자료형(ADT)
5.4 어플리케이션
5.5 구현
5.6 구현 비교
5.7 스택의 문항
Chapter 06. 큐
6.1 큐란 무엇인가?
6.2 큐는 어떻게 사용하는가?
6.3 큐의 추상 자료형(ADT)
6.4 예외
6.5 어플리케이션
6.6 구현
6.7 큐 관련 문항
Chapter 07. 트리
7.1 트리란 무엇인가?
7.2 용어 정의
7.3 이진 트리(Binary 트리)
7.4 이진 트리의 유형
7.5 이진 트리의 속성
7.6 이진 트리 운행(Traversals)
7.7 일반적인 트리 (N항 Trees)
7.8 스레드 이진 트리 운행 [Stack or Queue less Traversals]
7.9 수식 트리
7.10 XOR 트리
7.11 이진 탐색 트리(Binary Search Trees - BSTs)
7.12 균형 이진 검색 트리(Balanced Binary Search Trees)
7.13 AVL(Adelson-Velskii and Landis) 트리
7.14 그밖에 다양한 트리
Chapter 08. 우선 순위 큐와 힙
8.1 우선 순위 큐란 무엇인가?
8.2 우선 순위 큐 추상화 타입(Priority Queue ADT)
8.3 우선 순위 큐 응용프로그램들
8.4 우선 순위 큐 구현
8.5 힙과 이진 힙
8.6 이진 힙(Binary Heap)
8.7 우선 순위 큐와 힙 관련 문항들
Chapter 09. 그래프 알고리즘
9.1 소개
9.2 용어 설명
9.3 그래프 어플리케이션
9.4 그래프의 표현
9.5 그래프 운행(Graph Traversals)
9.6 위상 정렬(Topological Sort)
9.7 최단 경로(Shortest path) 알고리즘
9.8 최소 신장 트리
9.9 그래프 알고리즘의 문항들
Chapter 10. 정렬
10.1 정렬이란?
10.2 왜 정렬이 중요한가?
10.3 분류
10.4 그외 분류들
10.5 버블 정렬
10.6 선택 정렬(Selection sort)
10.7 삽입 정렬(Insertion sort)
10.8 셸 정렬(Shell sort)
10.9 병합 정렬(Merge sort)
10.10 힙 정렬
10.11 퀵 정렬
10.12 트리 정렬(Tree Sort)
10.13 선형 정렬 알고리즘
10.14 계수 정렬(Counting Sort)
10.15 버킷 정렬(Bucket sort 또는 Bin sort)
10.16 기수 정렬(Radix Sort)
10.17 토폴로지 정렬(Topological Sort)
10.18 외부 정렬(External Sorting)
10.19 정렬에 관한 문항들
Chapter 11. 검색
11.1 검색이란?
11.2 왜 검색인가?
11.3 검색의 종류
11.4 불규칙 선형 검색 (Unordered Linear Search)
11.5 정렬/규칙 선형 검색(Sorted/Ordered Linear Search)
11.6 이진 검색(Binary Search)
11.7 기본 검색 알고리즘 비교
11.8 심볼 테이블과 해싱
11.9 문자열 검색 알고리즘
11.10 검색 관련 문항들
Chapter 12. 선택 알고리즘
12.1 선택 알고리즘이란 무엇인가?
12.2 정렬에 의한 선택
12.3 분할 기반 선택(Partition-based Selection) 알고리즘
12.4 선형 선택(Linear Selection) 알고리즘
12.5 정렬 순번으로 K번째로 작은 요소 찾기
12.6 선택 알고리즘에 관한 문항들
Chapter 13. 심볼 테이블
13.1 개요
13.2 심볼 테이블이란 무엇인가?
13.3 심볼 테이블 구현
13.4 심볼 테이블 구현 방법의 비교
Chapter 14. 해싱
14.1 해싱(Hashing)이란 무엇인가?
14.2 해싱을 왜 사용하는가?
14.3 해시 테이블(Hash Table) ADT
14.4 해싱 알아보기
14.5 해싱 구성 요소
14.6 해시 테이블
14.7 해시 함수
14.8 적재 인수
14.9 충돌
14.10 충돌 제거 기법(Collision Resolution Techniques)
14.11 Separate Chaining
14.12 개방 주소법
14.13 충돌 해소 방법 비교
14.14 연산 복잡도 O(1)인 해싱 만드는 방법
14.15 해싱 기법(들)
14.16 해시 테이블이 적합하지 않는 경우들
14.17 해싱 문제
Chapter 15. 문자열 알고리즘
15.1 개요
15.2 문자열 매칭 알고리즘
15.3 전수 방법(Brute Force Method)
15.4 Robin-Karp 문자열 매칭 알고리즘
15.5 유한 오토마타로 문자열 매칭
15.6 KMP 알고리즘
15.7 보이어-무어(Boyer-Moore) 알고리즘
15.8 문자열 정렬을 위한 자료 구조
15.9 문자열에 대한 해시 테이블
15.10 문자열에 대한 이진 검색 트리
15.11 트라이
15.12 3항 검색 트리(Ternary Search Tree)
15.13 BST, Trie 그리고 TST 비교
15.14 접미사 트리
15.15 문자열 관련 문항들
Chapter 16. 알고리즘 디자인 기술
16.1 개요
16.2 분류
16.3 구현 방법에 따른 분류
16.4 디자인 방법에 의한 분류
16.5 다른 분류들
Chapter 17. 탐욕 알고리즘
17.1 소개
17.2 탐욕 전략(Greedy strategy)
17.3 탐욕 알고리즘의 특성
17.4 탐욕 알고리즘이 항상 올바르게 동작할 수 있을까?
17.5 탐욕 알고리즘의 장점과 단점
17.6 탐욕 응용 어플리케이션
17.7 탐욕 기술 이해하기
17.8 탐욕 알고리즘의 문항들
Chapter 18. 분할 정복 알고리즘
18.1 소개
18.2 분할과 정복 전략은 무엇입니까?
18.3 분할 정복은 항상 적용할 수 있습니까?
18.4 분할 정복 시각화
18.5 분할 정복 이해하기
18.6 분할 정복의 장점
18.7 분할 정복의 단점
18.8 마스터 정리
18.9 분할 정복의 응용
18.10 분할 정복 관련 문항들
Chapter 19. 동적 계획법
19.1 소개
19.2 동적 계획 전략이란 무엇인가?
19.3 동적 계획법 전략의 특성
19.4 동적 계획법으로 모든 문제를 풀 수 있을까?
19.5 동적 계획법 접근 방법들
19.6 동적 계획법 알고리즘의 예제들
19.7 동적 계획법의 이해
19.8 동적 프로그래밍에 관련한 문항들
Chapter 20. 복잡도 클래스
20.1 개요
20.2 다차 / 지수 시간
20.3 결정(Decision)문제란 무엇인가?
20.4 결정 절차
20.5 복잡도 클래스란 무엇인가?
20.6 복잡도 클래스의 유형
20.7 환산(Reductions)
Chapter 21. 디자인(설계) 인터뷰 질문들
21.1 용어
21.2 팁(Tips)
21.3 디자인(설계) 면접 문항들
21.4 연습을 위한 디자인 관련 질문 예제
Chapter 22. 운영체제 시스템 개념
22.1 용어
22.2 운영체제 개념 관련 문항들
Chapter 23. 컴퓨터 네트워크 기본
23.1 개요
23.2 LAN 대 WAN
23.3 분할과 다중화
23.4 단말 장치
23.5 중계 장치
23.6 매체(Medium)
23.7 P2P(Peer-to-peer)과 클라이언트/서버(Client/Server) 네트워크
23.8 인터넷은 어떻게 작동하는가?
23.9 OSI 모델과 TCP/IP 모델의 차이
23.10 클라이언트 서버 컴퓨팅과 인터넷
23.11 ARP와 RARP
23.12 부분망 구성(Subnetting)
23.13 라우팅(Routing)은 어떻게 동작할까?
23.14 유니캐스트, 브로드캐스트 그리고 멀티캐스트
23.15 경로 추적(Traceroute 혹은 Tracert)와 핑(ping)은 어떻게 동작할까?
23.16 QoS란 무엇인가?
Chapter 24. 데이터베이스 개념
24.1 용어
24.2 데이터베이스 개념의 문항들
Chapter 25. 대답하기 어려운 문제들
25.1 대답하기 어려운 문제들
Chapter 26. 기술 이외의 조언
26.1 팁
26.2 기술 외의 예제 문항들
Chapter 27. 그밖의 개념들
27.1 개요
27.2 비트 연산 파헤치기
27.3 기타 프로그래밍 문항들
