1) Dynamic Programming
- 동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결한다
(여기서 "프로그래밍"은 컴퓨터 코드를 쓰는 것이 아니라 테이블을 이용한 방법을 일컫는다)
분할정복 알고리즘은 문제를 서로 겹치지 않는(disjoint) 부분 문제로 분할하고,
해당 부분 문제를 재귀적으로 해결한 후,
해결 결과를 결합하여 원래의 문제를 해결한다.
- 반면, 동적 프로그래밍은 부분 문제가 서로 중복될 때,
즉, 부분 문제가 다시 자신의 부분 문제를 공유할 때 적용할 수 있다.
이 경우, 분할정복 알고리즘은 공유되는 부분 문제를 반복적으로 해결하여
일을 필요 이상으로 더 많이 하게 된다.
동적 프로그래밍 알고리즘을 이용하면 모든 부분 문제를 한 번만 풀어
그 해를 테이블에 저장함으로써 그 해를 테이블에 저장함으로써
각 부분 문제를 풀 때마다 다시 계산하는 일을 피할 수 있다.
- 일반적으로 최적화 문제(Optimization Problem)에 동적 프로그래밍을 적용한다.
이런 문제는 다양한 해를 가질 수 있다.
각 해는 값을 가져 이 중 최적(최소 또는 최대)의 값인 해를 찾기를 원한다.
이런 해를 그 제에 대한 유일한 최적해라 하지 않고 한 개의 최적해라 한다.
최적의 값을 가지는 해가 여러 개 존재할 수 있기 때문이다.
프로그래밍 알고리즘을 개발할 때는 다음 4단계를 따른다.
1. 최적해의 구조의 특징을 찾는다
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 일반적으로 상향식(bottom-up) 방법으로 계산한다
4. 계산된 정보들로부터 최적해를 구성한다.
- 1~3단계는 주어진 한 문제에 대한 동적 프로그래밍 해의 기초가 된다.
4단계는 최적해 자체는 필요 없고 최적해의 값만 필요할 경우 생략할 수 있다.
4단계를 수행할 경우, 최적해를 쉽게 구성하기 위해 3단계에서 부가적인 정보를 유지하기도 한다.
- 이후에는 동적 프로그래밍 방법을 이용해 몇 가지 최적화 문제를 풀어본다.
우선, 막대 하나를 더 작은 막대 여러 개로 나누어 총 가치가 최대가 되도록 하는 문제를 살펴본다.
그 다음, 일련의 행렬을 곱할 때 스칼라 곱의 전체 횟수를 최소화하는 곱 순서를 살펴본다.
동적 프로그래밍에 대한 이런 예가 주어졌을 때,
어떤 문제에 동적 프로그래밍이 적용되기 위해 필요한 두 가지 주요한 특징에 대해 논의한다.
- 그 다음, 두 개의 시퀀스에서 최장 공통 부분 시퀀스(Longest Common Subsequence)를
동적 프로그래밍을 이용해 찾는 방법을 보여준다.
마지막으로는 검색할 키들의 분포가 주어졌을 때,
동적 프로그래밍을 이용해 최적인 이진 검색 트리(binary search tree)를 만들어본다.
2) A* 알고리즘
- A* 알고리즘은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다.
이 알고리즘은 다익스트라 알고리즘과 유사하나 차이점은 각 꼭짓점 x에 대해 그 꼭짓점을 통과하는 최상의 경로를
추정하는 순위값인 휴리스틱 추정값 h(x)을 매기는 방법을 이용한다는 것이다.
이 알고리즘은 이 휴리스틱 추정값의 순서로 꼭짓점을 방문한다.
그러므로 A* 알고리즘을 너비 우선 탐색의 한 예로 분류할 수 있다
- 이 알고리즘은 1968년 피터 하트, 닐스 닐슨, 버트램 라펠이 처음 기술하였다. 그 3명의 논문에서 이 알고리즘은 A 알고리즘이라고 불렸다. 적절한 휴리스틱을 가지고 이 알고리즘을 사용하면 최적(optimal)이 된다. 그러므로 A* 알고리즘이라고 불린다.
- A* 알고리즘은 출발 꼭짓점으로부터 목표 꼭짓점까지의 최적 경로를 탐색하기 위한 것이다.
이를 위한 평가 함수 f(n)은 다음과 같다.
f(n) = g(n) + h(n)
g(n): 출발 꼭짓점으로부터 꼭짓점 n까지의 경로 가중치
h(n): 꼭짓점 n으로부터 목표 꼭짓점까지의 추정 경로 가중치
3) B 트리
- B-트리는 디스크나 다른 직접 접근 보조 기억 장치에서 잘 동작하도록 설계된 균형이 잡힌
검색 트리다. B-트리는 레드블랙 트리와 비슷하지만(13장), 디스크 입출력(I/O) 연산을
최소화하는데 있어 더 낫다.
많은 데이터베이스 시스템에서 정보를 저장하기 위해 B-트리나 B-트리 변형을 사용한다.
- B-트리는 B-트리의 노드가 자식을 수 개에서 수천 개까지 가질 수 있다는 점에서 레드블랙 트리와
다르다. 다시 말해, B-트리의 분기 인자(branching factor)는 사용된 디스크 장치의 특성에 의해 결정되지만,
매우 클 수 있다.
노드를 n개 가진 B-트리는 모두 O(lgn)의 높이를 가진다는 점에서 B-트리는 레드블랙 트리와 비슷하다.
- B-트리의 높이는 분기 인자 때문에, 즉 그것의 높이를 나타내는 로그의 밑이 훨씬 더 클 수 있어
레드블랙 트리의 높이보다 상당히 작을 수 있다.
그래서 B-트리를 동적인 집합 연산을 O(lgn) 시간으로 구현하는데 많이 사용할 수도 있다.
- B-트리는 이진 검색 트리를 자연스럽게 일반화한 것이다. 그림 18.1은 단순한 B-트리를 보여준다.
B-트리의 내부 노드 x가 x.n개의 키를 포함한다면 x는 x.n+1개의 자식을 가진다.
노드 x에 있는 키들은 노드 x에 의해 처리되는 키의 범위를 x.n+1개의 부분 범위로 분할하는데 사용된다.
그리고 각각의 부분 범위는 x의 자식에 의해 처리된다.
- B-트리에서 어떤 키를 검색할 때 노드 x에 저장된 x.n개의 키와 비교해 (x.n+1)가지 중 하나를 고르는 결정을 한다.
리프 노드(leaf node)의 구조는 내부 노드의 구조와 다른데 그 차이는 18.1절에서 다룬다.
- 18.1절에서는 B-트리의 정확한 정의를 제공하고 B-트리의 높이가 트리에 포함된 노드 수의 로그 함수값에 비례함을 증명한다. 18.2절에서는 B-트리에서 키를 찾는 방법과 키를 삽입하는 방법을 설명한다.
그리고 18.3절에서는 삭제에 관해 설명한다. 그러나 이에 앞서 자기 디스크에서 동작하도록 설계된 자료구조와
메인 랜덤 접근 메모리(Main Random-Access Memory)에서 동작하도록 설계된 자료구조를 다르게 평가하는 이유를
알아볼 필요가 있다.
https://ko.wikipedia.org/wiki/B%2B_%ED%8A%B8%EB%A6%AC
4) B+ 트리
- B+ 트리는 컴퓨터 과학 용어로, 키에 의해서 각각 식별되는 레코드의
효율적인 삽입, 검색과 삭제를 통해 정렬된 데이터를 표현하기 위한
트리 자료구조의 일종이다.
- 이는 동적이며, 각각의 인덱스 세그먼트(보통 블록 또는 노드라고 불리는)
내에 최대와 최소 범위의 키의 개수를 가지는 다계층 인덱스(multilevel index)로 구성된다
- B트리와 대조적으로 B+트리는, 모든 레코드들이 트리의 가장 하위 레벨에 정렬되어 있다.
오직 키들만이 내부 블록에 저장된다.
- B+트리에서 중요한 가치는 블록-지향적인 storage context(ex) filesystem)에서 검색을 효율적으로
검색을 효율적으로 할 수 있다는 점이다. 바이너리 서치 트리에 비해 B+트리 노드의
fanout(한 노드의 자식 노드 수)이 훨씬 높아서 검색에 필요한 I/O 동작 회수를 줄일 수 있기 때문이다.
'CS Fundamental' 카테고리의 다른 글
| [CS Fundamental] Base64 인코딩 (0) | 2024.09.20 |
|---|---|
| [CS Fundamental] 좋아하는 IDE에서 자주 사용 하는 기능들 또는 특별히 좋은 기능들 (0) | 2024.09.19 |
| [CS Fundamental] Docker와 VM의 차이점은? (0) | 2024.09.16 |
| [CS Fundamental] PNG 포맷에서 투명을 어떻게 표현하나요? (0) | 2024.09.16 |
| [CS Fundamental] CORS란? (0) | 2024.09.14 |
