with with

DBMS를 개발할 때는 아래의 사항을 고려해야 한다. 가용한 메모리보다 큰 데이터를 처리할 수 있어야 한다. Disk I/O는 성능저하의 원인이기 때문에 신중하게 사용해야 한다. Disk에서의 탐색은 Random보다 Sequential access가 더 빠르기 때문에 순차탐색을 최대화 해야한다. 이 사항들을 염두하고 DB 저장소를 관리하는 법을 알아보자. File Storage DBMS는 그들만의 file format을 이용하거나, OS에서 제공하는 파일 시스템을 이용해서 데이터베이스를 관리한다. 이런 파일들은 Storage Manager가 관리해준다. Storage Manager 기본적으로 데이터베이스의 파일을 여러 page 단위로 쪼개어 관리하게 된다. 여기서 page는 데이터가 들어있는 고정된 크기..

Normalization 정규화는 간단하게 말하면 비 정상상태의 테이블을 정상상태로 만들어 주는 것을 의미한다. 비 정상상태 비 정상상태의 테이블은 insert, update, delete의 명령을 수행할 때 적절치 못하게 동작하는 테이블을 의미한다. - insert시 쓸데없는 null값을 허용하는 경우 회원 정보를 저장할 때 ID가 null값이 들어가는 상황 - update시 데이터의 불 일치가 일어나는 경우 같은 ID값을 갖고있는 회원의 이름이 다르게 저장되는 상황 - delete시 특정 튜플이 모두 삭제되는 경우 교수가 강의가 끝나 course_id를 지웠는데, 해당 column의 데이터가 모두 삭제되는 상황 Lossless Decomposition 비 정상상태를 해결하는 방법은 보통의 경우 테이블..

Overflow (Underflow) overflow 현상은 다음과 같은 상황에 발생한다. $$ ve + ve $$ $$ -ve + (-ve) $$ $$ ve - (-ve) $$ $$ -ve - ve $$ overflow가 발생하지 않도록 연산에 유의하거나, 발생했을 때 별도의 처리를 해 줘야 한다. 이미지, 영상 처리과 같은 곳에서는 Satrating operations 과정을 거치는데, 간단하게 말하면, overflow가 발생한 경우, 표현 가능한 최대의 숫자로 값을 바꾸는 것을 의미한다. Multiplication (H/W) 하드웨어 레벨에서의 곱셈을 하는 방식은 위 그림과 같다. 1001 * 1001 의 연산을 예로 들어보자. multiplier의 가장 낮은 bit가 1인 경우, product r..

Registers 레지스터 사용처 $a0 ~ $a3 argument값을 저장할 때 사용 $v0, $v1 return값을 저장할 때 사용 (long 타입의 경우 두 레지스터를 사용하기 위함) $t0 ~ $t9 임시로 값을 저장할 때 사용 $s0 ~ $s7 사용빈도가 높은 값을 저장할 때 사용 $gp global pointer (for stack data) $sp stack pointer $fp frame pointer $ra return address $zero 0 상수값을 갖고있음. 덮어쓰기 불가 Instructions 명령어 읽기 기능 add A, B, C add A = B + C addi A, B, c add immediate A = B + c // c는 상수. (subi는 없고 대신 음수 상수를 이..

- 알고리즘 정의 주어진 Graph의 모든 노드를 한 번씩 방문하여 출발했던 노드로 돌아오는 방법 중, 가장 최단 시간으로 걸리는 경로를 찾는 문제이다. 일명 TSP 알고리즘이다. 위 예시에서는 v1 - v3 - v4 - v2 - v1로 방문하면 최단 시간이 걸린다. 참고로 출발점은 임의로 잡아도 상관 없다. 왜냐하면 모든 노드를 한 번씩 방문하기 때문에 반드시 특정 노드를 어느 순간 지나기 때문이다. 다만, 이해와 구현의 편의성을 위해 v1을 시점이자 종점으로 삼자. 최적의 경로는 위 경로 중 하나의 경우다. v1 - v2 를 지나 최적 경로 A를 지나 v1로 돌아오거나, v1 - v3 를 지나 최적 경로 A를 지나 v1로 돌아오거나, ..., v1 - vn 를 지나 최적 경로 A를 지나 v1로 돌아오..

- BST 이런 트리 형태의 자료구조. Tree - Binary Search Tree Binary Tree 중, 아래의 조건을 만족하는 Tree이다. 1. 루트노드의 왼쪽 서브트리의 노드는 루트노드보다 작거나 같아야 한다. 2. 루트노드의 오른쪽 서브트리의 노드는 루트노드보다 커야한다. BST로 with611.tistory.com - 알고리즘 정의 데이터를 효율적으로 관리하기 위해 BST를 사용하는데, BST의 경우에도 문제가 하나 있다. 바로 데이터 입력 순서에 따라서 트리의 모양이 달라진다는 것. 이게 왜 문제인가 라는 의문이 있을 수 있는데, 바로 이 때문에 탐색 시간의 차이가 생길 수 있기 때문이다. 필연적으로 데이터 중에서 특별히 많이 검색되는 데이터가 있을 것이고, 그렇지 않은 데이터도 있을 ..

* 배열의 인덱스가 1부터 시작한다고 가정합니다. ([1] = 1번째 와 같이 이해하기 쉽도록) - 알고리즘 정의 각 vertex에서 다른 모든 vertices의 최단 경로를 구하는 알고리즘. (mulit source-multi destination) 비슷한 역할을 수행하는 알고리즘에는 다익스트라 알고리즘이 있다. (single source-multi destination) 이 알고리즘을 이해하기 위해 몇가지 규칙을 만들자. D(k)[i][j]: vertex i 에서 vertex j로 가는 최단 경로를 저장. 단, 최단 경로를 생성하는 vertex는 {v1, v2, ..., vk}에서만 사용할 것. D(0)[i][j]: vertex i 에서 vertex j로 가는 최단 경로지만, 경유하는 vertex가 ..

- 정의 (x+1)^n 의 항을 전개했을 때, x^k항의 계수가 C(n, k)로 표현된다. n개의 항목 중 k개를 순서를 고려하지 않고 선택하는 경우의 수로도 잘 알려져 있다. - Pseudocode // Iterative way (Dynamic programming) public static int binDP (int n, int k) { index i, j; int[][] B = new int[0..n][0..k]; for (i=0; i