반응형
길벗 출판사의 개발자 리뷰어 활동에 당첨되어 '그림으로 이해하는 알고리즘' 책을 리뷰하게 되었다. 이 책의 핵심은 시각적인 요소를 활용하여 이해하기가 정말 쉽다는 점이다. 이 책을 받고 공부를 하면서 아래와 같이 글로만 정리했지만, 그림을 보면서 이해하고 작성을 한거라 이해하기가 정말 쉬웠다. 대학교 때는 그냥 글만 겁나게 많은 알고리즘 책으로 공부를 해서 이해하기도 많이 까다로웠는데, 대학교 1학년 때 이런 책으로 조금은 유하게 개념을 접근할 수 있도록 해줘야 하는게 아닐까 하는 생각이고, 책을 정말 잘 읽어서 좋은 지식을 쌓을 수 있었던 기회였다.
목차
제 0장 알고리즘의 기본
제 1장 데이터 구조
제 2장 정렬
제 3장 배열 탐색
제 4장 그래프
제 5장 보안 알고리즘
제 6장 클러스터링
제 7장 데이터 압축
제 8장 그 외 알고리즘
제 0장 알고리즘의 기본
1. 알고리즘의 적용 목적
- 실행 시간은 짧지만, 메모리를 많이 사용
- 실행 시간은 길지만, 메모리를 적게 사용
- 상황에 맞게 알고리즘을 적용해야 함
2. 개념에 대한 접근
우리가 회사에서 어떤 문제를 해결하거나 기능 구현을 했을 때, 바로 코드를 보는 것보다 어떻게 동작하여 어떤 로직을 실행하는지 전체적인 맥락을 파악한 다음에 코드를 보는 것이 더 효율적인 것처럼, 알고리즘도 그냥 보는 것보다 그림이나 숫자를 통해 접근하는 것이 더 좋을 수도 있다.
3. 알고리즘
- 계산이나 작업을 수행하는 순서
- 어떤 문제를 푸는 순서
4. 알고리즘 선택 방법
- 저장 공간을 적게 사용하여 메모리가 제한된 컴퓨터에서 작동 유무
- 계산 시간이 짧은 알고리즘(입력값을 주고 결과 도출까지의 시간)
5. 알고리즘 계산 시간 측정 방법
- 같은 알고리즘이라도 입력 크기에 따라 시간이 오래걸릴 수 있음
- 알고리즘의 기본 동작의 시간은 알고리즘 계산 시간에 큰 영향을 주지 않고, 입력값의 크기는 계산 시간에 큰 영향
- 알고리즘 시간 계산은 O(n), O(n^2), O(nlogn) 등으로 표기를 하는데, O는 Order라고 하며, '중요한 항 이외의 항은 무시한다'라는 의미를 가지고 있음
제 1장 데이터 구조
1. 데이터 구조
- 데이터를 메모리에 저장할 때, 데이터의 순서나 위치 관계를 잡는 것을 데이터 구조라고 함
- 효율적으로 데이터를 메모리에 저장하거나, 데이터를 찾을 때 목적에 맞게 설계하는 것이 중요함
2. 데이터 구조 종류
1) 리스트(List)
- 데이터를 일직선으로 정렬한 데이터 구조
- 데이터 추가와 삭제는 쉽지만, 데이터 탐색을 위한 접근하는 시간에는 오래 걸림
- 리스트에서는 선형 탐색을 사용하는데 시간 복잡도는 O(n)
- 리스트에서 마지막 포인터가 처음 포인터를 가리키게 하는 원형 리스트(순환 리스트), 각 데이터의 포인터들이 서로를 바라보는 양방향 리스트가 있다.
2) 배열(Array)
- 데이터를 한 열로 연속하여 정렬하는 구조
- 리스트와 달리, 데이터 탐색에는 용이하지만, 데이터 추가/삭제에는 시간이 오래 걸림
- 리스트는 특정 데이터에 접근할 때, 순차 탐색을 해야 하지만, 배열은 직접 접근이 가능함(랜덤 접근)
- 배열에서 데이터를 추가할 경우, 기존에 있는 데이터들을 뒤로 옮기고 추가를 해야 하므로, 배열에서는 추가/삭제에는 시간이 오래 걸린다.
- 배열에서 데이터 탐색 시에는 직접 접근이 가능하여 O(n), 데이터 추가/삭제 시 n개씩 공간을 비우거나 채워야 하므로 O(n)이 된다.
3) 스택(Stack)
- LIFO(Last In First Out) : 가장 나중에 들어온 게 가장 먼저 나가는 데이터 구조(후입선출)
- 푸시(Push) : 스택에 데이터를 넣는 작업
- 팝(Pop) : 스택에서 데이터를 꺼내는 작업
- 항상 최신 상태의 데이터를 접근할 때 용이한 데이터 구조
4) 큐(Queue)
- FIFO(First In First Out) : 가장 먼저 들어온 것이 가장 먼저 나가는 데이터 구조(선입선출, 대기행렬)
- 인큐(enqueue) : 큐에 데이터를 넣는 작업
- 데큐(dequeue) : 큐에서 데이터를 꺼내는 작업
- 큐에서 데이터를 추가하는 위치와 삭제하는 위치는 반대
- 큐는 너비 우선 탐색(BFS, Breadth-First Search)에 사용
5) 해시 테이블(Hash Table)
- 키(Key)와 값(Value)이 한 쌍을 이뤄 데이터를 저장하는 구조
- 배열에 Key와 Value를 쌍으로 가진 것으로 구성하면 선형 탐색이 되는데, 데이터의 양이 증가하면 시간도 증가
- 배열의 단점을 보완하기 위한 데이터 구조가 바로 해시 테이블
- 해시 함수를 사용하여 Key에 대한 해시값을 계산
- 해시값을 배열 크기로 나눠 나머지를 구하여 나머지 값에 맞는 배열 인덱스에 저장한다.(MOD 연산)
- 만약, 나머지 값이 겹치는 경우에는 해당 배열 인덱스 위치에 리스트로 연결한다.(체이닝)
- 예를 들어, A의 키 값은 3, B의 키 값은 5일 경우에, 배열 크기인 2로 나눌 경우에 둘다 나머지가 1이 된다. 그러면, A와 B는 리스트로 구성되고, 여기서 B를 탐색하려고 하면 B의 키값인 5를 2로 나누면 나머지가 1이 되는데, 1에는 이미 A가 있으므로, 선형 탐색을 한다.
- 해시 테이블은 해시 함수를 통해 데이터 탐색에 용이하고, 나머지가 겹치더라도 리스트로 관리를 하기 때문에 유연성이 높다.
- 하지만, 배열 크기가 작을 경우에는 리스트의 크기가 커져 데이터 탐색 속도가 느려지고, 배열 크기가 클 경우에는 메모리 낭비가 커진다.
6) 힙(Heap)
- 그래프의 트리 구조 중 하나로 우선수위 큐를 구현할 때 사용
- 우선순위 큐 : 데이터는 자유롭게 추가가 가능한데, 데이터를 꺼낼 때는 가장 작은 값을 먼저 꺼냄
- 힙에서의 노드는 최대 2개의 자식노드를 가짐
- 힙에서는 데이터를 저장할 때, 자식 노드의 값이 부모 노드의 값보다 항상 커야 함
- 힙에서 데이터를 꺼낼 경우, 맨 마지막의 노드가 올라오고, 자식 노드 중 가장 작은 노드가 부모노드가 된다.
- 그리고 나서, 자식노드의 값이 부모 노드의 값보다 항상 크도록 다시 자식 노드 중에 작은 값을 올린다.
- 힙은 데이터를 꺼낼 때 1개만 꺼내기 때문에 O(1), 힙을 정렬할 때에는 O(log n)
7) 이진 탐색 트리(Binary Search Tree)
- 이진 탐색 트리도 힙과 마찬가지로, 각 노드들은 최대 2개의 자식 노드들을 가짐
- 각 노드의 값은 왼쪽 가지에 있는 값들보다 크다. 즉, 10이 부모 노드면, 10이 2개의 자식 노드를 가지고 있는데, 왼쪽에 있는 자식노드들은 10보다 작다.
- 반대로, 각 노드의 값은 오른쪽 가지에 있는 값들보다 작다.
- 그래서, 최소값을 찾으려면 해당 노드보다 작은 왼쪽 가지만 탐색을 하면 되고, 최대값은 오른쪽 가지만 탐색을 하면 된다.
- 이진 탐색 트리의 시간 복잡도는 O(log n), 만약 한쪽으로 쏠리는 경우에는 O(n)
- 위의 한쪽으로 쏠리는 경우를 대비하여 균형 이진 탐색 트리가 나왔고, 최대 자식 노드를 2개에서 m개로 증가하여 균형을 맞추는 B트리도 있다.
제 2장 정렬
1. 버블 정렬(Bubble Sort)
- 왼쪽 또는 오른쪽에서 시작하여 인접한 두 숫자를 비교하여 교체하는 정렬 알고리즘
- 버블 정렬 시 N회씩 반복할수록 최소값이 정해지기 때문에, N번을 반복하는데, 인덱스는 -1씩 빼서 정렬을 해야 함
- 버블 정렬의 시간 복잡도는 O(n^2)
2. 선택 정렬(Selection Sort)
- 수열에서 최소값을 찾아서 맨 왼쪽과 교체를 하여 정렬하는 알고리즘
- 최소값을 찾을 때 선형 탐색을 함
- 선택 정렬의 시간 복잡도는 O(n^2)
3. 삽입 정렬(Insertion Sort)
- 미탐색 영역에서 숫자 하나를 꺼내어 정렬이 완료된 영역에 값을 넣어 정렬하는 알고리즘
- 삽입 정렬의 시간 복잡도는 O(n^2)
4. 힙 정렬(Heap Sort)
- 먼저, 데이터들을 내림차순으로 힙에 데이터 넣음
- 힙 정렬은 내림차순으로 정렬하기 때문에, 데이터를 뽑아올 때 최대값을 먼저 뽑기 때문에 역순으로 정렬 필요
- 힙 정렬 데이터를 넣을 때 O(n*log n), 데이터 추가 시 O(log n), 데이터를 뽑거나 추가를 할 경우의 재정렬은 O(log n) 이므로, 힙정렬은 최대 O(n*log n)의 시간 복잡도를 가짐
- 버블, 선택, 삽입 정렬의 시간복잡도인 O(n^2)보다 빠르지만, 구현이 조금 복잡함
5. 병합 정렬(Merge Sort)
- 수열을 거의 같은 길이로 분할을 한다. 예를 들어, 1 2 3 4 5 6 7 8 이렇게 있을 경우, 각 숫자를 1개씩 놔둔다.
- 더 이상 수열을 분할할 수 없으면 다시 수열을 하나씩 정렬하면서 수열이 1개가 될 때까지 합친다.
- 병합 정렬의 시간 복잡도는 O(n*log n)
6. 퀵 정렬(Quick Sort)
- 퀵 정렬은 임의의 숫자인 피봇(Pivot)을 잡고, 해당 피봇보다 작으면 왼쪽, 크면 오른쪽에 두면서, 각 영역 별로 재귀 진행
- 퀵 정렬은 분할 정복법이라고도 함
- 퀵 정렬의 시간 복잡도는 O(n*log n)
제 3장 배열 탐색
1. 선형 탐색(Linear Search)
- 배열에서 앞쪽에서 순서대로 데이터를 찾는 알고리즘
- 선형 탐색의 시간 복잡도는 O(n)
2. 이진 탐색(Binary Search)
- 이진 탐색은 먼저, 데이터가 정렬된 경우에 적용 가능
- 정렬된 수열에서 중앙 값을 비교하여 찾고자 하는 숫자의 범위들을 절반씩 줄일 수 있음
- 이진 탐색의 시간 복잡도는 O(log n)
제 4장 그래프
1. 그래프
- 그래프는 정점과 정점과 정점을 이어주는 간선으로 구성
2. 가중 그래프
- 간선에 값을 부여하여 연결의 강도를 정함
- 예를 들어, 각 노드 간의 운송 비용 또는 시간 등을 표현할 수 있음
3. 방향성 그래프
- 간선에 방향을 부여
- 간선에 방향이 없는 그래프를 무방향 그래프라고 함
4. 너비 우선 탐색(Breadth First Search, BFS)
- 그래프를 탐색하는 알고리즘 중 하나로, 시작점에서 가까운 순으로 너비를 넓혀가며 탐색
- 타겟이 시작점에 가까울수록 탐색의 속도가 빨라짐
5. 깊이 우선 탐색(Depth First Search, DFS)
- 그래프를 탐색하는 알고리즘 중 하나로, 시작점에서 하나의 길을 선택하여 끝까지 갈 수 있는 곳까지 가서 탐색하는 알고리즘
6. 벨먼-포드 알고리즘
- 그래프의 최단 경로를 찾는 알고리즘
- 시작점과 끝점이 주어졌을 때, 시작점에서 간선의 비용 합이 작은 경로를 찾는 알고리즘
- 각 정점을 갈 때, 각 정점의 비용이 계산한 값보다 작으면 작은 값으로 갱신
- 벨먼-포드 알고리즘의 시각 복잡도는 정점 수를 n, 간선 수를 m이라고 할 때, O(n*m)
7. 다익스트라 알고리즘
- 그래프의 최단 경로를 찾는 알고리즘
- 벨먼-포드 알고리즘과 달리 간선을 다 계산하는 것이 아닌 정점을 선택하여 갱신해 최단 경로를 찾음
- 다익스트라 알고리즘의 시간 복잡도는 최악 O(n^2), 데이터 효율성이 높으면 O(m+n*log n)
- 간선의 비용이 음수가 없다면 계산 시간이 적은 다익스트라 알고리즘을 사용하고, 간선의 비용이 음수가 있다면 정확한 답을 찾는 벨먼-포드 알고리즘을 사용하는 것이 좋음
8. A* 알고리즘(A 스타 알고리즘)
- 다익스트라 알고리즘을 기반으로 추정 비용을 힌트로 사용하여 불필요한 탐색을 생략하는 알고리즘
- 미리 설정한 휴리스틱 비용(추정 비용) 설정
9. 크루스칼 알고리즘
- 그래프의 최소 신장 트리를 구하는 알고리즘
- 간선에 비용이 있는 그래프에서 간선을 선택하여 모든 정점 연결
- 이 때 간선을 선택할 때 간선의 합 비용이 최소가 되어야 함
- 신장 트리 : 모든 정점을 연결하는 간선의 집합
- 항상 신장 트리는 최소값을 구하기 때문에 최소 신장 트리라고 함
- 그리디 알고리즘 : 각 시점에서 최선의 것을 선택하는 알고리즘
10. 프림 알고리즘
- 그래프의 최소 신장 트리를 구하는 알고리즘
- 크루스칼 알고리즘과 다르게 영역이라는 용어를 사용
11. 매칭 알고리즘
- 정점을 공유하지 않은 집합을 매칭이라고 함(정점 간에 짝을 지어주는 것)
- 즉, 각 정점들은 1쌍의 간선만 선택되어야 한다.
- 모든 간선이 왼쪽과 오른쪽 정점을 연결한 그래프를 이분 그래프라고 함
제 5장 보안 알고리즘
1. 데이터를 주고받을 때 발생하는 문제 4가지
- 도청 : 암호화 기술 사용
- 위장 : 메시지 인증 코드 또는 전자 서명 기술
- 변조 : 메시지 인증 코드 또는 전자 서명 기술
- 사후 부인 : 전자 서명 기술
2. 해시 함수
- 주어진 데이터를 고정된 길이의 불규칙한 값으로 변환하는 함수
- 값을 16진수로 표기하는 경우가 많음(0~9, a-f)
- 고속으로 계산 가능
- 해시 충돌 : 똑같은 데이터가 아닌데 해시값이 같은 경우
3. 대칭키 암호 방식
- 암호화와 복호화에 동일한 키를 사용
- 대칭키 암호 방식 시저 암호, AES, DES, 원타임 패드(OTP) 등
- 주로, AES가 많이 사용됨
- 키가 노출될 경우 보안 문제 발생
4. 공개키 암호 방식
- 암호화 복호화에 다른 키를 사용
- 비대칭키 암호 방식이라고도 함
- 암호화에 사용되는 키를 공개키, 복호화에 사용되는 키를 비밀키라고 함
- 주로, RSA가 많이 사용됨
- 공개키를 바꿔치기 하고, 해당 암호문을 탈취할 경우에 보안 문제 발생할 수 있음
5. 하이브리드 암호 방식
- 대칭키 암호 방식의 키 배송 문제와 공개키 암호 방식의 암호화 및 복호화 속도 문제를 해결하기 위해 만드어진 암호 방식
- 암호화할 때는 대칭키 암호 방식을 사용하여 공개키 암호 방식을 통해 보안 암호화
6. 디피-헬먼 키 교환법
- 두 사람이 안전하게 키를 교환하는 방법
- 두 사람이 공유할 비밀의수를 공개된 숫자와의 연산을 섞어 대칭키를 안전하게 교환
7. 메시지 인증 코드
- 인증과 변조 검출 기능 제공
- 암호문이 도중에 변조되어 다른 내용으로 복호화함으로 보안 문제가 생길 것을 대비하는 것
- 메시지 인증 코드는 MAC(Message Authentication Code) 라고도 함
- MAC 중에서도 거의 HMAC을 많이 사용함
8. 디지털 서명
- 인증과 변조 검출, 사후 부인까지 방지해주는 메커니즘
- 전송자만 작성할 수 있는 디지털 서명이라는 데이터 사용하여 메시지 작성자 특정
추후 계속 정리할 예정
결론
위의 사진과 같이, 이 책에서는 그림을 통해 이해를 하기 쉽도록 제공한다. 글을 읽어도 이해를 못하더라도 그림을 통해 천천히 접근하면 이해하기가 정말 쉽다. 다만, 아쉬운 건 코드를 통한 구현에 대한 설명이 없는 게 단점이지만, 개념을 정확하기 이해하기 위한 책임은 분명하다.
이 책을 통해 알고리즘을 입문하는 사람은 읽어보는 것을 권한다.
반응형
'IT > 책 서평' 카테고리의 다른 글
| [책서평] 마셔도 괜찮아 울어도 괜찮아를 읽고 (1) | 2024.07.07 |
|---|---|
| [책서평] 모두의 네트워크 기초(10일만에 배우는 네트워크) 후기 및 리뷰 (0) | 2024.05.21 |
최근댓글