[독서/밀리의서재] 코드 없는 알고리즘과 데이터 구조

비교적 최근인 2021년 출간. 200쪽 초반으로 부담스럽지 않은 분량이다.
리뷰 중 '이 수준으로 도움이 되는 경우가 있을까?' 하는 문장을 보고 열어봤다ㅋㅋ 초반 발췌독 해보니 역시나 '데이터 구조', '알고리즘'의 정의부터 예시를 들어 설명해 주는 친절한 책이었다. 그렇다고 교과서처럼 고리타분하거나 청소년용도서처럼 듬성듬성하고 어수선한 감은 없었고, 오히려 깔끔하면서 자세했다. 내 목표인 '가볍게 정독하기'에 딱 맞는 책 같아 선택했다.

목차(&현황)

Part 1 데이터 구조

1장 데이터 구조와 알고리즘, 자료형, 빅 오 표기법

• 데이터 구조와 알고리즘 개요
• 데이터 구조
• 알고리즘
• 데이터 구조와 알고리즘의 관계   [06.20]
• 기본 자료형
• 불
• 문자
• 정수
• 부동 소수점 수
• 함수
• 함수, 메소드, 프로시저, 서브루틴   [06.21]
• 재귀와 반복
• 알고리즘의 세 가지 유형
• 알고리즘 분석   [06.22]
• 빅 오 표기법   [06.23]

마치며

2장 선형 데이터 구조

• 컴퓨터 메모리   [06.24]
• 선형 데이터 구조의 개요
• 배열
• 리스트
• 스택
• 큐
• 우선순위 큐

마치며   [~06.28]

3장 트리 데이터 구조

• 트리
• 이진 트리
• AVL 트리
• RB 트리
• B 트리
• 힙

마치며

4장 해시 데이터 구조

• 해시와 해시 함수
• 해시 테이블
• 컴퓨터 보안 기초
• 암호 시스템
• 공개 키 암호 시스템
• 해싱 vs 암호화
• 컴퓨터 보안에서 해시의 역할
• 해시와 순환 중복 검사
• 해시의 다른 용도

마치며

5장 그래프

• 차원, 점, 선
• 그래프
• 그래프 vs 트리
• 무향 그래프와 유향 그래프
• 가중치 그래프
• 그래프와 소셜 네트워크 서비스
• 그래프 데이터베이스

마치며

Part 2 알고리즘

6장 선형 및 이진 탐색

• 선형 탐색
• 선형성
• 선형 탐색의 원리
• 이진 탐색
• 로그
• 이진 탐색의 원리

마치며

7장 정렬 알고리즘

• 정렬 알고리즘의 특징
• 버블 정렬
• 선택 정렬
• 삽입 정렬
• 셸 정렬
• 병합 정렬
• 퀵 정렬
• 힙 정렬
• 버킷 정렬
• 기수 정렬

마치며

8장 경로 탐색 알고리즘

• 너비 우선 탐색
• 깊이 우선 탐색
• 데이크스트라 알고리즘
• A* 알고리즘

마치며   [~07.03]

9장 군집화 알고리즘

• K-평균 알고리즘
• K-최근접 이웃 알고리즘
• 머신러닝
• 신경망
• 딥러닝

마치며

Part 3 데이터 구조와 알고리즘을 이해하는 데 필요한 지식들

10장 무작위성

• 무작위
• 하드웨어 이해하기
• 회로와 트랜지스터
• 증폭기, 피드백, 클럭, 오실레이터
• 논리 게이트
• 조합 및 순차 논리
• 혼성 신호 회로, 유도 저항, 노이즈
• 유사 난수
• 선형 피드백 시프트 레지스터
• 참난수 생성기

마치며

11장 스케줄링 알고리즘

• 운영체제
• 범용 운영체제
• 실시간 운영체제
• 인터럽트와 인터럽트 서비스 루틴
• 유한 상태 기계
• 커널, 프로세스, 스레드, 작업
• 메모리 관리 장치
• 작업 제어 블록
• 스케줄러와 스케줄링
• 선착순 스케줄링
• 최단 작업 우선 스케줄링
• 우선순위 스케줄링
• 라운드 로빈 스케줄링
• 다단계 큐 스케줄링과 다단계 피드백 큐 스케줄링

마치며

12장 알고리즘 기획과 설계

• 타당한 기획과 설계의 필요성
• 알고리즘의 3단계
• 순서도
• 순서도 기호
• 흐름선
• 단말 기호
• 입출력 기호
• 처리 기호
• 판단 기호
• 종속 처리 기호
• 프로그램 구조
• 순차 구조
• if-then 구조
• if-then-else 구조
• while 반복 구조
• do-while 반복 구조
• switch-case 구조
• 선형 탐색 알고리즘의 순서도
• 유사 코드

마치며

부록 더 나아가기

발췌(&메모)

[26쪽] 데이터 구조는 데이터를 구성하고 저장하는 방법을 설명하며, 데이터를 식별하는 방법을 제공하고 데이터와의 관계를 보여주는 개념이다.

[28~29쪽] 알고리즘은 문제를 해결하는 논리적 절차. 단순·명확·직관적일수록 유용한 알고리즘이다. 모호하거나 극소수만 아는 난해한 기능은 지양할 것.

[34~35쪽] 부동 소수점 수: 소수점이라고 부르는 작은 점(.)의 위치가 숫자를 정밀하게 표현하기 위해 어딘가 떠다니는 것처럼 움직이기 때문에 부동점이라는 이름이 붙었고, 한국어로 번역하는 과정에서 부동 소수점이 되었다. 

[39쪽] 재귀: 자기 자신을 호출하는 횟수의 한계인 최대 재귀 깊이를 초과해 스택 오버플로 에러가 발생할 수 있다.

[42쪽] 탐욕 알고리즘과 동적 프로그래밍 알고리즘 모두 문제를 더 작은 단위로 나누는 데 중점을 둔다는 공통점이 있지만, ... 탐욕 알고리즘은 근사치를 구하고 동적 프로그래밍 알고리즘은 최적화를 한다.

[44쪽] 알고리즘의 효율성을 설명하는 다양한 표기법이 존재하며, 각 표기법은 용도가 정해져 있다. 그 중 알고리즘 사이의 점근적 증가율(asymptotic growth rate: 알고리즘에 입력하는 데이터양의 증가에 따른 처리 시간 변화율)을 비교하기 위해 가장 많이 사용되는 것은 빅 오 표기법이다. 알고리즘의 복잡도를 주로 대문자 O 또는 빅 오를 사용하여 표기하는 관례로 인해 '빅 오' 표기법이란 명칭이 붙었다. 알고리즘의 실행 시간이 최악인 경우, 즉 최대 시간을 측정하여 나타낸다.

[47쪽] 컴퓨터 메모리는 컴퓨터가 처리 중이거나 처리를 끝낸 데이터를 저장할 수 있는 공간. 계층적으로 구성되어 있고, 각 계층(서열·순서)을 이루는 메모리 유형마다 정해진 역할이 있다. 

[51쪽] 운영체제의 메모리 관리 기능은 메모리 주소에 가상의 주소를 매핑함으로써 실행할 프로그램이 실재하는 물리적 공간보다 더 많은 공간(메모리)가 있다고 착각하게 만든다. 이 때 메모리 공간을 식별하기 위해 물리적 주소인 메모리 주소를, 프로그램에 할당된 (물리적)메모리상의 위치를 식별하기 위해 가상 주소를 사용한다. 

[52쪽] 가상 메모리를 일정한 크기의 페이지로 나눠서 사용하는 페이징 개념, 페이지에 매핑된 주소를 물리적인 주소로 변환하는 페이지 테이블 개념 – 가상 메모리는 물리적인 메모리 공간에 매핑되어 있다. 특정 데이터가 물리적인 메모리 공간에 여러 개로 나뉘어 저장되어도 서로를 참조해 해당 데이터를 손실 없이 안전하게 불러올 수 있도록 한다. 
운영체제는 프로그램에 제공하는 가상 주소는 가상 메모리의 각 페이지를 식별한다. 프로그램에서 컴퓨터에 무언가를 저장하도록 요청하면 운영체제는 사용 가능한 페이지를 확보하고 동작을 수행하다. 만약 사용 가능한 페이지가 없으면 에러가 발생하며 프로그램이 실행되지 않을 것이다. 

[52쪽] 데이터 구조가 선형이다 = 구성요소들이 서로 인접해 순차적인 방식으로 정렬되어 있다 → 이해하기 쉽고 프로그램 개발에 사용하기 좋다. 배열과 리스트는 가장 일반적인 선형 데이터 구조이자 가장 범용적인 데이터 구조이므로 다른 데이터 구조들의 기반 지식이 된다. 

우선순위 큐는 기본적인 큐를 확장한 것으로, 큐와 같이 선입선출 구조의 동작을 보여준다. 우선순위가 높은 요소가 낮은 요소보다 먼저 삭제되며, 만약 우선순위가 같다면 큐에 먼저 추가된 요소부터 삭제된다. 이 때 '우선순위'는 어떻게 정해지는가? - 우선순위 큐에서 모든 요소는 우선순위가 있으며 이는 키에 해당한다.(중략: 59p 하단에 상술)

많은 파일 시스템에서 데이터 계층구조로 B트리를 사용한다. 예를 들어 파일 시스템에는 폴더가 있고, 노드의 키-값 구조를 통해 폴더 각각의 이름을 파일 시스템의 객체와 연결할 수 있다. 

힙 데이터 구조와 힙 메모리는 전혀 다른 개념이며 매우 다른 방식으로 구현된다. 힙 메모리는 프로그래머가 직접 관리해야 하는 메모리의 할당 영역, 즉 프로그래머가 작성한 코드에 따라 메모리 공간을 동적으로 할당하거나 해제하는 부분이다.

양방향 과정인 암호화와 달리, 해싱은 단방향 과정이다. 

[92p에서 질문 → 142p에서 해결] '경로'는 유향/무향 그래프 모두에서 세부의미 차이 없이 쓰이는 용어인가? → Yes

일부 프로그래머는 트리를 일종의 최소화된 그래프로 여긴다. 왜냐하면 그래프에서 동작하는 대부분의 알고리즘이 트리에서도 동작하고, 트리는 기본적으로 순환이나 순환적인 상호작용이 없는 그래프와 같기 때문이다. 

그래프의 노드를 보통 객체(object) 또는 정점(vertex)이라고 하며, 정점들을 연결하는 선을 에지(edge)라고 한다. 에지로 연결된 정점들은 서로 인접한(adjacent) 상태다. 에지는 노드 하나에서 다른 노드로 방향성을 갖거나 갖지 않을 수 있고, 가중치를 갖거나 갖지 않을 수 있다. 가중치란, 그래프에서 에지 각각에 어떤 의미가 부여된 값이 있다는 뜻이다. 

배열이 정렬되지 않은 상태에서는 이진 탐색이 올바르게 동작하지 않는다. ☆

백트래킹은 모든 경우를 다 탐색해 문제의 해답을 찾는 제어 알고리즘을 뜻한다.

 

 

 

* 목차 출처: 교보문고 홈페이지