컴퓨터 컴퓨터는 정보(information)를 처리하는 기계라고 한다. 정보는 뭘까? 정보의 최소 단위는 두 가지 상태(0, 1)을 나타내는 bit이다. 이 bit가 모인 이진 데이터가 정보이다. 그렇다면 정보를 어떻게 처리할까? 정보를 처리는 비트의 상태 변환(0에서 1로, 1에서 0으로)과 같다. 정보를 처리하려면 비트의 상태 변환을 할 수 있는 물리적인 장치가 필요하고 이 장치가 논리 회로가 된다. 논리 회로 논리 게이트는 불 대수를(Boolean algebra) 구현한 물리적인 장치다. NOT, AND, OR, XOR, NAND, NOR 게이트가 있다. 불 대수는 수의 범위가 오직 0 또는 1인 수의 논리적 계산을 수학적으로 표현한 것이다. 현대 수학의 수가 실수와 허수로 이루어져 매우 복잡하다면..
DFS 그래프의 모든 정점을 특정한 순서에 따라 방문하는 알고리즘을 그래프의 탐색 알고리즘이라 한다. 대표적인 알고리즘으로 DFS(depth-first search)와 BFS(breadth-first search)가 있다. DFS는 그래프를 더 나아갈 길이 없을 때까지 깊이 들어가 탐색하며 더 나아갈 수 없다면 되돌아가는 방식이다. 즉 현재 정점과 인접한 간선들을 하나씩 검사하다가, 아직 방문하지 않은 정점으로 향하는 간선이 있다면 그 간선을 무조건 따라가고 더 이상 갈 곳이 없는 막힌 정점에 도달하면 마지막에 따라왔던 간선을 따라 뒤로 돌아간다. 아래는 인접 행렬을 탐색하는 DFS 코드이다. static void DFS(int v, int[][] graph, boolean visit[]) { Syste..
그래프 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현하는 자료 구조, 즉 정점(vertext)의 집합 V와 간선(edge)의 집합 E로 구성된 자료 구조이다. 도로망, 네트워크 망 부터 먹이 사슬, 사람들 간의 짝사랑 관계, 하루 동안의 도시 간 인구 이동 관계 등을 그래프로 표현할 수 있다. 그래프의 종류 그래프가 가지는 특징과 형태에 따라 여러 종류로 나눌 수 있다. 방향 그래프 (directed graph) : 각 간선이 방향을 가지는 그래프, 두 정점 u, v가 있을 때 u에서 v로 가는 간선과 v에서 u로 가는 간선은 서로 다른 간선이다. 무향 그래프 (undirected graph) : 각 간선이 방향을 가지고 있지 않은 그래프 가중치 그래프 (weighted graph) : 각 ..
분할 정복 문제를 더 이상 나눌 수 없을 때까지 나누고 (분할), 나누어진 부분 문제를 품으로써 (정복) 전체 문제의 답을 얻는 방식의 알고리즘 패러다임. 이진 탐색, 퀵 정렬 등이 대표적인 알고리즘이다. [동작 방식] 분할 : 문제를 더 이상 나눌 수 없을 때까지 2개 이상의 부분 문제로 나눈다. 나눠진 문제들은 서로 독립적이다. 정복 : 부분 문제를 푼다. 결합 : 정복된 답을 취합한다.
병행 제어 DBMS는 여러 사용자가 동시에 데이터베이스를 이용할 수 있도록 병행 수행 기능을 제공한다. 병행 수행은 실제로 여러 트랜잭션이 차례로 번갈아 수행되는 인터리빙(interleaving) 방식으로 지원한다. 하지만 아무런 제어 없이 병행 수행을 할 경우 갱신 분실, 모순성, 연쇄 복귀 등의 문제가 발생할 수 있다. 때문에 트랜잭션을 병행 수행 하면서도 정확한 수행 결과를 얻을 수 있도록 트랜잭션의 병행 수행을 제어하는 병행 제어(동시성 제어)가 필요하다. 병행 제어 기법 병행 제어의 핵심 목표는 트랜잭션을 번갈아 가면서 수행하면서도 트랜잭션을 순차적으로 실행하는 것과 같은 결과를 내는 것이다. 트랜잭션을 순차적으로 실행한 결과는 항상 정확하고 일관되기 때문이다. 가장 많이 사용하는 병행 제어 기..
장애의 유형 데이터베이스에 장애가 발생해도 DBMS의 회복 기능을 통해 데이터베이스는 정확하고 일관된 상태로 유지 할 수 있다. 장애가 발생하는 원인은 정전, 사용자의 실수, 하드웨어 고장, 소프트웨어 오류, 미디어 장치 고장, 트랜잭션 논리적 오류 등 매우 다양하다. 데이터베이스 저장 연산 데이터베이스는 비휘발성 저장 장치인 디스크에 저장되어 있다. 응용 프로그램에서 트랜잭션 수행을 지시하면 디스크에서 메인 메모리로 데이터를 보내고 데이터를 다시 디스크로 보내는 작업이 필요하다. 디스크와 메인 메모리 간의 데이터 이동은 블록(block) 단위로 이동하며 디스크에 있는 블록을 디스크 블록, 메인 메모리에 있는 블록을 버퍼 블록이라 한다. 디스크와 메모리 간의 데이터 이동은 다음 두 연산으로 수행된다. i..
회복과 동시성 제어 DBMS는 데이터베이스가 항상 정확하고 일관된 상태를 유지할 수 있도록 장애 발생 시 회복 기능과 동시성 제어 기능을 제공한다. 장애 발생 시 회복 기능을 통해, 여러 사용자가 동시에 데이터베이스를 사용해도 동시성 제어 기능을 통해 데이터베이스는 항상 일관된 상태를 유지한다. 회복과 동시성 제어 기능은 트랜잭션을 기반으로 동작한다. 트랜잭션 (Transaction) 트랜잭션이란 하나의 작업을 수행하는데 필요한 데이터베이스의 연산들(SELECT, INSERT, UPDATE, DELETE)을 모아놓은 것이다. 데이터베이스는 트랜잭션 단위로 작업을 수행한다. 계좌이체 트랜잭션은 2개의 UPDATE 문으로 구성되어 있다. 하나는 성호 계좌에서 5000원을 감소시키는 UPDATE문이며 다른 하..
Greedy (탐욕적 알고리즘)그리디는 경우의 수를 완성시킬 때, 지금 상황에서 가장 좋은 조각을 선택해 경우의 수 상태의 일부로 만들면서 경우의 수를 완성시키는 방식이다. 즉 탐욕적 선택으로 답을 완성시킨다. 성능이 뛰어나지만 최적해를 구한다고 보장할 수 없다.동작 방식경우의 수를 완성시키기 위해 조각 하나를 선택해 상태의 일부로 설정, 이때 가장 좋은 조각을 선택한다. 이때 아래 두 가지 속성을 증명한다.나머지 상태도 1번과 같은 방식으로 구한다.A) 탐욕적 선택 속성 : 우리가 선택한 가장 좋은 조각이 정답에 무조건 포함됨을 보인다. 귀류법으로 쉽게 증명할 수 있다.B) 최적 부분 구조 : 항상 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는지를 증명한다. 대개의 경우 이 속성이 성립하는지는 ..
