음 아마 비둘기보단 똑똑할꺼야

2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 3강 분할정복 알고리즘 - 1

2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개

1. [복습] 분할정복 방법의 원리

순환적으로 문제를 푸는 하향식 접근 방법
주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식

'분할' - '정복' - 결합

특징
- 분할된 문제는 원래 문제와 동일(입력 크기만 감소) 하고 서로 독립적

적용 알고리즘
- 이진 탐색, 퀵 정렬, 합병 정렬, 선택 문제

 

2. 합병 정렬

분할 정복 방법을 가장 잘 표현하고 있는 알고리즘이다.

배열을 동일한 크기의 두 개의 부분배열로 분할하고,
각각의 부분배열을 순환적으로 정렬한 후, (정복)
정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦.

분할: 입력 크기 n인 배열을 크기 n/2 인 두 부분배열로 분할
정복: 각 부분배열에 대해서 합병 정렬을 순환적으로 적용하여 두 부분배열을 정렬
결합: 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

합병 정렬에서 분할은 신경쓸 필요없다. 합병이 중요한 부분이다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
MergeSort(A[], n){
    if(n > 1){
        Mid = n/2;
        B[0..Mid-1= MergeSort(A[0..Mid-1], Mid);
        C[0..n-Mid-1= MergeSort(A[Mid..n-1], n-Mid);
        A[0..n-1= Merge(B[0..Mid-1], C[0..n-Mid-1], Mid, n-Mid);
    }
    return A;
}
 
Merge(B[], C[], n, m)
{
    i = j = k = 0;
    while(i<&& j<m){
        if(B[i] <= C[j]){
            A[k++= B[i++];
        }else{
            A[k++= C[j++];
        }
    }
    for(; i < n; i++) A[k++= B[i];
    for(; j < m; j++) A[k++= C[j];
    return A[0..n+m-1];
}
cs

 

성능 분석

두 부분배열 간의 비교 횟수 n/2 ~ ( n/2 + n/2 -1 = n - 1 )
최악의경우: Θ(n)
입력 데이터 개수만큼의 저장 장소가 추가로 필요하다.

합병 정렬 MergeSort() 수행시간
- 크기 n/2 인 두 번의 MergeSort() 순환 호출 + 한 번의 합병 Merge()
T(n) = T(n/2) + T(n/2) + Θ(n) (n>1)
T(1) = 1
                  ▼▼▼
         T(n) = 2T(n/2) + Θ(n)
                  ▼▼▼
             T(n) = O(nlogn)

퀵 정렬과 동일한 수행시간을 갖는다.

 

3. 선택 문제

선택문제란?
n개의 원소가 임의의 순서로 저장된 배열 A[0..n-1]에서 번째로 작은 원소를 찾는 문제

i = 1 > 최솟값
i = n/2 > 중간값
i = n > 최댓값

직관적인 방법
- 오름차순으로 정렬한 후 i번째 원소를 찾는 방법 > O(nlogn)
- 최솟값 찾는 과정을 i번 반복((i-1)번째까지는 최솟값을 찾은 후 삭제) > O(in)

최악 O(n2제곱), 평균 O(n) 알고리즘
최악 O(n), 평균 O(n) 알고리즘

3-1) 최솟값 찾기
각 데이터를 하나씩 모두 비교하는 방법
n개의 데이터에 대해서 최소한 (n-1)번의 비교가 필요 > O(n)

3-2) 최솟값과 최댓값 모두 찾기

최솟값 찾은 후 최댓값 찾는 방법(또는 최댓값 찾은 후 최소값 찾기)
n개의 데이터에서 최솟값을 찾는데 (n-1)번의 비교
 + (n-1)개의 데이터에서 최댓값을 찾는데 (n-2)번의 비교
==> 2n - 3 번의 비교

2n-3번의 비교가 아닌 (3/2)n -2번의 비교로 수행 가능
모든 원소를 두 개씩 짝을 이루어 동시에 최솟값/최댓값과 비교

1
2
3
4
5
6
7
8
9
10
11
12
FindMinMax(A[], n, min, max)
{
    if(A[0< A[1]){ min = A[0]; max = A[1]; }
    else { min = A[1]; max = A[0]; }
    for (i = 2; i < n; i++){
        if(A[i] < A[i+1] { small = A[i]; large = A[i+1]; }
        else { small = A[i+1]; large = A[i]; }
        
        if ( small < min ) min = small;
        if ( large > max ) max = large;
    }
}
cs

3-3) i번째로 작은 원소 찾기_ 최악 O(n2제곱), 평균 O(n)

개념과 원리
퀵 정렬의 분할 함수 Partition()을 순환적으로 적용한다.

분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할, i가 피벗의 인덱스와 같으면 피벗의 값을 반환하고 종료
정복: 인덱스 i가 포함된 부분배열에 대해서 선택 알고리즘을 순환적으로 적용
결합: 필요없음

1
2
3
4
5
6
7
8
9
10
11
12
int Selection(A[], n, i)
{
    Left = 0; Right = n -1;
    p = Partition(A, n);
    
    if(i == p + 1)
        return A[p];
    else if ( i < p + 1)
        Selection(A[Left..p-1], (p-1)-Left+1, i);
    else
        Selection(A[p+1..Right], Right-(p+1)-1, i-p-1);
}
cs

성능 분석

최악의경우 = 퀵 정렬의 최악의 경우
- 분할 함수가 항상 하나의 부분배열만 생성하는 경우
- 오름차순으로 정렬된 상태에서 i = n 을 찾는 경우 > 분할 함수 호출할 때 마다 피벗의 인덱스는 1씩 증가 > Partition()을 O(n)번 호출 => O(n제곱)
- 해결책 > 항상 일정한 비율의 두 부분배열로 분할, 최악의 경우에도 O(n)]

평균적인 경우 O(n)

 

3-4) i번째로 작은 원소 찾기_최악 O(n), 평균 O(n)

개념과 원리
특정한 성질을 만족하도록 피벗을 선택
> 항상 일정한 비율의 두 부분배열로 분할

피벗선택방법
① 크기 n인 배열의 원소를 5개씩 묶어 n/5개의 그룹 형성
- 5의 배수가 되지 않아 그룹을 생성하지 못한 채 남는 원소는 그대로 남겨 둔다.
② 각 그룹에 대해서 중간값을 찾음
③ n/5 개의 중간값들을 대상으로 다시 중간값을 찾음 > "중간값들의 중간값" => "피벗"

2018/05/22 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 2강 알고리즘 소개

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개

 

1. 분할정복 방법의 원리

  • 순환적으로 문제를 푸는 하향식 접근 방법
    주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식
  • 특징
    분할된 작은 문제는 원래 문제와 동일 → 단, 입력 크기만 작아진다.
    분할된 문제는 서로 독립적 → 순환적 분할 및 결과 결합이 가능
  • 각 순환 호출 시의 처리 과정
    분할: 주어진 문제를 여러 개의 작은 문제로 분할
    정복: 작은 문제들을 순환적으로 분할. 만약 작은 문제가 더 이상 분할되지 않을 정도로 크기가 작다면 순환호출 없이 작은 문제에 대한 해를 구함
    결합: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함.

1) 적용 알고리즘에서의 분할 과정

1-1) 이진탐색

중간 값을 기준으로 양쪽으로 분할한다. 한쪽은 사용 할 필요가 없다. 한쪽에서 분할 하고 분할하고 분할되지 않을때까지 분할한다.

n > n/2 , n/2 > n/4 , n/4 ...

1-2) 합병 정렬

정확히 절반크기의 두 개로 분할한다. 여기까지는 이진탐색과 동일하나 이진탐색은 한쪽은 사용하지않지만 합병정렬은 양쪽을 전부 사용한다.

n > n/2 , n/2 > n/4 , n/4 , n/4 , n/4 > ... 

1-3) 퀵 정렬

두개로 분할하는것은 맞으나 합병정렬은 정확히 두 개로 분할했다면 퀵정렬은 크기를 모름. 한쪽은 크고 한쪽은 작고 똑같을 수 도있고 크기가 다양한 일정하지않은 두 개로 분할하는 특징을 가진다.

n (=a+b) > a , b > ...

1-4) 선택 문제

 

 

2. 이진 탐색

  • 정렬된 상태의 데이터 대해 적용 가능한 효과적인 탐색 방법
    오름차순으로 정렬되었다고 가정

탐색방법

  • 배열의 가운데 원소와 탐색키 x(내가 찾고싶은 데이터) 를 비교
    1) 탐색키 = 가운데 원소 => 탐색 성공
    2) 탐색키 < 가운데 원소 => '이진탐색(크기 ½의 왼쪽 부분배열)' 순환 호출
    3) 탐색키 > 가운데 원소 => '이진탐색(크기 ½의 오른쪽 부분배열)' 순환 호출
  • 탐색을 반복할 때마다 대상 원소의 개수가 ½씩 감소

이진탐색의 분할 정복 결합 적용

  • 분할 : 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할. 탐색키와 가운데 원소가 같으면, 해당 원소의 배열 인덱스를 반환/종료
  • 정복 : 탐색키 x가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출
  • 결합 : 부분배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요

알고리즘_(순환형태)

1
2
3
4
5
6
7
8
BinarySearch(A[], Left, Right, x)
{
    if(Left > Right) return -1// 탐색실패
    Mid = (Left + Right)/2;
    if(x==A[Mid]) return Mid;
    else if (x<Mid) BinarySearch(A, Left, Mid-1, x); // 왼쪽 부분배열
    else BinarySearch(A, Mid+1, Right, x); // 오른쪽 부분배열
}
cs

     알고리즘 (반복형태)

1
2
3
4
5
6
7
8
9
10
11
BinarySearch_Iteration(A[], n, x)
{
    Left = 0; Right = n-1;
    While(Left <= Right){
        Mid == (Left+Right) / 2;
        if(x==A[Mid]) return Mid;
        else if (x<Mid) Right = Mid - 1// 왼쪽 부분배열
        else Left = Mid + 1;    // 오른쪽 부분배열
    }
    return -1// 
}
cs

 

이진 탐색에서의 분할과 비교

  • 입력 크기 n 일 때 최대 분할 횟수는?

n/2의k제곱 = 1 이 될때 까지 → k = log n

  • 최대 비교 횟수는? "최대 분할 횟수 + 1"

    예시) 입력 데이터 크기 n = 8 일 경우 최대 분할 횟수 k = 3이다 8/2의3제곱 = 1 이므로...
         최대 비교 횟수는 최대 분할 횟수 k 에 1을 더한 값이므로 3 + 1 = 4 이다.


성능 분석

T(n) = 입력 크기 n에 대한 탐색 과정에서의 모든 비교 횟수의 합
     = 맨 바깥 수준에서의 비교 횟수 + 순환 호출에서의 비교 횟수

T(n) = T(n/2) + O(1) (n>1), T(1) = 1

T(n) = logN

이진탐색 특징

  • 입력이 정렬된 리스트에 대해서만 적용 가능

  • 삽입 / 삭제 연산 시 데이터의 정렬 상태 유지가 필요
    평균 n/2개의 데이터 이동이 발생 > 삽입/삭제가 빈번한 응용에는 부적합하다.

 

3. 퀵 정렬

특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식
- 오름차순으로 정렬한다고 가정한다.

피벗 pivot
두 부분배열로 분할할 때 기준이 되는 특정 원소 (보통 주어진 배열의 첫 번째 원소로 지정)

(피벗을 기준으로 왼쪽과 오른쪽으로 나누고 각각의 부분배열에 대해서 퀵정렬을 순환적으로 한다.)

 

1) 피벗이 제자리를 잡도록 하여 정렬하는 방식

분할 전 데이터 : 30, 45, 20, 15, 40, 25, 35, 10

1. (첫 데이터인 30을 피벗으로 정한다.)

분할 후 : { 25, 10, 20, 15 } 30 { 40, 35, 45 }
             왼쪽 부분배열       오른쪽 부분배열

피벗을 기준으로 보았을 때 왼쪽부분배열의 모든값은 피벗보다 작은 값들이다.
오른쪽 부분배열의 모든 값은 피벗보다 다 크다.

 

  • 분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할

  • 정복: 두 부분배열에 대해서 퀵 정렬을 순환적으로 적용하여 각 부분배열을 정렬

  • 결합: 필요없음

 

2) 알고리즘

1
2
3
4
5
6
7
8
QuickSort(A[], n)
{
    if(n>1){
        pivot = Partition(A[0..n-1], n);    // 두 부분배열로 분할
        QuickSort(A[0..pivot-1], pivot);     // 왼쪽 부분배열에 대한 순환 호출
        QuickSort(A[pivot+1..n-1], n-pivot-1);    //오른쪽 부분배열에 대한 순환 호출
    }
}
cs

 

알고리즘 분할함수 Partition()

1
2
3
4
5
6
7
8
9
10
11
12
13
int Partition(A[], n)
{
    Left = 1; Right = n-1;
    while(Left < Right){                // 피벗 A[0]
        // 피벗보다 큰 값의 위치를 찾음
        while(Left < n && A[Left] < A[0]) Left++;
        // 피벗보다 작은 값의 위치를 찾음
        while(Right > 0 && A[Right] >= A[0]) Right--;
        if(Left < Right) 교환(A[Left] ↔ A[Right])
        else 교환(A[0] ↔ A[Right])
    }
    return Right;
}
cs

 

3) 분할과정

 

퀵 정렬의 적용 예

85보다도 88 피벗이 더 큰값이므로 맨오른쪽에 무한대의 값이 있다고 가정한다.

 

4) 성능분석

4-1) 분할함수 Partition() 수행 시간

피벗을 제외한 모든 원소는 1번~ 최대 2번 비교한다.
n ~ 2n
선형시간 Θn 을 갖는다.

4-2) 퀵 정렬 Quicksort() 수행 시간

한 번의 분할 Partition() + 두 번의 Quicksort() 순환 호출
T(n) = T(배열) + T(배열) + Θ(n) (n > 1)
T(1) = Θ(1)

 

4-3) 최악의 경우

피벗만 제자리를 잡고, 나머지 모든 원소가 하나의 부분배열로 분할되는 경우

극심한 불균형적 분할
- 피벗만 제자리를 잡고, 나머지 모든 원소가 하나의 부분배열로 분할되는 경우
- 피벗이 항상 부분배열의 최솟값 또는 최댓값이 되는 경우
- 입력 데이터가 정렬된 경우 AND 피벗을 배열의 처음 원소로 지정한 경우

T(n) = (Tn-1) + T(0) + Θ(n) (n>0), T(0)=0
                        ▼▼▼
                T(n) = T(n-1) + Θ(n)
                        ▼▼▼
                   T(n) = O(n2제곱)

 

4-4) 최선의 경우

피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우

가장 균형적인 분할
- 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우
- 피벗이 항상 부분배열의 중간값이 되는 경우

T(n) = T(n/2) + T(n/2) + Θ(n) (n>1)
T(1) = 1
                        ▼▼▼
            T(n) = 2T(n/2) + Θ(n)
                        ▼▼▼
                    T(n) = O(nlogn)

 

4-5) 평균적인 경우

부분배열의 모든 분할 비율에 따른 수행시간의 평균
- 피벗은 동일한 확률로서 분할 후 배열의 어느 곳에나 위치 가능
- 0:n-1, 1:n-2, 2:n-3, ... , n-2:1, n-1:0

T(1) = T(0) = 0
T(n) = 1/n n∑i=1 (T(I-1) + T(n-I)) + Θ(n),  n ≥ 2
                        ▼▼▼
                     T(n) = O(nlogn)

퀵 정렬의 특징

  • 최선/평균의 경우 → O(nlogn)
  • 최악의 경우 → O(n2제곱)
    최악을 피하고 싶다면... 피벗 선택의 임의성만 보장되면 평균적인 성능을 보일 가능성이 매우 높음
    배열에서 임의로 값을 선택해서 배열의 처음 원소와 서로 교환한 후 정렬 수행

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [알고리즘] 1강 알고리즘 소개

1. 알고리즘의 설계

1) 최댓값 찾기

1-1) 값들을 하나씩 모두 비교해 가면서 최댓값을 찾는 방법
1-2) 토너먼트 방식
    둘씩 비교해서 큰값을 찾아가는 방법
더 효율적인것을 결정해야한다.

(n-1)번 1-1과 1-2 의 효율성은 7번으로 같다.

2) 뒤섞인 카드에서 원하는 카드 찾기

2-1) 순차탐색(Sequential Search) 순차적으로 전부 다 뒤집는다

1
2
3
4
5
6
7
8
SequentialSearch(A[], n, x)
// 배열 A[0..n-1]에서 x를 찾는 알고리즘
{
    for(i = 0; i < n; i ++){
        if(x == A[i]) return i;
    }
    return -1;
}
cs

모든 배열의 원소를 전부 다 비교


2-2) 카드가 오름차순으로 나열되어 있다면 이진탐색(binary search)

1
2
3
4
5
6
7
8
BinarySearch(A[], Left, Right, x)
{
    if(Left>Right) return -1;
    Mid = (left + right) / 2;
    if(x == A[mid]) return Mid;
    else if (x<A[mid]) BinarySearch(A, Left, Mid-1, x)
    else BinarySEarch(A,Mid+1,Right,x);
}
cs

데이터가 뒤죽박죽일때는 순차탐색, 정렬되어있다면 이진탐색이 더 좋다.

> 주어진 문제, 속성, 조건 등의 매우 다양
 => 일반적이고 범용의 기법은 미존재

> 대표적인 설계 기법
- 분할정복 divide and conquer 방법
- 동적 프로그래밍 dynamic programming 방법
- 욕심쟁이 greedy 방법

2. 알고리즘의 분석

1) 정확성 분석 (다루지않음 이미 정확하다고 증명이 된 알고리즘만 학습한다.)

  • 유효한 입력, 유한 시간 → 정확한 결과 생성하는가?
    다양한 수학적 기법을 사용해서 이론적으로 증명이 필요하다.

2) 효율성 분석 (보통의 알고리즘 분석은 효율성 분석을 말한다.)

  • 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정
  • 메모리 양 > 공간 복잡도 (space complexity)
    정적 공간 + 동적 공간
    (상대적으로 계산하기 쉬움)
  • 수행시간 > 시간 복잡도 (time complexity)
    (보통의 효율성 분석은 시간복잡도를 분석하는것을 말한다.)
    시간이 덜 걸리는것이 효율성이 높다.

    알고리즘을 프로그램으로 구현해서 이를 컴퓨터에서 실행시켜 실제 수행시간을 측정
  • 이런 방법은 일반적이지 못하다!
    컴퓨터 속도, 사용한 프로그래밍 언어, 프로그램 작성방법, 컴파일러의 효율성 등에 종속적이기 때문!


    > 알고리즘이 수행하는 기본적인 연산의 횟수의 합
  • 시간 복잡도에 영향을 미치는 요인?
    - 입력으로 제공되는 데이터 크기 ("입력 크기")
    - 입력 데이터의 상태

3) 시간 복잡도

  • 입력크기 n 이 증가하면 수행 시간도 증가
    > 단순히 단위 연산의 개수가 아닌 입력 크기의 함수로 표현한다.
  • 입력 데이터의 상태(ex:정렬 비정렬)에 종속적
    - 평균 수행시간
    - 최선 수행시간 (데이터가 가장 이상적인 상태로 제공되었을 경우)
    - 최악 수행시간 (가장 데이터가 좋지않은 상태로 제공되었을 경우)
    평균수행시간이 가장 좋지만 평균수행시간을 계산이 쉽지않다. 그러므로 최악의 수행시간을 가지고 시간복잡도를 측정한다. 최악의 수행시간을 기준으로 같거나 적게 걸린다가 되므로 기준은 최악의 수행시간을 기준으로 가진다.
1
2
3
4
5
6
7
8
9
10
11
SumAverage(A[], n)
//A[0.. n-1], n : 입력 배열과 데이터 개수
    sum = 0;
    i = 0;
    while(i<n){
        sum = sum + A[i];
        i = i + 1;
    }
    average = sum / n;
    print sum, average;
}
cs

 

시간복잡도와 점근성능 빅오 표기법으로 까지 도출 할 수 있어야 한다.

 

3. 점근 성능

정의: 입력크기 n이 무한대로 커짐에 따라 결정되는 성능

데이터의 개수가 증가한다. 15개를 기준으로 효율성의 크기가 달라진다.

수행시간의 다항식 함수에서 최고차항만을 계수 없이 취해서 표현
(최고차항만이 가장 큰 영향력을 행사하기 때문이다.)
수행시간의 어림값, 수행 시간의 증가 추세 파악이 용이 > 알고리즘의 우열을 표현

1) 점근성능의 표기법

1-1) 정의 'Big-oh' 점근적 상한 (최악의 수행시간)

어떤 양의 상수 c와 n0이 존재하여 모든 n≥n0에 대하여 f(n)≤cㆍg(n)이면 f(n) = O(g(n))이다.

1-2) 'Big-omega' 점근적 하한 (최선의 수행시간)

어떤 양의 상수 c와 n0이 존재하여 모든 n≥n0에 대하여 f(n)≥cㆍg(n)이면 f(n)=Ω(g(n)) 이다.

1-3) 'Big-theta' 점근적 상하한 (알고리즘의 수행시간을 좀 더 엄밀하게 나타낼 수 있다)

어떤 양의 상수 c1, c2와 n0이 존재하여 모든 n≥n0에 대하여 c1ㆍg(n)≤f(n)≤c2ㆍg(n) 이면 f(n) = Θ(g(n)) 이다.

(점근적 상하한)

 

2) 주요 O-표기 간의 연산 시간의 크기 관계


◀◀◀효율적                                                                                                                    비효율적▶▶▶
상수시간: 데이터의 개수와 상관없이 소요시간은 일정하다.

 

3) 효율적인 알고리즘의 중요성

 

4) 알고리즘의 시간 복잡도 구하기

알고리즘에 나타난 루프의 반복횟수를 조사하여 시간 복잡도로 취함
g(n)은 최고 차수에 의존

 

4. 순환 알고리즘의 성능

1) 순환 recursion, 재귀
알고리즘의 수행 과정에서 자기 자신의 알고리즘을 다시 수행하는 형태

BinarySearch() 를 계산하면 T(n) = T(n/2) + O(1), T(1) = c1

이진탐색의 수행시간은 O(log n) 이다.

일일이 점화식으로 계산하기엔 여간 복잡한게 아니다.

모두 다 기억하긴 어렵지만 2,3,6번은 기억해야한다.

한가지만 기억해도 본전 뽑는다 최! 고! 차! 항! 만 기억하자!

2018/05/18 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 8강 데이터의 저장

2018/05/17 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 6강 정규형의 적용

2018/05/15 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 5강 정규화 기초

2018/03/21 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 4강 데이터베이스 언어

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 3강 관계형 모델

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 2강 데이터베이스 모델링

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 1강 데이터베이스의 이해

 

DBMS가 데이터를 가져오는 속도가 늦다면 쓰기 굉장히 싫어질꺼다... 비효율적

인덱스는 우리나라말로 찾아보기 라는 뜻이다.

인덱싱이 어떻게 내부적으로 구성되고 동작하여 DBMS가 데이터를 빠르게 찾아줄 수 있는지 알아보도록 하자.

1. 인덱싱

1) 데이터 검색 과정

  • 비효율적 과정
    디스크에 데이터 모음이 있다면~
    메모리에 블럭단위로 읽어와서 첫번째 레코드부터 검색 할 데이터가 있는지 검색하여 원하는 결과가 나올 때 까지 읽는다.

2) 인덱스의 개념

  • 데이터 검색에서 발생하는 비효율적인 문제를 해결을 목적으로 시작
    - 인덱스: DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 하는 데이터와 관련된 부가적인 구조
    - 인덱싱: 인덱스를 디자인하고 생성하는 작업
  • 인덱스와 검색키(특정컬럼값)를 통하여 레코드가 디스크 저장장치 또는 메모리의 어느 블럭에 저장되어 있는지 파악하고, 해당 블럭을 빠르게 적재한다.

검색키?
파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

  • 1번의 데이터 검색과정의 효율적인 과정
    메모리에 적재하기 전에 디스크에 인덱스를 생성 해 놓는다.
    예시)이름을 검색키로 놓고 각각에 해당하는 레코드가 어디있는지 포인터를 가지고 있다.
    메모리에 인덱스(검색키+포인터)를 적재(블럭단위 적재보다 더 많은 인덱스 데이터를 적재 가능)해서 검색한다.
  • 인덱스의 단점은 디스크에 추가적인 데이터(검색키 + 포인터)를 저장하기 때문에 용량을 조금 더 많이 먹는다가 단점이 될 수 있다.

3) 인덱싱의 개념

  • 인덱스의 종류
    - 순서 인덱스: 특정 값에 대해 정렬된 순서 구조
    - 해시 인덱스: 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어느 버킷에 할당되는지 결정
  • 인덱스의 평가기준
    - 접근 시간: 데이터를 찾는 데 걸리는 시간
    - 유지 비용: 새로운 데이터 삽입 및 기존 데이터 삭제 연산으로 인한 인덱스 구조 갱신 비용
    - 공간 비용: 인덱스 구조에 의해 사용되는 부가적인 공간 비용

 

2. 순서 인덱스

1) 순서 인덱스의 특징

  • 검색키로 정렬된 순차 파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 순서 인덱스를 사용
    - 검색키를 정렬하여 해당 검색키와 관련된 레코드와의 연계를 통하여 인덱스 생성

2) 인덱스의 구성

  • 인덱스 엔트리의 구조


설명.
덱스 엔트리는 [검색키값] 과 [포인터]로 구성되어 있는데 [포인터]는 또 두 개의 항목,
[블럭ID] 와 [오프셋]으로 구성되어 있다.
예를 들어 검색키 값이 20140001이고 블럭ID가 b2 오프셋이 30이면
블럭ID가 b2 에서 30바이트만큼 떨어져 있는 곳에 20140001 이라는 검색키값을 가진
레코드가 있다 라는 뜻

  • 순서 인덱스의 분류
    - 밀집(dense) 인덱스
    - 희소(sparse) 인덱스

3) 밀집 인덱스

모든 레코드에 대해 [검색키값+포인터] 쌍을 유지

 

4) 희소 인덱스

인덱스의 엔트리가 소수의 검색키 값만을 유지

설명.
검색키값 14001에 해당하는 레코드를 찾으려 한다면 14001보다 작은 값 중에 가장 큰 값을 가진 검색키 값을 찾는다.
14001이 나올 때 까지 다음 값을 순차적으로 읽어들인다.
희소인덱스는 듬성듬성 인덱스를 구성하지만 내부적으로 레코드를 가지고와서 다시 레코드를 찾아봐야한다는 단점이 있지만 인덱스에 해당하는 데이터의 양이 밀집인덱스보다 작기 때문에 레코드가 엄청 큰 릴레이션에서도 비교적 적은 크기의 인덱스 데이터를 가질 수 있다.

5) 다단계 인덱스

밀집 , 희소 인덱스의 장단점을 잘 섞어보자 해서 나온 인덱스

  • 4KB 크기의 블럭에 100개의 엔트리가 삽임될 때, 100,000,000 개(1억개)의 레코드에 대한 순서 인덱스
    - 1,00,000개(백만개)의 블럭 = 4GB의 공간 필요
    (4GB를 메모리에 적재하는건 불가능에 가까움)

  • 인덱스 크기에 따른 검색 성능
    - 인덱스 크기 < 메모리 크기
    디스크 I/O 이 줄어 탐색 시간이 축소
    - 인덱스 크기 > 메모리 크기
    저장된 블럭을 여러번 나누어 읽어야 하기 때문에 디스크 I/O 비용이 증가하여 탐색 시간이 증가

  • 내부 인덱스와 외부 인덱스로 구성
    - 외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블럭을 지칭
    - 포인터가 가리키는 블럭을 스캔하여 원하는 레코드보다 작거나 같은 검색키 값 중에 가장 큰 값을 가지는 레코드를 탐색
    (내부 인덱스를 밀집 인덱스에 가깝게 구성하고 내부인덱스 위에 외부 인덱스를 희소인덱스에 가깝게 만들어 여러 층으로 구성되도록 한다.)

  • 내부 인덱스는 1,000,000개의 블럭을 갖고, 외부 인덱스는 100개의 블럭만 사용하여 40MB 크기의 외부 인덱스로 메모리에 적재 가능

 

3. B+ - 트리 인덱스

1) B+ 트리의 원형

2) B+ 트리의 구조

  • 루트 노드로 부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
    - 순서 인덱스(밀집인덱스)는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
    - 현재까지도 널리 사용되는 대표적인 순서 인덱스

  • B+ 트리의 노드 구조

하나의 노드의 사이즈가 일반적인 블럭 사이즈로 구성되고 여러 개의 검색키가 노드 안에 존재한다. K1 ~ Kn개의 검색 키가 있고 P1포인터를 따라가면 K1의 검색키보다 숫자가 작은것 혹은 알파벳이 앞선 것만 있고 P2는 K1과 K2사이의 순서에 존재하는 검색키의 존재만 위치하는 식으로 구성되어있다.

3) B+트리의 구성 요소

  • 인덱스 세트: 루트노드와 중간노드로 구성
    - 단말노드에 있는 검색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용
    - [n/2] ~ n 사이의 개수를 자식으로 소유
    (원하는 레코드가 어디에 있는지 찾기 위해서 힌트를 제공한다 즉, 인덱스세트에는 원하는 레코드가 어디에 가면 찾을 수 있는지 힌트만 제공하는 역할을 한다.) 

  • 순차 세트: 단말노드로 구성
    - 모든 노드가 순차적으로 서로 연결

    (B+트리는 인덱스 세트와 순차 세트로 구성되어있다.)

4) 단말노드의 예

 

5) B+ 트리의 예

단말노드에 포인터는 실제 레코드가 디스크에 어디에 있는지 가리키는 포인터다.

 

6) B+트리의 특징 (외우지않아도 된다. 참고사항일 뿐)

  • 루트는 2, 혹은 [n/2] ~ n 개 사이의 포인터를 가짐

  • 루트와 단말 노드를 제외한 모든 노드는 최소 [n/2]에서 n개 사이의 포인터를 가짐

  • 모든 단말 노드는 루트로부터 같은 거리
    (높이균형트리이기때문)

  • 단말 노드가 아닌 노드에 있는 검색키 값의 수는 그 (중간)노드의 포인터 수보다 하나 작음

  • 단말 노드는 데이터 파일의 순차 세트를 나타내며 모두 리스트로 연결

  • 단말 노드는 적어도 [(n-1)/2] 개의 검색키 값을 포함

 

7) '장보고' 검색

B+트리의 인덱스 첫번째 블럭만 읽어 온다. 정도전보다 크면 오른쪽 작으면 왼쪽으로 가도록 한다.
장보고는 정도전보다 가나다 순에서 작은 범위이므로 왼쪽.
정도전의 왼쪽 포인터를 따라가서 해당 블럭을 가져온다.
'안창호'의 ㅇ 보다 '장보고'의 ㅈ 이 가나다순에서 더 크므로 오른쪽 포인터의 블럭을 디스크에서 읽어온다.
불러온 블럭을 장보고와 같은 검색키값이 있는지 하나씩 비교한 다음 '장보고' 검색키값이 일치하면 왼쪽 포인터에 해당하는 레코드를 읽어온다.

네 번 만에 장보고 레코드를 읽어 올 수 있었다. (겁나 빠름)

 

8) B+ 트리 상에서의 삽입, 삭제(유지비용)

  • 레코드 삽입, 삭제 시 B+트리 또한 수정
    - 레코드 삽입: 노드에서 유지해야 할 검색키 값과 포인터 수 증가로 인해 노드를 분할해야 하는 경우가 발생
    - 레코드 삭제: 노드에서 유지해야 할 검색키 값과 포인터 수 감소로 인해 노드를 병합해야 하는 경우가 발생
    - 높이 균형 유지: 노드가 분할되거나 병합되면서 높이의 균형이 깨지는 경우가 발생

9) B+트리 상에서의 삽입과 삭제

  • 삽입: 검색과 같은 방법을 사용하여 삽입되는 레코드의 검색키 값이 속할 단말 노드를 탐색
    - 해당 단말 노드에 <검색키, 포인터> 쌍을 삽입
    - 삽입 시 검색키가 순서를 유지

  • 삭제: 삭제될 레코드의 검색키를 통해 삭제될 검색키와 포인터를 포함한 단말 노드를 탐색
    - 같은 검색키값을 가지는 다중 엔트리가 존재할 경우, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 탐색 후 단말 노드에서 제거
    - 단말 노드에서 제거된 엔트리의 오른 쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동

10) 노드가 분할되는 삽입

  • '강감찬' 삽입

삽입하기위해 '강감찬'이 들어가야 할 위치를 검색한다. 이 때 검색은 위에 '장보고'를 검색했을 때와 동일한 방법으로 검색한다.
'김영희' '나태양' '도철수'가 있는 블럭에 삽입되어야한다.
하지만 해당 블럭은 꽉 차 있어 들어갈 수 없으므로 분할 해야 한다.
'강감찬'과 '김영희'를 하나의 단말 노드로 구성하고 '나태양'과 '도철수'를 하나의 단말 노드로 구성시킨다.

(빈 공간이 있으면 그냥 넣으면된다.)
노드가 분할이 되면 단말노드가 하나였던것이 두 개가 되므로 부모 노드(중간 노드)에 새로운 포인터를 추가로 삽입해줘야 한다.

▼ 부모 노드(중간노드) 변경 후 ▼

11) 노드가 병합되는 삭제

  • '강감찬'이 추가된 B+트리에서 피천득 삭제
    - 피천득이 있는 단말 노드를 검색
    해당 단말 노드는 삭제 후 홍길동만 남게 됨
    [(n-1)/2] 개 보다 적은 검색키 값이 적으므로 다른 노드와의 병합이 필요

    - 홍길동이 저장 된 노드의 왼쪽의 형제 노드와 병합
    홍길동을 포함한 엔트리를 형제 노드로 이동
    비워진 노드를 삭제
    비워진 노드를 가리키는 포인터도 삭제
    기존의 포인터를 대체할 '정도전'을 부모 노드에 삽입

 

 

 

2018/05/17 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 6강 정규형의 적용

2018/05/15 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 5강 정규화 기초

2018/03/21 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 4강 데이터베이스 언어

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 3강 관계형 모델

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 2강 데이터베이스 모델링

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 1강 데이터베이스의 이해

 

DBMS가 내부적으로 데이터를 어떻게 저장하는지 알아보도록 하자

1. 파일 구성

1) 물리적 저장장치

물리적 저장장치는 데이터 접근 속도, 용량을 기준으로 다양한 장치로 구성

레지스터 → 캐시 → 메인메모리 → 자기디스크, 플레시메모리 → 광학 디스크, 자기테이프

◀◀◀◀◀◀◀◀◀속도, 가격                                   저장용량▶▶▶▶▶▶▶▶▶▶▶

2) 저장장치별 특징

휘발성
- 캐시: 고비용 저장장치로 빠른 접근 속도를 보장
- 메인메모리: 실제 프로그램과 데이터 적재 공간
- 플래쉬 메모리: 메인메모리와 유사하나 비휘발성

비휘발성
- 자기디스크: 데이터베이스 전체를 안정적으로 저장 (비휘발성 중 가장 빠름)
- 광학 디스크 드라이브: CD, DVD, Blue-ray 등
- 테이프 장치: 용량이 크고 저렴하나 순차 접근 방식으로 접근 속도가 매우 느림

3) 데이터베이스 구성

데이터베이스는 여러 개 의 파일로 구성되어있다. 사용자가 보았을때 DBMS만 보이지만 DBMS는 여러 개 의 파일로 관리하고 있다.
각각의 파일은 여러 개 의 블록으로 나누어 저장 된다.
블록 내에서는 여러 개의 레코드가 저장되어있다.

DB > 파일 > 블록 > 레코드

파일: 데이터를 영구적으로 저장하기 위해 사용되는 가장 기초적인 구조
블록: 파일을 고정적인 길이로 분할하여 생기는 균등한 크기의 데이터 묶음
레코드: 블록을 구성하는 요소, 더 이상 분리될 수 없는 최소 데이터 저장 단위

4) 고정 길이 레코드

고정적인 바이트 수를 갖는 레코드를 저장하는 기법
고정길이일 경우 레코드의 컬럼 데이터타입 크기만큼 할당해서 블록에 저장하면 된다.

문제점:
문제점1. 레코드의 길이가 블록길이에 딱 맞춰 떨어지지않는 단점이 존재
블록의 길이가 레코드 길이로 정확히 나눠지지 않아 남은 공간을 비워두는 방법 => 블록내의 남는 공간 낭비로 이어진다.
문제점2. 블록의 길이가 레코드 길이로 정확히 나눠지지 않아 한 레코드를 두 블럭에 나누어 저장하는 방법 => 레코드 접근 시 두 블록을 접근 (시스템에서는 두 블럭에 접근해야 하므로 부하가 늘어난다.)

문제점 1 , 2 두 가지 방법 모두 무엇이 더 낫고 더 나쁜지 비교할 수 없다. 혼용해서 적절하게 사용해야 한다.

레코드 삭제 시 문제
- 해당 레코드가 저장된 위치에 빈공간이 생성
- 장시간 레코드의 삽입 및 삭제 발생 시, 저장 공간에 많은 낭비가 발생

레코드 삭제 시 대처 방안
- 마지막 레코드로 공백 대체
- 삭제 리코드 이후의 레코드를 이동
- 가용 리스트 관리

5) 레코드 삭제 대처

5-1) 마지막 레코드로 공백 대체

이름이 장보고인 레코드가 삭제되었다면 맨 마지막 이름이 안창호인 레코드를 삭제된 레코드 위치에 위치시키는 방법
항상 마지막 블럭의 위치를 알고있어야하며 빈 공간을 삭제 후 마지막 공간까지 가서 끄집어 올려야 하므로 상당한 비용이 발생하는 방법

5-2) 삭제 레코드 이후의 레코드를 이동

이름이 장보고인 레코드가 삭제되었다면 이름이 나철수인 레코드부터 마지막 레코드까지의 위치를 한단계씩 위로 끄집어 올리는 방법
삽입되는 순서를 그대로 유지시킬 수 있는 장점이 있다. (검색을 빠르게 유지 가능)
나철수 부터 맨 마지막 레코드까지 한 단계씩 올려야 하므로 어마어마한 비용이 소요되는 단점이 존재.

5-3) 가용 리스트 관리

공백 레코드 포인터를 관리하는 방법.
삭제되는 레코드의 위치들을 공백 레코드가 관리하므로써 새로 삽입되는 레코드를 공백 레코드 포인터가 가지고있는 공백의 위치에 저장시키는 방법이다.
첫번째 방법을 개선시킨 방법이다.
하지만 단점인 레코드의 순서가 뒤죽박죽이 되는건 어쩔 수 없는 단점으로 존재한다.

6) 가변 길이 레코드(varchar)

블록에 저장되는 레코드의 길이가 서로 다른(가변적) 레코드를 할당하는 방법

가변 길이 레코드가 사용되는 상황
- 한 블록 내에 저장되는 레코드 유형이 둘 이상
- 길이가 고정되지 않은 컬럼의 개수가 하나 이상
- 레코드가 멀티셋을 허용한 컬럼을 가질 때

멀티셋
레코드의 컬럼값이 여러 개인 컬럼

가변 길이 레코드 형식
어디가 끝인지를 항상 기억하고 있어야된다는게 고정길이와의 차이점이다.

고정길이 레코드 먼저 블록의 첫번째에 채우기 시작하는데 처음 0~4바이트까지는 어디서부터 얼마만큼이 가변길이인지 정보를 저장해놓는 용도로 사용한다. 4바이트부터 고정길이 데이터를 채우기 시작해서 레코드의 컬럼에 고정길이 데이터가 저장이 끝나면 한 바이트에 NULL 을 입력하여 가변바이트의 시작을 구분한다.

6-1) 슬롯페이지 구조

7) 파일 구조화 방법

하나의 블록 내부에 레코드를 어떤방식으로 저장하는거였다면 지금부턴 각각의 레코드가 하나의 파일 내부에 몇번째 블록에 들어가야하는지 이다.

파일 구조화
- 파일 수준에서 레코드를 관리(순서 등)하는 기법

파일 구조화 방법의 종류
- 힙 파일 구조: 저장순서 고려없이 레코드를 파일 내 임의의 위치에 배치
(메모리)
- 순차 파일 구조: 레코드들이 특정 컬럼값을 기준으로 정렬되어 저장
(특정 컬럼값을 기준으로 계속 순서대로 저장, 검색에는 굉장히 빠름. 저장하는데는 최악 중간에 예상치 못한 순서의 레코드가 들어오면 순서를 맞추기 위해 재정렬하는 비용이 소요.)
- 해시 파일 구조: 레코드를 입력 받아 레코드가 저장 될 블록 주소를 반환하는 해시 함수를 사용
(해시 함수를 사용해서 레코드를 저장, 찾는데 삽입되는데 해시함수를 거쳐야 하기 때문에 비용이 소요되지만 힙과 순차의 중간정도의 파일 구조화 방법이다.)

7-1) 순차 파일 구조의 예
레코드가 검색키 순서대로 정렬
레코드가 파일에 삽입되는 시점에서 키 값이 부여
장점
- 검색키에 대한 정렬 연산이 불필요, 키 값들의 순서로 레코드를 판독하는 연산에 효율적
- 현재 레코드에서 정렬된 키 순서로 다음 레코드를 찾을 때 부가적인 블록 접근이 불필요
- 이진 탐색을 사용하면 더 빠르게 레코드를 검색
단점
- 레코드 삽입, 삭제에 많은 비용 소요

7-2) 다중 테이블 클러스터링 파일 구조
빈번히 조인되는 테이블을 하나의 파일에 저장하기 위한 구조
필요한 테이블이 미리 조인되어 저장

 

2. 저장장치 접근

파일은 논리적 관점에서의 저장 객체

실제 저장될 때에는 여러 개의 물리적 단위인 블록으로 저장
- 블록은 데이터의 전송 단위
- 일반적으로 2KB ~ 32KB 사용
- 블록 전송을 최소화 할 수록 입출력 소요 시간이 단축

> 사용 중인 블록을 지속적으로 메모리에 적재
> 한정적 공간으로 인하여 필요에 따라 특정 블록 할당 해지
> 메모리 내부에 버퍼라는 공간에 블록을 저장하고, 이를 관리하기 위한 버퍼 관리자를 사용

1) 버퍼 관리자

DBMS상의 소프트웨어는 필요한 블록이 있을 때 버퍼관리자에게 해당 블록을 요청
- 요청된 블록이 버퍼에 있다면, 버퍼 관리자는 블록이 위치한 메모리 주소를 프로그램에게 전달
- 요청된 블록이 없는 경우, 버퍼 관리자는 버퍼내의 새로운 공간을 할당하고 해당 블록을 적재
- 더 이상 적재할 공간이 없다면, 버퍼에 있는 기존 블록을 선택하여 할당을 해지하고 해당 블록을 적재

2) 버퍼 관리자의 기능

버퍼 교체 전략
- 가용 공간을 확보 하기 위해 기존에 적재된 블록의 할당을 특정 기준에 의하여 해지
- 미래에 가장 적게 사용될 블록을 선택하여 디스크로 내보내는 것이 이상적인 버퍼 교체 전략
- 버퍼 교체 전략 기법
> LRU(Least Recently Used): 최근에 가장 적게 참조한 블럭을 교체
> MFU(Most Frequently Used): 특정 기간동안 가장 여러 번 사용된 블록을 선택하여 블록을 교체

고정 블록
- 장애로 인하여 메모리의 데이터가 손실되어 작업이 중단될 경우, 중단된 작업의 결과물이 디스크에 기록되는 것을 방지
- 디스크 블록이 교체되는 것을 제한

블록 강제 출력
- 시스템 로그와 같이 중요한 데이터는 디스크에 영구적으로 기록되어야 함
- 버퍼 공간이 필요 없어도 강제로 디스크에 기록

2018/05/15 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 5강 정규화 기초

2018/03/21 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 4강 데이터베이스 언어

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 3강 관계형 모델

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 2강 데이터베이스 모델링

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 1강 데이터베이스의 이해

 

나쁜릴레이션은 데이터베이스를 운용하는데 굉장히 비효율적 및 이상현상을 일으키는 릴레이션이다.

(아직까지 악당은 남아있닼ㅋㅋㅋㅋㅋㅋ)

1. 정규형의 개념

1) 정규형

- 이상 현상을 최소화 하도록 특정 조건을 갖춘 릴레이션의 형식

- 정규형의 분류

정규형은 타 정규형을 내포하거나 내포당하고있다.
제1정규형이 가장 적은 조건, 가장 약한 형태의 정규형이라 한다.
실무에서는 BC정규형까지만 사용하고 4,5 정규형은 잘 사용하지 않는다.

2) 정규형의 목적

정의
특정 정규형의 조건을 만족하도록 릴레이션과 속성(컬럼)을 재구성하는 과정

※정규화의 기능
- 데이터베이스 내에 모든 릴레이션을 효과적으로 표현 (중복을 최소화해서 가장 적은용량으로 DB 구성)
- 보다 간단한 관계 연산에 기초하여 검색 알고리즘을 효과적으로 작성할 수 있도록 지원
- 바람직하지 않은 삽임, 수정, 삭제 등의 이상 발생 방지 (갱신 이상 방지)
- 새로운 형태의 데이터가 삽입될 때 릴레이션 재구성의 필요성을 축소

3) 제1정규형

- 가장 약한 조건을 갖춘 정규형
- 릴레이션의 모든 속성이 단일 값으로 구성되어야 하는 조건

정의
릴레이션 스키마에서 정의된 모든 속성의 도메인이 원자값(관계형모델의 가장 기본적인 제약조건)을 갖는 상태
=> 기본적으로 관계형 모델을 통해서 만들어진 모든 릴레이션은 제1정규형을 만족한다라고 할 수 있음.

3-1) 제1정규화가 필요한 릴레이션

입항시간이 값이 두 개, 출항시간이 값이 두 개, 목적이 두 개 인 레코드가 있다.
원자값이 아니기때문에 제1정규화가 필요하다.

제1정규화를 시킨 도크릴레이션

단일값만으로 이루어지게 만들기 위해 두번째 릴레이션과 세번째 릴레이션을 변경하였다.

 

4) 함수적 종속성 판결

정의 5강 참조

Q. 도크번호 → 도크관리자?
도크릴레이션을 보면 도크번호가 D1으로 모두 같다 일때 도크관리자는 김주연이고 D2일때 현익창이다
따라서 도크는 도크관리자를 종속한다.

Q. 목적 → 담당도선사?
목적이 선적으로 같은 두번째와 세번째 레코드가 같을 때 담당도선사가 김혜겸으로 같으므로 종속한다.

Q. 목적 → 도크번호?
첫번째와 두번째 레코드의 목적이 선적으로 같을 때 D1으로 같으므로 종속한다.
나머지는 목적컬럼의 값이 다르므로 볼필요없다.

같을때 같은지만 보면된다. (다~ 다르면 종속한다??)

 

5) 함수적 종속성 다이어그램

릴레이션 내의 속성간의 종속 관계를 직관적이고 이해하기 쉽게 도식화 한 표현 방식
- 직사각형: 속성 또는 속성 집합
- 화살표: 함수적 종속성

목적         →     담당도선사
(결정자)            (종속자)

6) 도크 릴레이션의 함수적 종속성 다이어그램

해석,풀이
- 도크번호가 도크관리자를 종속한다.
- 도크번호와 입항시간이 파란색 사각형으로 묶여있다. 이 말은 도크번호와 입항시간 두 개가 같이 출항시간과 목적 담당도선사를 각각 종속한다.
- 목적이 도크번호를 종속한다.
- 목적이 담당도선사를 종속한다.

 

2. 제2정규형

1) 제2정규형의 정의

릴레이션이 제1정규형을 만족하고 기본키의 부분집합이 특정 속성을 종속하고 있지 않은 상태

정의
주어진 릴레이션의 인스턴스가 기본키가 아닌 속성들이 기본키에 완전히 종속되어 있는 상태

2) 제2정규형의 적용

도크릴레이션의 도크번호와 입항시간에 밑줄이 그어져있으므로 도크릴레이션의 기본키에 해당한다.
도크번호와 입항시간이 출항시간,목적,담당도선사를 각각 종속한다.
여기서 문제는 도크관리자다. 도크관리자를 종속하고있는것은 도크번호이다.
기본키의 일부분인 도크번호가 도크관리자를 종속하고있다. 완전히 종속하고있지않은 부분적으로 종속하고있기 때문에 도크관리자 종속을 제거하면 제2정규형을 만족하게된다.
해결방법 = 기본키에 완전히 종속되도록 릴레이션을 분해해야한다.

3) 임의 분해(맘대로) 시 발생하는 문제점

- 불필요한 조인이 발생 (무리하게 릴레이션을 짤라서 2개의 릴레이션을 만들면 불필요하게 조인해서 검색해야한다. 조인은 DBMS에 많은 부하가 발생한다.)
- 원본 릴레이션 재구성이 불가능할 수 있다. (꼴리는데로 분해했다간 돌이킬 수 없는 강을 건너게된다.)

4) 릴레이션의 무손실 분해

정의
스키마 R에 함수적 종속성 X→Y가 존재하고 X∩Y=∮(X와 Y에 겹치는 컬럼이 없다) 이면, R을 R - Y 와 XY로 분해

도크관리 릴레이션 무손실 분해
- {도크번호} → {도크관리자}
- {도크번호} ∩ {도크관리자} =∮

도크관리 - {도크관리자}, {도크번호, 도크관리자}
도크릴레이션에서 도크관리자를 빼고 도크번호와 도크관리자만 존재하는 릴레이션을 추가적으로 생성한다. 이러면 조인했을 때 아무런 문제가 발생하지 않음.

조인해야하는 추가연산이 발생하지만 레코드가 줄어들으므로 용량이 줄어드는 효율성이 추가연산 단점보다 훨씬 크다.

5) 제2정규화의 함수적 종속성 다이어그램

 

3. 제3정규형

1) 제3정규화의 정의

정의
릴레이션이 제2정규형을 만족하고, 기본키가 아닌 속성들이 어떤 키에도 이행적으로 종속되지 않은 상태

이행적 종속이란?
X → Y 이고 Y → Z 이면 X → Z 이다.
(5강에 나왔었다 암스트롱 공리에서... 어휴 본인 비둘기인듯...)

2) 제3정규화의 적용

제2정규화가 된 도크릴레이션에서 도크번호와 입항시간은 목적을 종속하고 (X→Y) 목적이 담당도선사를 종속한다(Y→Z)
위 부분은 이행적 종속성에 해당한다.

{도크번호, 입항시간} → {목적}
                                {목적} → {담당도선사}
→ {담당도선사}

담당도선사를 빼버리자! 그러면 제3정규화가 적용된다!!

목적이 기본키이고 담당도선사를 종속하는 릴레이션을 새로 구축한다. 그리고 도크릴레이션에는 담당도선사만 제거한다.

4. BC정규형

1) BC정규형의 정의

정의
릴레이션이 제3정규형을 만족하고 릴레이션에서 성립하는 X→Y 형태의 모든 함수적 종속성에 대하여 X가 슈퍼키인 상태

슈퍼키: 기본키가 될 수 있는 컬럼

입출항관리 릴레이션(제3정규화가 적용된 도크릴레이션)의 함수적 종속성
- {도크번호, 입항시간} → {목적}
- {도크번호, 입항시간} → {출항시간}
- {목적} → {도크번호}

현상태에서 입출항관리 릴레이션에 BC정규화를 적용시키려면 목적→도크번호 를 따로 떼어내야한다.

2) BC정규화의 적용

항상 종속자를 떼어내는 것이고 결정자를 남겨둔다.
목적이 도크번호를 종속한다는것은 목적이 결정자가 되고 도크번호가 종속자가된다.
그러므로 도크번호를 떼어내야한다.
목적이 기본키이고 도크번호를 종속하는 릴레이션을 추가로 생성하고 기존 입출항관리 릴레이션에서 도크번호를 떼어낸다.
입출항관리 릴레이션의 기본키를 목적과 입항시간으로 두고 출항시간을 종속하도록한다.

 

2018/05/15 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 5강 정규화 기초

2018/03/21 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 4강 데이터베이스 언어

2018/03/19 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 3강 관계형 모델

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 2강 데이터베이스 모델링

2018/03/16 - [방송통신대학교/컴퓨터과학과 [3학년 1학기]] - [데이터베이스] 1강 데이터베이스의 이해


비효율성을 줄여야 DBMS를 효율적으로 사용할 수 있다.

이번 강의에서는 수학과 논리학이 조금 들어갈 수 있다.

1. 좋은 릴레이션과 나쁜 릴레이션

1) 나쁜 릴레이션의 예


(그림 나쁜릴레이션의 예)

등급과 할인율에 부분적인 중복이 발생하고 있다. 중복레코드는 존재하지않지만 중복의 문제를 내포하고있다.

2) 잘못된 데이터베이스 모델링

2-1) 데이터의 중복

2-2) 갱신 이상
- 삽입 이상: 레코드 추가 시 불필요한 컬럼의 값이 없이는 추가하지 못 하는 경우
- 삭제 이상: 삭제 시 의도하지 않았던 다른 데이터가 삭제되는 경우
- 수정 이상: 중복 저장된 레코드를 수정 시 모두 반영이 안되어 데이터베이스의 일관성이 깨지는 경우

2-3) 갱신 이상 - 삽입 이상
위 삽입된 그림에서 등급 신규 할인율 3프로를 추가하려면 나머지 3개 레코드(고객번호,고객명,전화번호)에 불필요한 정보를 추가하지않는이상 새로운 로우를 추가하지 못한다.    

2-4) 갱신 이상 - 삭제 이상
일반이나 VIP 등급을 삭제하고자할 때 등급과 할인율을 제외한 나머지 레코드 또한 삭제하지 않는 한 삭제하지 못하는 문제

2-5) 갱신 이상 - 수정 이상
일부에게만 할인율을 15프로 적용해놓고 추후 다른것에도 15프로를 적용하려다 수정에 실패한다면 비일관성이 발생한다.

3) 좋은 릴레이션의 개념

컴퓨터 프로그래머적 관점에서의 모델링 (어떻게 데이터를 저장해야 하는가?)
릴레이션의 스키마가 얼마나 효율적으로 실세계를 반영하고 있는지 평가하는 방법을 강구해야한다.
※ 고려사항
1. 한 릴레이션 내의 컬럼과 컬럼사이의 관계 분석
2. 갱신이상이 발생하지 않는지 데이터의 종속과 중복 제거
3. 새로운 컬럼들이 데이터베이스에 추가될 때, 기존 컬럼과의 관계 수정을 최소화

2. 함수적 종속성과 카노니컬 커버

나쁜릴레이션을 좋은릴레이션으로 바꾸려면??

1) 함수적 종속성
릴레이션 인스턴스를 분석하여 속성들(컬럼과 컬럼) 간의 연관관계를 표현한 것
릴레이션의 효율성을 향상시켜 좋은 릴레이션으로 변환하는데 이용되는 중요한 개념

정의
임의의 릴레이션 스키마 R의 인스턴스 r(R)에 포함되는 서로 다른 두 레코드 t1,t2와 속성 집합 X와 Y에 대해,
t1[X] = t2[X] 일 때, t1[y] = t2[y] 이면 함수적 종속성 X → Y가 성립한다.

2) 함수적 종속성의 판별

등급과 전화번호의 종속성
등급 컬럼과 전화번호 컬럼을 비교하였을때 등급이 같은 VIP 레코드더라도 전화번호 컬럼의 값은 다르다.
(X 의 컬럼값이 같으면 Y의 컬럼값도 같아야 종속성이 발생한다.)
* 그러므로 등급은 전화번호와 종속할 수 없다.

등급과 할인율의 종속성
등급이 일반으로 같다면 할인율도 5프로로 같은가?
등급컬럼의 값이 다를때는 신경쓸 필요가 없다. 같을때의 조건만 생각하면 된다.
등급한 할인율을 함수적으로 종속한다.
{등급} → {할인율}

3) 함수적 종속성의 확장

함수적 종속성은 릴레이션의 효율성 여부에 중요한 판단기준이 되지만 릴레이션의 인스턴스만으로 잠재된 모든 함수적 종속성을 찾아내기 어려움

판별되지 않은 모든 함수적 종속성을 찾기 위해 추론 규칙을 사용하여 확장

클로저(closure)
- 판별된 함수적 종속성 집합으로부터 유추할 수 있는 모든 함수적 종속성 집합 F+

4) 함수적 종속성 추론 규칙

4-1) 암스트롱 공리(Armstrong's axiom)

설명
재귀성: X의 컬럼이 Y의 컬럼값을 전부 내포하고 있다면, X가 Y를 종속한다.
부가성: X가 Y의 종속하고있다면 XZ가 YZ를 종속한다.
이행성: X가 Y를 종속하고 Y가 Z를 종속하면 X가 Z를 종속한다.
분해: X가 YZ를 종속하면 X가 Y를 종속한다. X가 Z를 종속한다. X가 Y 와 Z 를 각각 종속한다.
합집합: X가 Y를 종속하고 X가 Z를 종속하면 X가 YZ를 종속한다.
의사 이행성: X가 Y를 종속하고 WY가 Z를 종속하면 Y가 X로 대치가 되도 그대로 성립한다.

공리를 사용해서 클로저를 구할 수 있다.

(암스트롱 공리는 이해용도이다. 암기용도가 아님)

4-2) 함수적 종속성의 판별

고객번호 → 고객명
=> 고객번호가 다 다르므로 고객번호가 고객명을 종속할 수 없다. 고객명이 같아야 할 필요조차 없다.
같은 값이 없으므로 종속한다고 할 수 있다.

(여기서 약간 말이 웃기게 들리는데 고객번호가 고객명을 종속한다. 즉, 같은값이 있을때 같은값이 있으면 종속한다 라는게 정의 였다. 고객번호가 같은 값이 없으므로 고객번호가 고객명을 종속한다 라고 할 수 있다. 나도 이해가 잘 안된다...)

고객명 → 등급
=> 고객명의 레코드가 모두 다른 컬럼값이므로 고객명이 등급을 종속한다.

{고객번호, 고객명} → 할인율
=>고객번호와 고객명이 같은게 전혀없다 그러므로 종속한다.

위 종속성은 모두 유효한 함수적 종속성이다.

암스트롱 공리 의사 이행성에 따라 고객번호가 등급을 종속한다라고 할 수 있다.(고객번호 → 등급)

고객번호 → {고객명, 등급, 할인율}

5) 커버와 카노니컬 커버

5-1) 커버(cover)
정의
함수적 종속성들의 집합 E가 있을 때, E가 F+(클로저)에 포함되면 E의 모든 함수적 종속성이 F로부터 추론 가능 상태
=> F가 E를 커버 (E에 있는 의미가 F에 다 있다 라는 뜻)

5-2) 카노니컬 커버(canonical cover)
정의
F의 카노니컬 커버, Fc는 F+(클로저)에 존재하는 모든 함수적 종속성을 커버할 수 있는 최소한의 함수적 종속성들로만 이루어진 집합
설명: 함수적 종속성 집합(클로저) 안에는 불필요한 함수적 종속성을 많이 내포하고있는데 다 버리고 최소한의 의미만 가지고있는 함수적 종속성으로만 적용하겠다 라는게 카노니컬 커버

함수적 종속성 추론 규칙으로 확장된 클로저에는 자명한 종속성중복된 종속성을 포함

자명한 중속성이란?
A → A (당연한것)

중복된 종속성이란?
X → AB, X → B (의미가 여러번 존재)

불필요한 함수적 종속성을 제거한 표준형으로 변환 후 정규화를 수행한다.

표준형 조건
- F의 모든 함수적 종속성의 오른편 속성은 반드시 1개
- F에서 X → A를 X의 진부분집합 Y에 대하여 Y → A로 교체했을 때, 그 집합이 F와 동등한 집합이 불가능
- F에서 어떤 함수적 종속성을 제거했을 때, 그 집합이 F와 동등한 집합이 불가능

5-3) 카노니컬 커버의 도출

릴레이션 R의 스키가 (X,Y,Z)라고 가정하자
F+(클로저) = { X → YZ, Y → Z, X → Y, XY → Z}
                           ▼▼▼
        F+' = {X → YZ, Y → Z, XY → Z}
1. X가 YZ를 종속하고 X가 Y를 종속한다 라면 X가 Y를 종속한다는 것을 제거해도 된다.
                           ▼▼▼
                F+'' = {X → YZ, Y → Z}
2. XY가 Z를 종속한다라는 이야기는 X가 Y를 종속하고 X를 종속한다는 의미가 X → YZ에 포함되어 있다. 그러므로 XY → Z 에서 XY를 XX로 바꿀 수 있으므로 XX → Z 는 X → Z와 동일하다. 그러므로 XY → Z는 제거가 가능하다.

 

기말고사에서는 교재에 있는 알고리즘은 나오지 않음. 카노니컬 커버의 도출하는 과정만 나온다.

 

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/2100sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

경상북도 예천 순대국밥 전문점 단골식당 본점 후기

주말에 여자친구 결혼식 투어를 마치고 여친님께서 뜬금없이

'예천 순대 먹어볼래?' 라고 던지셨습니다.

잡식성인 저는 덥석 물었죠

순대? 응!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

처음엔 예천에 순대?

왠 순대? 의문반의심반으로 여친님께서 네x버 검색 후 찾은 식당으로 안내합니다.

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/2300sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

 

단골식당은 어느시장의 골목에 자리잡고있는데요

시장의 메인스트릿에서 좌회전을 딱!하자마자 딱 봐도 사람이 많아보였어요.

주차를 하려는데 여친님께서 "내가 먼저 내릴까!?!?!?"

역시 현명하신 여친님!!

"응!!!!!!! 내려내려!"

samsung | SM-G935S | Normal program | Center-weighted average | 1/2400sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

 

사람이 정말 많아요

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/2800sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

주차는 길가에 그냥 주차하면 됩니다.

남의 가게 앞에만 주차하지않으면 되는것 같았어요 ㅋㅋㅋ (시골인심이란...)

가까운 거리에 저도 주차를 하고 여친님께 가니

samsung | SM-G935S | Normal program | Center-weighted average | 1/7300sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

이런 번호표를 나눠줬다고 해요

대기시간은 5분이라고 했는데

한 10분 조금 넘게 기다렸던것같아요

아무래도 순대국하고 순대국밥은 미리 만들어놓고 데워서 내놓기만하면되니

회전률이 빠른가보다 하고있었어요

samsung | SM-G935S | Normal program | Center-weighted average | 1/120sec | F/1.7 | 0.00 EV | 4.2mm | ISO-250

10분 정도 대기 후 드디어 입장!

자리는 한 40석정도 있는것같았어요

방이 3개정도 있고 홀이 있어요

전부 좌식이고 의자는 없어요

메뉴판에 메뉴는 여러가지가 있는데

우리는 많이먹지 못하기때문에

모듬순대 하나 따로국밥 하나 시켰어요 ㅎㅎ

samsung | SM-G935S | Normal program | Center-weighted average | 1/40sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

주문을 빠르게 하고 여기저기 보는데

3대천왕!! 백종원 싸인이!!!

우와! 우와!!!

3대천왕에 나온 집인가봐요

samsung | SM-G935S | Normal program | Center-weighted average | 1/120sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

samsung | SM-G935S | Normal program | Center-weighted average | 1/60sec | F/1.7 | 0.00 EV | 4.2mm | ISO-200

 

유명인 싸인이 정말 많아요...

엄청 유명한집인가봐요

 

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/60sec | F/1.7 | 0.00 EV | 4.2mm | ISO-200

추억방 사랑방 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

유치...ㅋㅋㅋㅋ

주문하고 바로 밑반찬과 따로국밥용 밥을 하나 셋팅해 주셨어요

samsung | SM-G935S | Normal program | Center-weighted average | 1/60sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

너무 배가고파서 밥이랑 김치랑 냠냠

얼마 지나지않아 바로 모듬순대가 나와요

samsung | SM-G935S | Normal program | Center-weighted average | 1/40sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

전통막창순대와 김치막창순대가 반반있는 모둠순대에요

비주얼은 음 잘 모르겠어요 그냥 순대같아보여요

samsung | SM-G935S | Normal program | Center-weighted average | 1/30sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

김치막창순대

samsung | SM-G935S | Normal program | Center-weighted average | 1/30sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

근데... 이거 진짜 존나맛있어요...

엄청 쫀득하고 부드럽고 와 미쳤어요 순대가 이런맛이 난다는게 정말 신기해요

그냥 미쳐버렸어요...

한입먹을때마다 와 맛있다 와 맛있다 와 맛있다

진짜 미쳐버렸어요 맛이 미쳤어요

samsung | SM-G935S | Normal program | Center-weighted average | 1/25sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

곧이어 나온 순대국

색은 진한 사골국물 색 같아요

일반 프랜차이즈 순대국밥집 가면 색깔이 너무 하얗다못해 우윳빛이 나는 것들이 있는데요

여긴 달라요...

진짜 아무것도 첨가하지않은 순수한맛이에요

samsung | SM-G935S | Normal program | Center-weighted average | 1/30sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

제가원래 순대국밥을 원래좋아하고 다대기와 새우젓을 기본적으로 넣어먹거든요?

간이 필요없어... 이건 간을 하면 죄짓는거야...

미쳤어

미쳐버렸어아주그냥

samsung | SM-G935S | Normal program | Center-weighted average | 1/30sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

하 사진보니깐 또 먹고싶다 ㅠㅠ

재방문 의사 100000000000000000000000000000000000000%....

인생 순대국밥집이었다...

samsung | SM-G935S | Normal program | Center-weighted average | 1/60sec | F/1.7 | 0.00 EV | 4.2mm | ISO-320

따로국밥을 개인당 시킬껄 그랬어요...

둘이서 남김없이 설거지 한듯이 돼지마냥 뚠뚠하게 먹고왔습니다.

1인 1국밥 시키세요

왜냐구요?

2인 1국밥 시키면 다먹고 후회합니다.

.

.

.

식당 맞은편에는 단골휴게소라는 카페가있어요

카페에 붙은 아이스크림이 맛있어보여서 개당 3천원짜리

둘이서 사먹었어요

디저트까지 완벽했습니다...

맛도 진짜 맛있어요

여친님 디저트까지먹고 기분좋아서 차타기전에 춤 한사바리 땡기고 탐.ㅎㅎㅎ

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/2100sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

samsung | SM-G935S | Normal program | Center-weighted average | 1/60sec | F/1.7 | 0.00 EV | 4.2mm | ISO-100

내돈내고 내가 결제해서 먹었다!!!!!!!!!!!!!!!!!!!!!!!!

모듬순대 9천원 따로국밥 6천원

합이 1.5만원

미쳤다 이집은 가서 꼭 먹길바람

인생 순대집

samsung | SM-G935S | Normal program | Center-weighted average | 1/10000sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

samsung | SM-G935S | Normal program | Center-weighted average | 1/10000sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

samsung | SM-G935S | Normal program | Center-weighted average | 1/60sec | F/1.7 | 0.00 EV | 4.2mm | ISO-200

예약도 되는것같았어요

계산하는데 예약전화도 받으시더라구요

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/1000sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

이 장소를 Daum지도에서 확인해보세요.
경북 예천군 용궁면 읍부리 299-2 | 용궁단골식당 본점
도움말 Daum 지도
준돌 Jundol / 2018.04.24 00:12 / 오키나와 여행기 18.03.31 ~ 18.04.02

samsung | SM-G935S | Normal program | Center-weighted average | 1/240sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

어머니께서 회사에 근속하신지 5년이 되셔서 휴가를 받으셨습니다.

저희 어머니 아버지께서는 이번 여행이 첫 해외여행이세요.

원래는 패키지로 두분만 보내드리려했는데

마음이 영 놓이지도않고 왠만한 패키지여행 2인 값이면 3인 자유여행 값이랑 동일하더라구요...

그래서 제가 따라가기로 했습니다!

첫 해외여행인만큼 해외여행에 대한 인식을 나쁘지않게끔 만들어드리고자

최대한 휴식을 취할 수 있는 휴양지로! 편안하게끔 여행하고자 오키나와를 선택했습니다.

가족여행을 가고싶어하셔서 급히 2주전에 휴가를 내고 오키나와 비행기 티켓을 끊었어요!

마침 삼성카드에서 진에어와 프로모션도 진행하고있어서

3명 왕복 615,000원에 티켓팅 했습니다! 겟겟!

1인당 왕복 205,000원입니다!

완전 쌈....

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/3384sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

 

공항이 마냥 신기하신 아버지 ㅎㅎ 그런 아버지가 신기하신 어머니

아버지는 저 큰 비행기가 항상 어떻게 하늘을 날아다니시는건지 이해할 수 없다고 하십니다.

 

3명일 경우에는 진에어 오키나와 여객기의 경우 3,4,3 의 비행기 좌석 배열을 가지고 있기 때문에

3명이 탑승할 경우 좌우측의 창가자리에 배정해 줄 확률이 높아요

창가자리는 호기심이 많으신 아버지께서 앉으셨어요 ㅎㅎ

그리고 진에어 오키나와 여객기는 가는동안 간단한 기내식을 준비해줘요!

samsung | SM-G935S | Normal program | Center-weighted average | 1/60sec | F/1.7 | 0.00 EV | 4.2mm | ISO-500

 

진에어 브랜드 색상은 참 좋아요 부드러워 보이잖아요?

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/24sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

 

기내식 구성은

물 한 잔
물티슈
바나나
요플레
삼각김밥

이에요 간단하지만 든든하게 채울 수 있어요

samsung | SM-G935S | Normal program | Center-weighted average | 1/24sec | F/1.7 | 0.00 EV | 4.2mm | ISO-200

samsung | SM-G935S | Normal program | Center-weighted average | 1/24sec | F/1.7 | 0.00 EV | 4.2mm | ISO-200

 

삼각김밥은 음 그냥 그래요 ㅋㅋㅋ 그래도 주는거에 감사해요

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/30sec | F/1.7 | 0.00 EV | 4.2mm | ISO-160

 

음 요플레 마싯땅 ㅎㅎ

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/1408sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

 

비행기는 슈우우우웅 2시간동안 날아서 나하공항에 도착합니다.

저는 오키나와달인 이라는 사이트에서 렌트카를 대여했어요!

생각보다 렌트카가 굉장히 저렴했어요

3박4일에 13,500엔!!

 

나하공항에서 나오면 여러 렌트카 회사에서 직원들이 나와서 팻말을 들고있어요.

자신이 예약한 렌트카 회사가 써져있는 팻말을 들고있는 직원한테 가셔서

예약자 이름 확인 후 아래 사진과 같은 받침이 있는 종이를 주는데요!

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/12448sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

 

위 사진에 보시면 맨 앞장에 붙어있는 31번이 대기번호에요

대리점에 도착하면 저 대기번호 순으로 렌트카 대여 처리를 해줘요

기다리고 있으면 알아서 영어로 불러줍니다.

공항에서 직원이 저 종이를 건네주면서 나하공항에서 나가서

왼쪽으로 돈다음 쭈우욱 1번 까지 가라고 해줘요 가면!

막 여러 렌트카 회사에서 차들이 오는데요

타임즈 렌트카의 경우 셔틀 버스가 여러대가있어요!

짐칸이 있는 셔틀버스의 경우에는 기사님이 짐칸에 실어주시는데

짐칸이 없는 버스의 경우 들고타라고 하시더라구요 ㅎㅎ

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/2144sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

 

1번 탑승구에 타임즈 렌트카 셔틀버스가 없어도 당황하지마세요!

곧 옵니다! 다른 회사이름이 적혀있는 버스 타지마시구요

기다리시면 금방와요! 5~10분 간격 이내로 도착하는것같았어요

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/3720sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

 

셔틀버스로 이동하는 동안 받은 종이에 이것저것 작성하고

일본에서 운전하는 요령? 같은 안내 숙지 서명란이 있어요 그것도 전부 작성해주세요

타임즈 렌트카 나하공항점에 도착했는데요!

나하공항점은 허허벌판같은곳에 있어요 컨테이너박스로 ㅋㅋㅋ

임시대리점 같은 느낌이더라구요 공사한대나 뭐래나

그래서 대리점에 들어가시면 짐은 기사님이 알아서 잘 정렬해주십니다

밑에 사진 보시면 우리가 은행에서 보던 익숙한 대기번호 호출판 있죠?

29번이라고 되어있는데 제 번호는 31번!

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/122sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

 

보통 소요시간은 한팀당 10분 정도 소요되는것 같았어요

직원분이 영어? 일어? 라고 안내를 선택해달라고하는것같았는데

영어로 하셔도 괜찮을것같아요 소통에는 문제가 없었어요!

 

기다리는동안 사진도 찍고 여기저기 구경합니다.

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/144sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

samsung | SM-G935S | Normal program | Center-weighted average | 1/2512sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

samsung | SM-G935S | Normal program | Center-weighted average | 1/3680sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

samsung | SM-G935S | Normal program | Center-weighted average | 1/4816sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

samsung | SM-G935S | Normal program | Center-weighted average | 1/7696sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

samsung | SM-G935S | Normal program | Center-weighted average | 1/120sec | F/1.7 | 0.00 EV | 4.2mm | ISO-80

samsung | SM-G935S | Normal program | Center-weighted average | 1/120sec | F/1.7 | 0.00 EV | 4.2mm | ISO-80

 

드디어 제 번호가 불리고!

31번!

직원분이 친절하게 응대해주십니다.

잔금 결제하고

저희의 경우 주 운전자를 저로 등록하고 세컨 드라이버로 아버지를 등록했습니다.

추가요금같은건 없고 주 운전자와 동일하게 국제운전면허증하고 여권만 있으면 됩니당

따로 세컨드라이버를 등록할꺼냐고 물어보지않기때문에 미리 말씀해주시는게 좋아요

 

 

samsung | SM-G935S | Normal program | Center-weighted average | 1/60sec | F/1.7 | 0.00 EV | 4.2mm | ISO-80

samsung | SM-G935S | Normal program | Center-weighted average | 1/120sec | F/1.7 | 0.00 EV | 4.2mm | ISO-100

samsung | SM-G935S | Normal program | Center-weighted average | 1/1188sec | F/1.7 | 0.00 EV | 4.2mm | ISO-50

그리고 저희가 받은 차량은 마쯔다의 악셀라 스포츠입니다!

다음 포스팅에서는 마쯔다 악셀라의 상세 사진을 포스팅해보기로 할게요!

오키나와 입국 어렵지 않아요 ㅎㅎ

준돌 Jundol / 2018.04.23 16:24 / Android

이번 프로젝트는 대한민국의 남바완 대기업의 본사 사옥내에서 개발 해야하는 프로젝트가 되시겠습니다.


본사 사옥에 개발환경을 셋팅하는데 보안때문에 안되는게 뭐 이리 많은지 ㅡㅡ


기본적으로 사내망과 외부망을 분리해서 사용하거나 따로 허용해주지않는이상 외부 인터넷망을 사용하지 못하는 곳에서는 프록시 서버를 거쳐서 외부망에 접속하도록 되어있습니다.


안드로이드스튜디오에서는 빌드시 외부 라이브러리를 엄청 가져다가 빌드빌드빋딩 하기때문에 설정해줘야하는게 많은데요.


이 삽질만 안했어도 하루는 단축할 수 있었겠네요.


1. 먼저 프록시 설정 파일을 Get 하도록 해봅시다.

1-1. 시작 > 인터넷 옵션 > 연결 > LAN설정 > 자동구성스크립트 사용에 체크되어있고 경로가 하나 있을겁니다.

http://proxy.xxx.com:8080/proxy.pac

xxx 는 기업의 영문이름이 되겠죠? 아마도? (제경우에 그랬으니까요)

이걸 에디터를 이용하여 열어보시면 맨 아래쪽에 Default Return 해가지고 ip주소가 하나 있을겁니다. 이부분 기억해두십쇼. 이 ip 를 이하에서는 예시로 555.555.555.555:8080 이라고 하겠습니다.

2. Android Studio Proxy Setting

2-1. Android Studio > File > Settings > Appearance & Behavior > HTTP Proxy > Auto Detect proxy settings 라디오버튼 체크 합니다.

2-2. Automatic proxy configuration URL 이 부분에 1-1 의 http://proxy.xxx.com:8080/proxy.pac 주소를 넣어줍니다.

2-3. OK 버튼 클릭

2-4. gradle.properties 에 아래내용을 추가합니다.

org.gradle.daemon=true
systemProp.https.proxyHost=555.555.555.555
systemProp.https.proxyPort=8080
systemProp.http.proxyHost=555.555.555.555
systemProp.http.proxyPort=8080
systemProp.https.nonProxyHosts=*.xxx.com|localhost

여기서 555.555.555.555 를 proxy.pac 파일의 Default Return 부분의 ip 주소와 포트를 입력합니다.

2-5. build.gradle

repositories {
jcenter{url "http://jcenter.bintray.com/"}
}

레파지토리 url 을 강제로 지정합니다.


2-6. 추가로 java 인증서 관련하여 실패했다고 나오면 C:\Program Files\Java\jre1.8.0_161\lib\security 이 경로에 dl.google.cer 과 bintary.cer 파일을 신뢰시켜준다.

https://stackoverflow.com/questions/22887829/peer-not-authenticated-while-importing-gradle-project-in-eclipse

위 url 을 참고한다.


이렇게 한 다음 다시 빌드하면 정상적으로 빌드에 필요한 파일들을 다운로드 받는 것을 볼 수 있다.


언느 프로젝트던지 환경설정이 제일 뭣같다.

'Android' 카테고리의 다른 글

Android Studio 프록시 환경에서 개발하기  (0) 2018.04.23
© 2015 Jundol in 음 아마 비둘기보단 똑똑할꺼야
Designed by DH / Powered by Tistory
147 / 14 / 114,041