Chapter 00 알아두면 쓸 데 있는 자료구조와 알고리즘 _0.1 자료구조 _0.2 알고리즘 _0.3 C 언어로 메모리를 다루는 방법 __0.3.1 포인터 복습 __0.3.2 구조체 복습 __0.3.3 메모리 레이아웃 복습 __0.3.4 스택에서 데이터를 다루는 방법 __0.3.5 힙에서 데이터를 다루는 방법
Part 01 자료구조 Chapter 01 리스트 _1.1 리스트 ADT __1.1.1 리스트의 개념 __1.1.2 리스트와 배열 비교 _1.2 링크드 리스트 __1.2.1 링크드 리스트의 노드 표현 __1.2.2 링크드 리스트의 주요 연산 ___Vitamin Quiz 1-1 __1.2.3 링크드 리스트 예제 프로그램 __1.2.4 링크드 리스트의 장단점 ___Vitamin Quiz 1-2 _1.3 더블 링크드 리스트 __1.3.1 더블 링크드 리스트의 주요 연산 __1.3.2 더블 링크드 리스트 예제 프로그램 ___Vitamin Quiz 1-3 _1.4 환형 링크드 리스트 __1.4.1 환형 더블 링크드 리스트의 주요 연산 __1.4.2 환형 더블 링크드 리스트 예제 프로그램 _연습문제
Chapter 02 스택 _2.1 스택 ADT __2.1.1 스택의 개념 ___Vitamin Quiz 2-1 __2.1.2 스택의 핵심 기능: 삽입과 제거 연산 _2.2 배열로 구현하는 스택 __2.2.1 배열 기반 스택과 스택의 노드 표현 __2.2.2 배열 기반 스택의 기본 연산 __2.2.3 배열 기반 스택 예제 프로그램 ___Vitamin Quiz 2-2 _2.3 링크드 리스트로 구현하는 스택 __2.3.1 링크드 리스트 기반 스택과 스택의 노드 표현 __2.3.2 링크드 리스트 기반 스택의 기본 연산 __2.3.3 링크드 리스트 기반 스택 예제 프로그램 _2.4 스택의 응용: 사칙 연산 계산기 __2.4.1 수식의 중위 표기법과 후위 표기법 __2.4.2 후위 표기식을 계산하는 알고리즘 __2.4.3 중위 표기식을 후위 표기식으로 바꾸는 알고리즘 __2.4.4 사칙 연산 계산기 예제 프로그램 _연습문제
Chapter 03 큐 _3.1 큐 ADT __3.1.1 큐의 개념 __3.1.2 큐 ADT의 핵심 기능: 삽입과 제거 연산 _3.2 순환 큐 __3.2.1 공백 상태와 포화 상태 __3.2.2 순환 큐의 기본 연산 __3.2.3 순환 큐 예제 프로그램 _3.3 링크드 큐 __3.3.1 링크드 큐의 기본 연산 __3.3.2 링크드 큐 예제 프로그램 _연습문제
Chapter 04 트리 _4.1 트리 ADT __4.1.1 트리의 개념 __4.1.2 트리의 구성 요소 __4.1.3 트리 표현 방법 __4.1.4 노드 표현 방법 __4.1.5 트리의 기본 연산 __4.1.6 트리 예제 프로그램 ___Vitamin Quiz 4-1 _4.2 이진 트리 __4.2.1 이진 트리의 종류 __4.2.2 이진 트리의 순회 __4.2.3 이진 트리의 기본 연산 __4.2.4 이진 트리 예제 프로그램 _4.3 수식 트리 __4.3.1 수식 트리 구축 방법 __4.3.2 수식 트리의 구현 __4.3.3 수식 트리 예제 프로그램 _4.4 분리 집합 __4.4.1 분리 집합 표현 __4.4.2 분리 집합의 기본 연산 __4.4.3 분리 집합 예제 프로그램 _연습문제
Part 02 알고리즘 Chapter 05 정렬 _5.1 정렬 알고리즘의 개요 _5.2 버블 정렬 __5.2.1 버블 정렬의 성능 측정 __5.2.2. 버블 정렬 예제 프로그램 ___Vitamin Quiz 5-1 _5.3 삽입 정렬 __5.3.1 삽입 정렬의 성능 측정 __5.3.2 삽입 정렬 예제 프로그램 _5.4 퀵 정렬 __5.4.1 퀵 정렬 사용 전 해결해야 하는 2가지 문제 __5.4.2 퀵 정렬 예제 프로그램 __5.4.3 퀵 정렬의 성능 측정 _5.5 C 언어 표준 라이브러리의 퀵 정렬 함수: qsort( ) __5.5.1 qsort( ) 함수 예제 프로그램 ___Vitamin Quiz 5-2 __5.5.2 qsort( ) 응용 문제 _연습문제
Chapter 06 탐색 _6.1 탐색 알고리즘의 개요 _6.2 순차 탐색 __6.2.1 전진 이동법 ___Vitamin Quiz 6-1 __6.2.2 전위법 ___Vitamin Quiz 6-2 __6.2.3 계수법 ___Vitamin Quiz 6-3 _6.3 이진 탐색 __6.3.1 이진 탐색의 성능 측정 __6.3.2 이진 탐색의 구현 __6.3.3 이진 탐색 예제 프로그램: 두 번째 최종 시험 문제 __6.3.4 C 언어 표준 라이브러리의 이진 탐색 함수: bsearch( ) __6.3.5 bsearch( ) 함수 예제 프로그램 _6.4 이진 탐색 트리 __6.4.1 이진 탐색 트리 표현 __6.4.2 이진 탐색 트리의 기본 연산 __6.4.3 이진 탐색 트리 예제 프로그램 __6.4.4 이진 탐색 트리의 문제점 _6.5 레드 블랙 트리 __6.5.1 레드 블랙 트리의 구현 규칙 __6.5.2 레드 블랙 트리의 기본 연산 __6.5.3 레드 블랙 트리 예제 프로그램 _연습문제
Chapter 08 해시 테이블 _8.1 해시 테이블의 개요 __8.1.1 해시 __8.1.2 해시 테이블 _8.2 해시 함수 __8.2.1 나눗셈법 __8.2.2 자릿수 접기 __8.2.3 해시 함수의 한계: 충돌 _8.3 충돌 해결 기법 __8.3.1 체이닝 __8.3.2 개방 주소법 _연습문제
Chapter 09 그래프 _9.1 그래프의 개요 __9.1.1 그래프의 탄생 배경: 오일러의 문제 해결 도구 __9.1.2 그래프의 정의 ___Vitamin Quiz 9-1 _9.2 그래프 표현 방법 __9.2.1 인접 행렬 __9.2.2 인접 리스트 ___Vitamin Quiz 9-2 _9.3 그래프 순회 기법 __9.3.1 깊이 우선 탐색 __9.3.2 너비 우선 탐색 __9.3.3 그래프 순회 예제 프로그램 _9.4 위상 정렬 __9.4.1 위상 정렬의 동작 방식 __9.4.2 위상 정렬 예제 프로그램 _9.5 최소 신장 트리 __9.5.1 프림 알고리즘 __9.5.2 크루스칼 알고리즘 __9.5.3 최소 신장 트리 예제 프로그램 _9.6 최단 경로 탐색: 데이크스트라 알고리즘 __9.6.1 데이크스트라 알고리즘의 개념 __9.6.2 데이크스트라 알고리즘 예제 프로그램 _연습문제
Chapter 10 문자열 탐색 _10.1 문자열 탐색 알고리즘의 개요 _10.2 고지식한 탐색 알고리즘 __10.2.1 고지식한 탐색의 동작 방식 __10.2.2 고지식한 탐색 알고리즘 예제 프로그램 _10.3 카프-라빈 알고리즘 __10.3.1 카프-라빈 알고리즘의 동작 방식 __10.3.2 카프-라빈 알고리즘 예제 프로그램 _10.4 KMP 알고리즘 __10.4.1 KMP 알고리즘의 동작 방식 __10.4.2 경계 정보 사전 계산 방법 __10.4.3 KMP 알고리즘 예제 프로그램 _10.5 보이어-무어 알고리즘 __10.5.1 나쁜 문자 이동 __10.5.2 착한 접미부 이동 __10.5.3 보이어-무어 알고리즘의 전처리 과정 __10.5.4 보이어-무어 알고리즘 예제 프로그램 _연습문제
Part 03 알고리즘 설계 기법 Chapter 11 알고리즘 성능 분석 _11.1 알고리즘 성능 측정 기준과 수행 시간 __11.1.1 알고리즘 성능 측정 기준 __11.1.2 알고리즘 수행 시간 분석 _11.2 점근 표기법 __11.2.1 O 표기법 __11.2.2 Ω 표기법 __11.2.3 Θ 표기법 _11.3 재귀 알고리즘 성능 분석 __11.3.1 재귀 방정식과 재귀 알고리즘 __11.3.2 퀵 정렬의 성능 분석 __11.3.3 마스터 정리 _연습문제
Chapter 12 분할 정복 _12.1 분할 정복 기법의 개요 __12.1.1 분할 정복 전술의 탄생 배경: 아우스터리츠 전투 __12.1.2 분할 정복 알고리즘의 개념 _12.2 병합 정렬 __12.2.1 병합 정렬 동작 방식 __12.2.2 병합 정렬 알고리즘의 구현 _12.3 거듭 제곱 계산 __12.3.1 거듭 제곱 계산법 __12.3.2 거듭 제곱 계산 알고리즘의 구현 _12.4 분할 정복 기반 피보나치 수 구하기 __12.4.1 피보나치 수를 구하는 방법 __12.4.2 분할 정복으로 피보나치 수를 구하는 방법 __12.4.3 분할 정복 기반 피보나치 수 구하기 알고리즘의 구현 연습문제
Chapter 13 동적 계획법 _13.1 동적 계획법의 개요 __13.1.1 동적 계획법의 탄생 배경 __13.1.2 동적 계획법의 개념 _13.2 동적 계획법 기반 피보나치 수 구하기 __13.2.1 동적 계획법으로 피보나치 수를 구하는 방법 __13.2.2 동적 계획법 기반 피보나치 수 구하기 알고리즘의 구현 _13.3 최장 공통 부분 수열 __13.3.1 LCS 알고리즘 __13.3.2 동적 계획법 기반 LCS 알고리즘의 구현 _연습문제
Chapter 14 탐욕 알고리즘 _14.1 탐욕 알고리즘의 개요 _14.2 거스름돈 줄이기 문제 __14.2.1 거스름돈 계산 예제 프로그램 __14.2.2 탐욕 알고리즘의 중요한 속성 _14.3 크루스칼 알고리즘 다시 보기 _14.4 데이크스트라 알고리즘 다시 보기 _14.5 허프만 코딩 __14.5.1 고정 길이 코드와 접두어 코드 __14.5.2 허프만 트리 구축 __14.5.3 데이터 압축 __14.5.4 데이터 압축 해제 __14.5.5 허프만 코딩 예제 프로그램 _연습문제
Chapter 15 백트래킹 _15.1 백트래킹의 개요 __15.1.1 백트래킹의 사례: 테세우스 이야기 __15.1.2 백트래킹의 개념 _15.2 미로 탈출로 찾기 __15.2.1 재귀 호출 기반 백트래킹 __15.2.2 미로 탈출 알고리즘의 구현 __15.2.3 미로 탈출 알고리즘 예제 프로그램 _15.3 8개의 퀸 문제 __15.3.1 8개의 퀸이 만드는 해공간과 백트래킹 __15.3.2 N개의 퀸 문제 풀이 알고리즘의 구현 __15.3.3 N개의 퀸 문제 풀이 예제 프로그램 _연습문제
[ Main Quest: 더 나은 개발자 되기 ] 자료구조+알고리즘, 더 나은 개발자가 되기 위한 최고의 Level Up 루트!
자료구조와 알고리즘을 배우면 좋은 개발자가 되는 데 큰 도움이 됩니다. 사실 요즘은 표준 라이브러리에서 여러 알고리즘을 기본으로 제공하고 있으므로 표준 라이브러리만 사용해도 프로그램을 만들기에는 충분합니다. 하지만 아무리 좋은 도구라도 상황에 맞지 않는다면 쓸모가 없습니다. 표준 라이브러리는 개발자에게 있어 도구함과 같습니다. 좋은 개발자라면 상황에 맞는 도구를 잘 꺼내어 쓸 줄도 알아야 합니다.
그렇다면 “상황에 맞는 자료구조와 알고리즘을 어떻게 선택할 수 있을까요?” 자료구조와 알고리즘이 어떤 원리와 구조로 작동하는지 정확하게 이해하고 있어야 합니다. 작동 원리를 알고 있으므로 이것저것 적용해 보면서 허송세월하는, “‘왜 안 되지?’의 시간”을 줄여 더 좋은 프로그램을 만드는 시간에 더 많은 시간을 투자할 수 있습니다. 심지어 문제가 발생했을 때는 상황에 맞게 알고리즘을 개선할 수도 있습니다.
하지만 자료구조와 알고리즘은 배우면 배울수록 더욱 복잡한 수식이 등장하고, 코드마저 점점 길어집니다. 개발자에게는 자료구조와 알고리즘은 레이드 퀘스트와 같습니다. 더 높은 전투력을 가지기 위해 도전하고 또 도전하지만, 클리어는 절대 만만치 않죠. 마찬가지로 더 좋은 개발자가 되기 위해서 자료구조와 알고리즘을 배워야 하지만, 끝까지 배우기는 절대 쉽지 않습니다. 어쩌면 자료구조와 알고리즘은 개발자에게 ‘최종 보스’일지도 모릅니다.
그동안 자료구조와 알고리즘을 끝까지 배우지 못했다면 그건 아직 『이것이 자료구조+알고리즘이다』를 만나지 못했기 때문일 것입니다. 재미는 학습을 계속할 큰 동력이 됩니다. 좋은 동료가 있으면 즐겁게 게임(캠핑, 등산, 운동, 독서 모임 등)을 이어갈 수 있는 것처럼, 좋은 참고서가 옆에 있으면 자료구조와 알고리즘을 끝까지 즐겁게 배울 수 있습니다. 그래서 『이것이 자료구조+알고리즘이다』가 동료로 삼을 만큼 좋은 책이냐고요? 지금부터 『이것이 자료구조+알고리즘이다』의 특징과 다루는 내용을 소개하겠습니다.
● 『이것이 자료구조+알고리즘이다』의 특징
》 자료구조+알고리즘 개념에 위트 넘치는 이야기를 담았다! 》 복잡한 수식은 최소화하고 이해에 꼭 필요한 수식만 담았다! 》 작동 원리를 쉽게 이해할 수 있게 도와주는 다양한 그림을 담았다! 》 배운 내용을 곧바로 점검할 수 있는, 퀘스트처럼 재미있는 다양한 연습문제를 담았다! 》 배운 알고리즘을 바로바로 테스트할 수 있는 108개의 예제 소스를 제공한다! 》 자료구조와 알고리즘 공략을 위한 저자 Q&A 카페를 운영한다!
● 『이것이 자료구조+알고리즘이다』에서 다루는 내용
》 알고리즘의 기반이자 그 자체로도 아주 유용한 4가지 자료구조 → 리스트, 스택, 큐, 트리
파워문화리뷰[도서 서평] 이것이 자료구조 + 알고리즘이다 with C 언어
내용
평점5점
편집/디자인 평점5점바**이|2022.09.13|추천2|댓글0리뷰제목
알고리즘과 자료구조.
전산 쪽에 관련된 사람이라면 가슴속 어딘가에 품고 있는 애증의 단어라고 생각한다.
분명 알기는 아는데... 남에게 가르쳐 줄 정도로 확실히 알고 있는지 묻는다면 자신 있게
그렇다고 말할 수 있는 사람이 얼마나 될까?
그런 자신감 없는 나에게 도움이 될 거라 생각해서 선택한 책이
이것이 자료구조 + 알고리즘이다 wit C언어라는;
자료구조 및 알고리즘과 친해질 수 있도록 도와주는 책
내용
평점5점
편집/디자인 평점5점블***7|2023.11.26|추천0|댓글0리뷰제목
이것이 자료구조+알고리즘이다 with C 언어
박상현 지음
이 책은 박상현 저자님의 "뇌를 자극하는 알고리즘" 이라는 책의 후속작 입니다.
우선, 저자님의 이전 책인 "뇌를 자극하는 알고리즘" 책을 보지 못하여서 비교할 수 없지만,
이 책은 프로그래밍을 한다면 기본적으로 알아야 하는 자료구조와 알고리즘에 대해 군더더기 없이 깔끔하게 정리된;
포토리뷰알고리즘 이보다 쉬울 수 있을까?
내용
평점5점
편집/디자인 평점5점d*****3|2023.11.26|추천0|댓글0리뷰제목
보통 자료구조나 알고리즘 관련 책은 생각만 해도 어려울 것 같고, 잠이 올 것 같다. 그래서 해야된다는 굳은 의지가 아니면, 보통 앞에서 3~4장을 보고 덮어두는 경우가 허다할 것이다.
그렇다면, 이 책으로 다시 한번 시작해보자. 글과 그림으로 재미있게 알고리즘을 이해할 수 있다. 처음부터 끝까지 전혀 지루하지 않게 읽을 수 있었다.
개인적으로 자료구조, 알고리즘 책;
보통 자료구조나 알고리즘 관련 책은 생각만 해도 어려울 것 같고, 잠이 올 것 같다. 그래서 해야된다는 굳은 의지가 아니면, 보통 앞에서 3~4장을 보고 덮어두는 경우가 허다할 것이다.
그렇다면, 이 책으로 다시 한번 시작해보자. 글과 그림으로 재미있게 알고리즘을 이해할 수 있다. 처음부터 끝까지 전혀 지루하지 않게 읽을 수 있었다.
개인적으로 자료구조, 알고리즘 책은 2~3권 교차해서 읽으면 좋은데, 본인도 4권을 가지고 있다. 그 중 제일 재미없고 어려운 책은 대학 교재였다. 처음부터 이 책으로 시작했으면, 대학 교재가 이 책이었으면, 재미와 지식을 둘 다 가졌을텐데 하는 아쉬움이 들었다. 오히려 전공자에게는 알고리즘을 포기하게 만드는 단점이랄까~
모두 읽고 나니 비전공자도 쉽게 읽을 수 있는 난이도라고 생각한다. 다만 예제가 C언어인데, 개념을 익히는데, 전혀 문제가 되지 않는다. 오히려, 예제에서 연산을 하나하나 구현하므로, 다른 언어와 비교하면서 살펴보기를 추천한다.
책의 구성은 크게 3개의 파트로 되어 있는데, Part 01에서는 자료 구조(리스트, 스택, 큐, 트리)를 살펴보고, Part 02는 알고리즘(정렬, 탐색, 우선순위 큐와 힙, 해시테이블, 그래프)을 설명한다. 마지막 Part 03은 알고리즘 설계 기법(성능 분석, 분할 정복, 동적 계획법, 탐욕 알고리즘, 백트래킹)에 관해 설명한다.
각 장을 설명하면 아래와 같다.
먼저, Chapter 00은 자료구조 개념과 알고리즘의 정의에 관해 알아보고, 앞으로 다룰 예제에서 꼭 필요한 C언어의 포인터, 구조체, 메모리 레이아웃(스택, 힙)으로 몸풀기를 진행한다.
본격적으로 Chapter 01에서는 리스트의 개념을 이해하고, 배열과 차이점, 링크드 리스트, 더블 링크드 리스트, 환형 링크드 리스트를 구현한다.
Chapter 02는 우리에게도 아주 익숙한 스택이다. 스택의 개념과 연산을 이해하고, 배열 기반 스택과 링크드 리스트 기반 스택을 구현한다.
Chapter 03은 큐의 개념과 주요 연산을 이해하고, 순환 큐와 링크드 큐를 구현한다.
Chapter 04는 트리다. 트리의 개념을 이해하고, 이진 트리와 수식 트리, 분리 집합을 살펴본다.
Chapter 06은 탐색의 개념에 관해 알아보고 순차 탐색, 이진 탐색의 개념을 이해한다. 그리고 이진 탐색 트리와 레드 블랙 트리를 구현한다.
Chapter 07은 우선순위 큐와 힙(메모리 힙과는 다르며, 완전 이진 트리의 종류)의 개념을 이해하고, 힙 기반 우선순위 큐를 구현한다.
Chapter 08에서는 해시 테이블의 개념을 이해하고, 해시 테이블과 해시 함수를 구현한다. 또한 해시 테이블의 주소 충돌 해결 방법도 다룬다.
Chapter 09는 그래프의 개념과 표현 방법을 이해하고, 그래프의 순회 기법과 위상 정렬, 최소 신장트리 기법과 최단 경로 탐색 알고리즘을 살펴본다.
Chapter 10은 문자열 탐색 알고리즘의 개념을 알아보고, 카프-라빈 알고리즘, KMP 알고리즘, 보이어-무어 알고리즘을 구현한다.
Chapter 11에서는 알고리즘 성능 측정 기준(정확성, 작업량, 메모리 사용량, 단순성, 최적성)을 이해하고, 수행 시간의 개념과 표기법을 알아본다 .
Chapter 12는 알고리즘 설계 기법의 하나인 분할 정복을 알아본다.
Chapter 13은 동적 계획법의 개념을 살펴보고, 동적 계획법을 이용하여 피보나치 수 구하기, LCS(최장 공통 부분 수열) 알고리즘을 설계한다.
Chapter 14는 탐욕 알고리즘의 개념을 이해하고, 탐욕적 관점에서 그래프에서 배운 크루스칼과 데이크스트라(다익스트라) 알고리즘을 살펴본다. 허프만 코딩(데이터 압축)도 구현한다.
마지막, Chapter 15에서는 백트래킹 개념을 이해하고, 미로 탈출 알고리즘과 N개의 퀸 문제 풀이 알고리즘을 설계한다.
각 장의 시작은 학습 목표인데, 이 장에서 설명하는 핵심 개념과 학습 흐름을 정리한다. 핵심 개념은 알고리즘의 탄생 배경이라든지, 적절한 예시(나폴레옹의 전술, 그리스-로마 신화, 수학자 레온하르트 오일러의 이야기)를 들어 전혀 지루하지 않고, 흥미를 부추기며 알고리즘 속으로 독자를 끌어 들인다. 알고리즘을 설명할 때는 그림을 이용하여 단계별로 설명하므로 쉽고, 페이지도 금방금방 넘어간다. ㅎㅎ, 이어서 응용 알고리즘 설명과 C언어 구현 예제 및 실행 결과, 마지막 연습 문제로 마무리한다.
깊이 우선 탐색 개념 설명
중간 중간 "!여기서 잠깐", "NOTE"는 관련 용어이나 참고 사항, 보충 설명이 있을 때마다 나오니, 읽어 보고 참고하시면 된다.
이 책에서 좋았던 부분은 단연코 알고리즘과 관련하여 흥미를 끌만한 다양한 내용이며, 저자의 위트 넘치는 표현이다. 그리고 빼놓을 수 없는 부분이 예제의 완성도이다. 변수의 선언이라든지, 소스 코드 분리, 테스트 코드, 바로 현업에 사용해도 전혀 어색하지 않는다고 개인적으로 생각한다.
636페이지의 분량이지만, 읽다 보면 생각보다 빨리 읽을 수 있을 것이다. 개념을 설명하기 위한 그림과 예제가 많아서 이해하기도 쉽고, 읽기도 쉬웠다. 책 내용과 그림은 퍼플계열인데, 그 부분도 좋았다.
개인적으로는 10장의 문자열 탐색 알고리즘이 많이 어려웠다. 리뷰 다 쓰고 다시 읽어 봐야 겠다. 다른 장들은 비교적 어렵지 않게 읽혔다. 단점으로는 연습문제 답도 만들어 주세요~, 이러다 아무도 안 읽고 버려질 수 있어요. 제발~
마지막으로 우리가 알고리즘 책을 봐야하는 이유에 관한 저자의 인용 문구로 마무리하고자 합니다.
알고리즘을 체계적으로 공부하지 않아도 프로그래밍을 할 수 있지만, 더 나은 프로그래머가 되기 위해서는 알고리즘에 대해 제대로 알아둘 필요가 있습니다.
음성 검색
QR/바코드 검색
