Normalization 정규화 - 데이터 중복을 최소화하여 DB 성능 향상, 데이터 정합성 유지 등을 목적으로 수행하는 작업들을 지칭한다. - 순차적으로 아랫 단계의 정규형부터 윗 단계의 정규형까지 만족시켜가며 Anomaly(의도치 않은 이상현상)를 예방하는 것을 목적으로 한다. - 정규화는 필수적이진 않지만, 기본적으로 정규화를 수행하여 Anomaly를 최소화한 후, 성능 도모를 위해 반정규화를 수행하는 것이 일반적이다. * Summary of Normalization 1NF - 모든 속성들이 원자값으로만 구성되어 있는 형태 2NF - 일반 속성들에 부분 종속이 제거되어 있는 형태 3NF - 일반 속성들에 이행 종속이 제거되어 있는 형태 BCNF 1NF (First Normal Form; 제1정규형)..
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;..
Data Modeling 데이터 모델링 - 정보시스템 구축을 위해, 업무에 어떤 데이터가 존재하는지 업무에 필요한 정보는 무엇인지를 분석하는 방법이다. - 데이터베이스를 구축하기 위한 분석 및 설계 과정이다. - 현실세계를 추상화·단순화·명확화하여 일정한 체계로 표현해내는 과정을 의미한다. - 현실세계의 여러 Aspect(측면)를 체계화하는 작업이다. 데이터 모델링의 특징 Abstraction (추상화) - 현실세계를 일정한 형식에 맞추어 표현한다. - 다양한 현상을 일정한 양식의 표기법에 따라 표현한다. Simplification (단순화) - 복잡한 현실세계를 약속된 규약에 의해 제한된 표기법이나 언어로 표현하여 누구나 쉽게 이해할 수 있도록 한다. Clarification (명확화) - 누구나 이해..
Machine Learning Overview 머신러닝 개요 - 인공지능의 한 분야로, 인공지능의 패턴인식과 계산 학습 이론에서 발전한 컴퓨터과학의 한 분야이다. - 머신러닝에서는 주어진 데이터로부터 학습하고 예측할 수 있는 알고리즘을 연구한다. - Data Mining을 통해 입력 데이터로 사용할 적합한 입력 변수를 선택하고, Missing Data(입력에 빠진 데이터)를 보충하거나, Outlier(이상치)를 제거하고, 적절한 양의 데이터를 선택하는 과정이 머신러닝의 핵심이다. * Data Mining (데이터 마이닝) - 현재의 데이터를 탐색하고 정리하는 일련의 과정을 지칭하는 용어이다. - 데이터 마이닝은 현재 데이터의 특징을 알아내는데 중점을 두고, 머신러닝은 현재 데이터를 통해 학습하여 미래를 ..
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에 도달할 수도 있다. - 이 알고..
