안내
확인
U
회원관리
로그인
가입
찾기
회원아이디
패스워드
로그인유지
회원아이디
이름
이메일
휴대폰번호
패스워드
패스워드 재입력
회원이용약관 및 개인정보 취급방침에 동의 합니다
회원이용약관 보기
개인정보처리방침 보기
본인 이름 입력
회원가입시 이메일 입력
자료구조 기초 가이드: 이 책 한 권이면 끝!
3. 시간 복잡도와 공간 복잡도의 이해
와이웨이브이퍼블리싱
|
박빈
|
2025-02-03
13
읽음
0
0
0
8 / 206 목차보기
이전
8 / 206 목차
다음
로그인
회원가입
와
와이드웨이브
저자소개
서평
출판사평
Chapter 1: 자료구조란 무엇인가?
1. 자료구조의 개념과 필요성
자료구조가 중요한 이유
2. 자료구조 vs 알고리즘
3. 시간 복잡도와 공간 복잡도의 이해
시간 복잡도 (Time Complexity)
공간 복잡도 (Space Complexity)
4. 자료구조 선택의 중요성
결론
Chapter 2: 배열(Array)과 연결 리스트(Linked List)
1. 배열의 기본 개념과 특징
배열의 특징
배열 예제 (Python)
2. 배열의 시간 복잡도 (검색, 삽입, 삭제)
삽입/삭제 예제
3. 동적 배열(Dynamic Array)과 메모리 할당
동적 배열 예제
4. 단일 연결 리스트(Singly Linked List)
단일 연결 리스트의 구조
단일 연결 리스트 예제 (Python)
5. 이중 연결 리스트(Doubly Linked List)
이중 연결 리스트 예제
6. 원형 연결 리스트(Circular Linked List)
원형 연결 리스트 특징
7. 연결 리스트 vs 배열 (장단점 비교)
Chapter 3: 스택(Stack)과 큐(Queue)
1. 스택(Stack)의 개념과 동작 원리 (LIFO)
스택의 주요 연산
스택의 시각적 동작
2. 스택의 구현 (배열 vs 연결 리스트)
배열을 이용한 스택 구현 (Python)
연결 리스트를 이용한 스택 구현
3. 스택의 활용 (재귀 호출, 괄호 검사, 백트래킹)
1) 재귀 호출 (Recursion)
2) 괄호 검사 (Valid Parentheses)
4. 큐(Queue)의 개념과 동작 원리 (FIFO)
큐의 주요 연산
5. 큐의 구현 (배열 vs 연결 리스트)
배열을 이용한 큐 구현
연결 리스트를 이용한 큐 구현
6. 원형 큐(Circular Queue)와 덱(Deque)의 개념
원형 큐 (Circular Queue)
덱 (Deque, Double-ended Queue)
7. 큐의 활용 (프로세스 스케줄링, 데이터 버퍼)
1) 프로세스 스케줄링
2) 데이터 버퍼
결론
Chapter 4: 해시 테이블(Hash Table)
1. 해시 테이블의 개념과 원리
해시 테이블의 주요 특징
해시 테이블 예제 (Python 내장 딕셔너리 활용)
2. 해시 함수(Hash Function)와 충돌 해결 방법
해시 함수(Hash Function)
충돌 해결 방법
1) 체이닝(Chaining)
2) 개방 주소법(Open Addressing)
체이닝 방식 해시 테이블 구현 (Python)
3. 개방 주소법(Open Addressing) vs 체이닝(Chaining)
개방 주소법 – 선형 탐사(Linear Probing) 구현
4. 해시 테이블의 성능 분석 (충돌 발생 확률, 해시 분포)
충돌 발생 확률 (Load Factor)
해시 분포
5. 해시 테이블의 활용 (캐싱, 데이터 검색, 암호화)
1) 캐싱(Caching)
2) 데이터 검색 및 색인
3) 암호화 및 보안
간단한 캐싱 시스템 구현 (LRU Cache)
결론
Chapter 5: 트리(Tree) 자료구조 기초
1. 트리의 개념과 기본 용어 (루트, 부모, 자식, 리프)
트리의 기본 용어
트리 예시
2. 이진 트리(Binary Tree)의 구조
이진 트리의 특징
이진 트리 구현 (Python)
3. 이진 탐색 트리(BST)의 원리와 활용
BST의 특징
BST의 활용
BST 삽입 연산 구현
4. 트리의 순회 방법 (전위, 중위, 후위 순회)
1) 전위 순회 (Preorder Traversal)
2) 중위 순회 (Inorder Traversal)
3) 후위 순회 (Postorder Traversal)
트리 순회 구현 (Python)
5. 트리의 응용 (파일 시스템, 게임 AI)
1) 파일 시스템
2) 게임 AI (Minimax 알고리즘)
Minimax 알고리즘 예제
결론
Chapter 6: 균형 트리(Balanced Tree)
1. 균형 트리의 필요성 (BST의 문제점)
BST의 문제점
2. AVL 트리: 균형 유지 원리와 회전 연산
AVL 트리의 특징
AVL 트리의 회전 연산
AVL 트리 구현 (Python)
3. 레드-블랙 트리(Red-Black Tree)의 특징과 활용
레드-블랙 트리의 특징
레드-블랙 트리 활용
4. B-트리(B-Tree)와 B+ 트리의 개념과 데이터베이스 활용
B-트리의 특징
B+ 트리(B+ Tree)
B-트리와 B+ 트리 비교
B-트리 삽입 연산 예제
B+ 트리의 활용 예시
결론
Chapter 7: 그래프(Graph) 자료구조
1. 그래프의 기본 개념 (정점, 간선, 방향성)
그래프의 구성 요소
그래프 예시
2. 그래프 표현 방법 (인접 행렬 vs 인접 리스트)
1) 인접 행렬 (Adjacency Matrix)
2) 인접 리스트 (Adjacency List)
3. 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)
DFS (깊이 우선 탐색)
BFS (너비 우선 탐색)
4. 최단 경로 알고리즘 (다익스트라, 플로이드-워셜)
다익스트라(Dijkstra) 알고리즘
플로이드-워셜(Floyd-Warshall) 알고리즘
5. 최소 신장 트리(MST) 알고리즘 (크루스칼, 프림)
크루스칼(Kruskal) 알고리즘
프림(Prim) 알고리즘
6. 그래프의 활용 (소셜 네트워크 분석, 추천 시스템)
소셜 네트워크 분석
추천 시스템
결론
Chapter 8: 우선순위 큐(Priority Queue)와 힙(Heap)
1. 우선순위 큐의 개념과 활용
우선순위 큐의 활용
우선순위 큐 구현 (Python heapq 사용)
2. 힙(Heap)의 개념과 동작 원리
힙의 특징
힙의 주요 연산
3. 최소 힙(Min-Heap)과 최대 힙(Max-Heap)
1) 최소 힙(Min-Heap)
2) 최대 힙(Max-Heap)
4. 힙 정렬(Heap Sort) 알고리즘
힙 정렬의 특징
힙 정렬 구현 (Python)
5. 우선순위 큐의 활용 (스케줄링, 네트워크 패킷 관리)
1) 스케줄링 (Task Scheduling)
2) 네트워크 패킷 관리 (Packet Scheduling)
결론
Chapter 9: 탐색(Search)과 정렬(Sorting)
1. 선형 탐색(Linear Search)과 이진 탐색(Binary Search)
선형 탐색(Linear Search)
이진 탐색(Binary Search)
2. 정렬 알고리즘 개요 및 시간 복잡도 분석
3. 기본 정렬 알고리즘 (버블 정렬, 선택 정렬, 삽입 정렬)
버블 정렬(Bubble Sort)
선택 정렬(Selection Sort)
삽입 정렬(Insertion Sort)
4. 고급 정렬 알고리즘 (퀵 정렬, 병합 정렬, 힙 정렬)
퀵 정렬(Quick Sort)
병합 정렬(Merge Sort)
5. 정렬 알고리즘의 실제 활용 (데이터 분석, 데이터베이스)
결론
Chapter 10: 고급 자료구조
1. 트라이(Trie) 자료구조와 문자열 탐색
트라이의 특징
트라이 구현 (Python)
2. 분할 상환 분석(Amortized Analysis) 개념
대표적인 예: 동적 배열(Dynamic Array) 크기 조정
3. 스킵 리스트(Skip List)의 원리와 활용
스킵 리스트의 특징
스킵 리스트 구현 (Python)
4. 페르시아노 트리(Fibonacci Heap)의 개념
특징
5. 퍼시스턴트 자료구조(Persistent Data Structures)
활용
결론
Chapter 11: 실전 프로젝트 - 자료구조 적용하기
1. 대규모 데이터 처리에서 자료구조 선택하기
자료구조 선택 기준
대규모 데이터 처리 예제: 로그 파일 분석
2. 실전 문제 풀이 (코딩 테스트 및 백준, 프로그래머스 활용)
자주 등장하는 문제 유형 및 추천 자료구조
실전 예제: 괄호 검사 문제 (백준 유형)
3. 자료구조 기반 알고리즘 최적화
최적화 기법
최적화 예제: 중복 요소 제거 (해시 테이블 활용)
최적화 예제: 이진 탐색을 이용한 탐색 성능 향상
4. 자료구조와 객체지향 프로그래밍(OOP) 결합
객체지향 프로그래밍과 자료구조 결합
결론
Chapter 12: 자료구조 인터뷰 대비 및 실무 활용
1. IT 기업 코딩 인터뷰에서 나오는 자료구조 문제 유형
주요 자료구조 및 관련 문제 유형
예제 문제: 두 수의 합(Two Sum)
2. 자료구조 문제 해결 전략 및 패턴
1) 슬라이딩 윈도우 (Sliding Window)
2) 이진 탐색 (Binary Search)
3) 그리디 알고리즘 (Greedy Algorithm)
3. 실무에서의 자료구조 선택과 트레이드오프
자료구조 선택 가이드
실무 활용 사례
4. 빅데이터, AI, 블록체인에서 활용되는 자료구조
빅데이터
AI 및 머신러닝
블록체인
Merkle Tree 구현 예제
결론
판 권