Segment Tree 세그먼트 트리 - 데이터의 교체가 발생되는 환경에서, 데이터의 합(총합과 부분합)을 가장 빠르게 구할 수 있는 자료구조이다. - 세그먼트 트리에서 지원하는 연산은 아래와 같다: Operation: Initiation - 주어진 데이터를 통한 세그먼트 트리 구축 Operation: Sum - 주어진 Sequence의 부분합 계산 (A[i] + … + A[k]) Operation: Update - i번째 데이터 교체 (A[i] = v) Mechanism (원리) - 세그먼트 트리에서는 데이터들은 Sequence(Array)로 저장한다. Specification Description 데이터의 개수 (= Leaf Node의 개수) \(N\) 세그먼트 트리의 높이 (H) \(\lceil\l..
Euclidean Algorithm 유클리드 호제법 - 최대 공약수를 빠른 시간내에 산출할 수 있는 알고리즘이다. Mechanism (원리) * Notation \(GCD(a, b) \equiv a\)와 \(b\)의 최대 공약수 (Greatest Common Divisor) \(LCM(a, b) \equiv a\)와 \(b\)의 최소 공배수 (Lowest Common Multiple) Theorem. \(A = q\cdot B + r\) 일 때, \(GCD(A, B) = GCD(B, r)\) 이다. (단, \(0 \leq r < B < A\) 이다.) Implementation (구현) * C++ typedef int type; void swap(int *a, int *b) { int temp = *a;..
A* Algorithm [A-Star Algorithm] A* 알고리즘 - 그래프의 시작 정점에서 도착 정점에 이르는 최단 경로를 계산하는 알고리즘이자, 상태 공간 트리의 탐색에도 사용되는 알고리즘이다. - A* 알고리즘에서는 Best-First Search(최적 우선 탐색) 방법과, 도착 정점까지 경로의 추정치를 사용하여 다음 정점을 선택한다. (장래의 탐색 정보를 활용하기 때문에, Dijkstra's 알고리즘과 같은 단순한 탐색 알고리즘에 비해 훨씬 효율적이다.) - Dijkstra's 알고리즘에서는 모든 정점에 대해 최단 거리를 구하는 반면, A* 알고리즘에서는 특정 도착 정점에 대한 최단 거리를 비교적 빠르게 구할 수 있다. * Best-First Search (최적 우선 탐색) - 각 정점에는 ..
Branch and Bound (BB, B&B, BnB) 분기 한정 - State Space Tree(상태 공간 트리)를 탐색할 때, Bound(한정)된 Branch(분기)를 수행함으로써 불필요한 부분(=최적해가 존재할 가능성이 없는 부분)은 탐색하지 않아 시간 낭비를 줄이는 탐색 방법이다. - 1960년 Ailsa Land와 Alison Doig가 제안한 방법으로, Linear Programming(선형 계획법)을 해결하기 위해 제시되었다. Essentials of Branch and Bound (분기 한정을 수행하기 위한 필수 요소) 1. 해당 문제가 모든 경우의 수를 나열할 방법이 존재해야 한다. 2. 해당 문제에 분기를 더 이상 할 필요가 없음을 판단할 지표가 존재해야 한다. - 상태 공간 트리에..
Graph Coloring Problem 그래프 색칠 문제 - 주어진 그래프에 \(k\)개의 색상을 사용하여 정점을 색칠하되 인접한 정점에는 같은 색깔이 칠해지지 않도록 그래프의 모든 정점을 색칠할 수 있는지를 묻는 문제이다. Mechanism (원리) Figure Description - 색칠할 대상이 되는 평면들이 서로 인접해있는 형태를 취하고 있다. - 주어진 지도에서 각 면들의 인접 관계를 화살표로 표현하면 왼쪽 그림과 같이 표현할 수 있다. - 즉, 각각의 평면들은 그래프의 정점으로, 각각의 화살표들은 정점들을 잇는 간선에 대응시킬 수 있다. - (b)의 인접 관계를 그래프로 대응시키면 왼쪽 그림과 같이 표현할 수 있다. - 이와 같이, 색칠할 평면(지도)을 그래프에 대치시켜 백트래킹 알고리즘을..
Mazing Problem 미로 찾기 문제 Mechanism (원리) Figure Description - 주어진 미로이다. - S는 시작지점, T는 목표 지점을 의미한다. - 미로를 탐색하는 과정에서 다수의 경로 중 하나를 선택해야 하는 지점(분기점, O 도형)을 표시한다. - 위에서 분기점들을 Node로 하고, 시작 지점 S를 Root로 하는 상태 공간 트리를 만들 수 있다. - S에서 시작하여 Child로 내려가며 탐색을 하되, 분기점에 다다르면, 선택지 중 하나를 골라서 탐색한다. - 그림의 회색 도형들은 운 좋게 방문하지 않고, 탐색이 종료된 노드들이다. - 운이 좋으면 시행착오를 겪지 않고 T에 도달할 수 있고, 운이 나쁘면, 모든 노드들을 다 방문한 후에 T에 도달할 수도 있다. - 이 알고..
Backtracking 백트래킹 - 백트래킹 탐색에서는 탐색을 진행하다, 더 이상 진행할 수 없다면, 왔던 길을 되돌아가 다른 길을 찾는다. - 즉, 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 통칭하는 개념이다. - 백트래킹 알고리즘마다 DFS와 약간의 차이는 있겠지만, 기본적으로는 모두 DFS의 카테코리에 속한다. - 백트래킹 알고리즘들이 모두 상태 공간 트리를 실제로 구성하여 수행하는 것은 아니지만, 백트래킹의 진행 과정은 상태 공간 트리의 Root부터 Leaf까지 DFS 방식으로 탐색하는 것과 논리적으로 동일하다. - 백트래킹에서는 상태 공간 트리를 탐색할 때, Parent에서 Child로 진행하며 최적해에 가까워져 가는데, Child로 진행하는중에 더 이상 진행할 가치가 없는(오답인)..
State Space Tree Search 상태 공간 트리 탐색 - 문제 해결 과정의 중간 상태들을 모두 Node로 구현해놓은 트리이다. - 상태 공간 트리의 Leaf Node는 해당 문제의 해(Solution)에 해당된다. - Optimum(최적해)는 Leaf Node 어딘가에 위치해 있고, 이를 효율적으로 찾아내는 것이 이 포스트의 주요 이슈이다. Brute Force (주먹구구식 탐색) - 상태 공간 트리에 존재할 수 있는 모든 Leaf Node들을 계산하여 모든 경우의 수를 조사하는 방법이다. - 대부분의 경우에서, 허용치를 넘어선 나쁜 성능을 보인다. Example. Asymmetric TSP Problem with Brute Force using State Space Tree - 위와 같은, ..
