Algorithm Flashcards Preview

PE > Algorithm > Flashcards

Flashcards in Algorithm Deck (36):
1

B트리와 B+트리에 관련하여 다음을 설명하시오.
가. B트리, B+트리 삽입 알고리즘
나. B트리, B+트리 삭제 알고리즘
다. 26, 57, 5, 33, 72, 45를 순서대로 삽입하고, 72, 33, 45를 순서대로 삭제하는 B트리, B+트리를 그리시오. (단, 차수는 3)

1. 균형을 유지하는 m-way 탐색 트리, B트리와 B+트리의 개요

  • B 트리 : Root 노드는 최소 2개 이상 자식 노드와 최소 1개 이상 key값을 가지며, Root 노드와 Leaf 노드를 제외한 모든 노드는 최소 m/2개, 최대 m개 서브 트리로 구성된 자료구조
  • B+ 트리 : 순차 탐색 성능 향상을 위해 인덱스 집합(Index Set)과 순차 집합(Sequence Set)으로 구성된 트리, Leaf노드는 Linked List를 이용하여 순차적 접근이 용이하게 구성된 자료구조

2. B크리, B+트리 삽입 알고리즘

  가. B트리 삽입 알고리즘

    1) 여유공간 있을 경우

  • 삽입할 Key 값은 항상 Leaf 노드에 삽입

    2) 여유공간 없을 경우

  • 해당 Leaf 노드에 새로운 key 값을 삽입 했을 경우 가정
  • 중간 key 값을 중심으로 2개 노드로 분할(Split)
  • 중간 key 값은 분할된 노드에 대한 부모 노드에 삽입
  • 이 때, 부모 노드에서 Overflow 발생할 경우 분할 작업 반복
  • Leaf 노드는 key를 최대 m-1 개 까지 가질 수 있고, m개 이상인 경우 Overflow 발생에 따른 2개 노드로 분할

  나. B+ 트리 삽입 알고리즘

    1) 여유공간 있을 경우

  • B 트리와 거의 동일
  • 단순히 순서에 맞게 삽입
  • 신규 노드는 Linked List로 구성된 Leaf 노드에도 삽입

    2) 여유공간 없을 경우

  • 노드 분할이 발생하면 중간 key 값이 부모 노드로 이동, 새로 분열된 노드에도 포함함
  • 신규 노드는 Linked List로 구성된 Leaf 노드에도 삽입

3. B트리, B+트리 삭제 알고리즘

  가. B트리 삭제 알고리즘

    1) 삭제 key 값이 Leaf 노드 인경우

  • 삭제는 항상 Leaf 노드에서 이루어짐
  • 최소 key 개수가 m/2-1 보다 작은 경우 Underflow 발생
  • Underflow 발생 시, 재분배 또는 합병 수행

    2) 삭제 key 값이 Leaf 노드가 아닌 경우

  • 후행 key 값과 자리를 바꾸어 Leaf 노드로 이동시킨 후 삭제
  • 최소 key 개수가 m/2-1 보다 작은 경우 Underflow 발생
  • Underflow 발생 시, 재분배 또는 합병 수행
  • 재분배(Redistribution) : 트리 구조가 유지되는 Underflow 대응 기법
    • 최소 key 개수 보다 많은 key를 가진 형제 노드에서 차출
    • 부모 노드에 있던 key 값은 Underflow 발생 노드로 이동
    • 차출된 형제 노드 key 값은 부모 노드로 이동
  • 합병(Merge) : 트리 구조가 변경되는 Underflow 대응 기법
    • 재분배 불가능한 경우 적용
    • 형제 노드를 결합하는 방법으로, 합병 결과 빈 노드는 제거

  나. B+ 트리 삭제 알고리즘

    1) 재배치와 합병 수행하지 않는 경우

  • 삭제는 항상 Leaf 노드에서 이루어짐
  • Index 부분은 다른 Key 값 검색 시 사용될 수 있기 때문에 Leaf 노드 값이 삭제 되어도 삭제하지 않음

    2) 재배치 할 경우

  • Index 부분 노드 key 값은 변하지만 Tree 구조는 변하지 않음

    3) 합병 할 경우

  • Index 부분에서도 key 값을 삭제

4. B 트리, B+ 트리 삽입/삭제 과정

 

 

A image thumb
2

내부정렬

▣ 내부정렬

- 교환 : 버블 정렬, 퀵 정렬

- 삽입 : 삽입 정렬, 셀 정렬

- 병합 : 2-way 병합, n-way 병합

- 분배 : 기수 정렬

- 선택 : 선택 정렬, 히프 정렬

3

선택 정렬

▣ 선택 정렬

- 정렬되지 않은 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식

 

#include

#include

 

void printArray(int value[], int count);

 

void selectionSort(int value[], int count)

{

    int i = 0, j = 0;

    int min = 0, temp = 0;

    

    // 11 Line : 전체 자료 개수보다 1 적은 횟수(count - 1) 만큼 루프를 돈다.

    // 정렬의 마지막에 남은 자료는 최대 자료이기 때문에 추가적인 정렬이 필요 없다.

    for(i = 0; i < count-1; i++) {

        //12 Line : (정렬되지 않은 자료 중) 최솟값이 위치(min)를 초기화 시킨다.

        min = i;

        

        //13~17 Line : 정렬되지 않은 자료들 (j의 값이 i+1 부터 시작된다)을 대상으로 가장 작은 키 값을 찾는다.

        for(j = i + 1; j < count; j++) {

            if(value[j] < value[min]) {

                min = j;

            }

        }

        

        //18~20 Line : 정렬되지 않은 자료들 중 가장 작은 키 값을 가지는 자료(위치 min)와 정렬 대상이 되는 자료(위치 i)의 위치를 교환한다.

        temp = value[i];

        value[i] = value[min];

        value[min] = temp;

        

        printf("Step-%d,", i+1);

        printArray(value, count);

    }

}

4

버블 정렬

▣ 정의

- 정렬되지 않은 전체 자료들을 대상으로 인접한 두 개 자료의 키 값을 비교하여 위치를 교환하는 정렬 방식

▣ 원리

1) 인접한 두 개의 값을 비교

2) 앞의 값이 뒤의 값보다 크면 교환

3) 비교할 대상 없을 때까지 반복

 

▣ 특징

- 효율성 : 최선, 평균, 최악 O(n^2)

- n^2 으로 느린 알고리즘

 

▣ 소스코드

void printArray(int value[], int count);

 

void bubbleSort(int value[], int count)

{

    int i = 0, j = 0;

    int temp = 0;

    

    //Line 12 : 전체 자료 개수보다 1적은 횟수(count-1) 만큼 루프를 돈다.

    //정렬의 마지막에 남은 자료는 최대 자료이기 때문에 추가 정렬이 필요 없다.

    for(i = count - 1; i >=0; i--) {

        if(value[j-1] > value[j]) {

            //Line 13 ~ 19 : 정렬되지 않은 자료들을 대상으로 이웃한 두 자료 사이의 위치를 교환한다.

            temp = value[j-1];

            value[j-1] = value[j];

            value[j] = temp;

        }

    }

    printf("Step-%d,", count - i);

    printArray(value, count);

}

5

퀵 정렬

▣ 퀵 정렬

- 중심 값(Pivot)을 기준으로 두 자료의 키 값을 비교하여 위치를 교환하는 정렬 방식

- Left : 왼쪽 끝에서 오른쪽으로 움직이면서 피봇보다 큰 자료 찾음

- Right : 오른쪽 끝에서 왼쪽으로 움직이며 피봇보다 작은 자료 찾음

- Left는 Right까지 이동할 수 없고, 반대로 Right는 Left보다 더 왼쪽으로 이동할 수 없다

6

삽입 정렬

▣ 삽입 정렬

- 기존에 정렬된 부분 집합에 정렬할 자료의 위치를 찾아 삽입하는 정렬 방식

7

병합 정렬

▣ 정의

- 같은 개수의 원소를 가지는 부분 집합으로 기존 자료를 분할(Divide)하고 분할된 각 부분 집합을 병합(Merge)하면서 정렬 작업을 완성(Conquer)하는 분할 정복(Divide and Conquer) 기법에 의한 정렬 방식

- 2개의 부분 집합의 원소들을 하나의 집합으로 합치는 가운데 정렬이 이루어지는 것이며, 이는 2개의 부분 집합의 원소를 차례로 비교하면서 이루어진다.

 

▣ 정렬 원리

1) 분할 : 정렬할 데이터 집합을 반으로 나누기

2) 반복 : 나누어진 하위 데이터 집합의 크기가 2 이상이면, 하위 데이터 집합에 대해 "절차 1(분할)을 반복

3) 정렬 및 병합 : 원래 같은 집합의 나뉘어진 하위 데이터 집합 들을 병합 (병합 할 때 데이터 집합의 원소는 순서에 맞추어 정렬)

4) 반복 : 데이터 집합이 다시 하나가 될 때까지 "절차 3(정렬 및 병합)" 반복

 

▣ 정렬 및 병합 단계 상세 설명

1) 병합을 위한 빈 배열 생성

2) 병합하려는 2개의 부분집합의 첫 원소 비교

3) 키 값이 작은 원소 선택하여 정렬 위해 생성한 배열에 삽입

4) 2~3 과정 반복하여 정렬 완료

 

▣ 소스코드

void mergeSort(int value[], int buffer[], int start, int end) {

    int middle = 0;

    

    //원소의 개수가 1개가 될 때까지 순환적으로 병합 정렬을 실행한다.

    if(start < end) {

        

        //2개의 부분 집합으로 나누기 위해 중간 위치 middle을 구한다.

        middle = (start+end) / 2;

        

        //왼쪽 부분 집합(start, middle)과 오른쪽 부분집합(middle+1, end)에 대해

        //순환적으로 병합 정렬을 실행한다.

        mergeSort(value, buffer, start, middle);

        mergeSort(value, buffer, middle+1, end);

        

        //병합 정렬이 완료된 두 개의 부분 집합에 대해 병합을 실시한다.

        //단, 이 때 병합을 위해 배열의 개수만큼의 추가적인 메모리 공간이 필요하며,

        //이를 위해 버퍼(buffer)를 전달한다.

        //이 버퍼는 외부에서 전달 받은 것으로, 함수 mergeSort()를 사용하기 위해서는

        //이러한 버퍼를 입력 파라미터로 전달해야 한다.

        mergeSortInternal(value, buffer, start, middle, end);

    }

}

 

void mergeSortInternal(int value[], int buffer[], int start, int middle, int end) {

 

    //변수들을 초기화 시킨다

    int i = 0, j = 0, k = 0, t = 0;

    

    //변수 i : 첫 번째 부분 집합의 원소를 가리키는 인덱스

    //변수 j : 두 번째 부분 힙합의 원소를 가리키는 인덱스

    //변수 k : 결과 버퍼의 현재 위치를 가리키는 인덱스

    i = start;

    j = middle + 1;

    k = start;

    

    //두 개 부분 집합(start, middle) 및 (middle+1, end)을 대상으로 루프를 돌면서

    //각 부분 집합 원소의 키 값을 비교한다.

    //만약 키 값이 작다면 해당 원소의 키 값을 복사하고 다음 원소를 가리키도록 이동시킨다.

    while(i <= middle && j <= end) {

        if(value[i] <= value[j]) {

            buffer[k] = value[i];

            i++;

        } else {

            buffer[k] = value[j];

            j++;

        }

        k++;

    }

    

    //위 루프를 빠져 나온 것은 두 개의 부분 집합 중 한 개 부분 집합이 모두 복사되었다는 의미이므로,

    //원소가 남은 다른 부분 집합의 자료들을 복사해 주어야 한다.

    //따라서, 아래 조건에서 어느 부분 집합의 원소가 남았는지 판단한 다음,

    //해당 부분 집합의 남은 원소들을 결과 버퍼에 복사한다.

    if(i > middle) {

        for(t = j; t <= end; t++, k++) {

            buffer[k] = value[t];

        }

    } else {

        for(t = i; t <= middle; t++, k++) {

            buffer[k] = value[t];

        }

    }

    

    //정렬 결과가 저장된 버퍼의 내용을 최종적으로 복사한다.

    for(t = start; t <= end; t++) {

        value[t] = buffer[t];

    }

    

    printf ("start-%d,middle-%d,", start, middle, end);

    

    for(t = start; t <= end; t++) {

        printf("%d ", value[t]);

    }

    

    printf("\n");

    

}

8

히프 정렬

▣ 정의

- 루트 노드 삭제 연산으로 정렬된 데이터 집합을 만들어 내는 정렬 기법

▣ 유형

- Min Heap

- Max Heap

▣ 특징

- 히프는 완전 이진 트리이면서 동시에 최대 트리 혹은 최소 트리를 말하는 것으로, 최대 히프는 루트 노드의 키가 트리 전체 중 항상 최댓값을 지니고, 최소 히프의 루트 노드는 트리 전체 중 항상 최솟값을 가지는 특성이 있다.

- 오름차순 정렬 : 최소 히프에 정렬하고 싶은 자료를 모두 삽입한 다음, 최소 히프에서 자료의 개수 만큼 루트 노드를 삭제하면 키 값이 가장 작은 자료에서 큰 순서대로 자료가 반환된다.

- 내름차순 정렬 : 최대 히프에 자료를 추가한 다음, 루트 노드를 반환하면 키 값이 가장 큰 자료에서 작은 순서대로 자료를 반환하게 된다.

 

▣ 수행 단계

1) 삽입 : 정렬하고자 하는 Data를 Heap에 삽입

2) 정렬 : Heap 정렬 수행

3) 삭제 : Root 노드의 값을 추출

4) 재정렬 : Heap 재정렬 수행

5) 반복 : 추출할 Data 없을 때까지 1~4 반복

9

분할 정복 알고리즘

▣ 정의

- 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘

▣ 원리

1) 문제를 더 작은 문제(부문제)로 분할

2) 분할된 문제 해결

3) 해결된 문제 통합

▣ 분할과 정복의 원리 소스코드

function F(x);

if F(x)의 문제가 간단 then;

return F(x)을 직접 계산한 값;

else

x 를 y1, y2로 분할

F(y1)과 F(y2)를 호출

return F(y1), F(y2)로 부터 F(x)를 구한 값

 

▣ 종류

1) 병합 정렬 (Merge Sort)

2) 퀵 정렬 (Quick Sort)

3) 선택 문제 (Selection)

4) 최근접 점의 쌍 찾기 (Closet Pair)

10

그래프

▣ 그래프의 종류

1) 간선의 방향성

- 무방향 그래프 : 간선에 방향이 없는 그래프

- 방향 그래프 : 간선에 방향이 있는 그래프

2) 간선의 가중치

- 가중 그래프 : 간선에 가중치가 할당된 그래프

3) 구조적 특징

- 완전 그래프 : 연결 가능한 최대 간선 수를 가진 그래프

- 부분 그래프 : 원래의 그래프에서 일부의 노드나 간선을 제외하여 만든 그래프

- 다중 그래프 : 중복된 간선을 포함하는 그래프

 

▣ 그래프의 구현

1) 인접 행렬(Adjacency Matrix)

2) 인접 리스트(Adjcency List)

 

▣ 그래프 탐색

1) 깊이- 우선 탐색 : 아직 탐색 되지 않은 노드 먼저 탐색 (스택)

2) 넓이-우선 탐색 : 이전 노드에 연결된 모든 노드 탐색 (큐)

 

▣ 깊이-우선 탐색 알고리즘

traversal_DFS (node v) {

스택 S;

 

v

push(S, v);

while(not is_empty(S)) {

u

for(all w ∈ (u의 인접 노드들)) {

if(w != 방문) {

w

push(S, w);

}

}

}

}

▣ 넓이-우선 탐색 알고리즘

traversal_BFS (node v) {

    큐 Q;

    

    v

    enqueue(Q, v);

    while(not is_empty(Q)) {

        u

        for(all w ∈ (u의 인접 노드들)) {

            if(w != 방문) {

                w

                enqueue(Q, w);

            }

        }

    }

}

 

11

최소 비용 신장 트리

▣ 신장 트리 정의

- 신장(Spanning) : 모든 노드를 포함한다는 의미

- 신장트리(Spanning Tree) : 기존 그래프가 가진 모든 노드를 순환 없이 서로 연결시킨 트리

▣ 최소 비용 신장 트리

- 정의 : 가중 그래프의 신장 트리 중에서 가중치의 합이 최소인 신장 트리

▣ 최소 비용 신장 트리 알고리즘 종류

- 프림 (Prim)

- 크루스칼 (kruskal)

- 솔린 (sollin)

12

크루스칼(Kruskal)

▣ 정의

- 그래프의 모든 간선을 비용 순으로 정렬한 다음, 낮은 비용을 가지는 간선을 차례대로 선택하여 신장트리

▣ 알고리즘

1) 초기화

- 그래프 G의 최소 비용 신장 트리 H를 다음과 같이 초기화한다.

H= (V(G), E(H)))

단, E(H) = ∅

- 그래프 G의 모든 간선을 가중치 값에 따라 오름차순으로 정렬한다.

2) 루프

Step-1) 정렬된 간선들 중에서 1) 가중치가 작으면서 2) 순환을 발생시키지 않는 간선 e를 추출.

Sep-2) 그래프 G의 모든 노드가 V(T)에 연결 될때까지 Step-1을 반복

13

프림(Prim)

▣ 정의

- 트리를 확장시켜 최소 비용 신장 트리를 만드는 방법

▣ 특징

- 임의의 시작 노드 1개만 추가하여 알고리즘 시작

- 현재 신장 트리와 연결된(부속된) 간선 중에서 가장 적은 비용을 가지는 간선을 선택(선택된 노드는 제외)

▣ 알고리즘

1) 초기화

- 그래프 G에서 임의의 시작 노드 r을 선택하여, 신장 트리 T를 초기화

  V(T) = { r }

  E(T) = ∅ (아직 선택된 간선은 없다)

2) 루프

Step-1) V(T)와 부속된(연결된) 모든 간선들 중에서 (1) 가장 가중치가 작으면서 (2) 순환을 발생시키지 않는 간선을 선택하여 신장 트리 T를 확장

  E(T) = E(T) ∪ { e }, e: 추가되는 최소 가중치 간선

  V(T) = V(T) ∪ { w }, w: e와 부속된 노드로, V(T)에 포함되지 않던 노드

Step-2) 그래프 G의 모든 노드가 V(T)에 포함될 때까지 Step-1을 반복

14

솔린(Sollin)

▣ 정의

- 각 단계에서 여러 개의 간선을 선택하여, 최소비용 신장트리를 구축하는 알고리즘

▣ 알고리즘

1) 그래프의 각 정점 하나만을 포함하는 n개의 트리로 구성된 신장 포레스트(Forest)에서부터 시작

2) 매번 포레스트에 있는 각 트리마다 하나의 간선을 선택

3) 선정된 간선들은 각각 두개의 트리를 하나로 결합시켜 신장트리로 확장

4) 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선

5) 선택된 간선은 구축중인 신장트리에 추가

6) n - 1 개의 간선으로 된 하나의 트리가 만들어지거나, 더 이상 선정할 간선이 없을 때 종료

▣ 슈도 코드

void sollin() {

  /*집합 E 의 초기 상태는 주어진 그래프의 간선 집합*/

  /*집합 F 의 초기 상태는 그래프의 모든 정점들로 구성된 간선이 없는 숲*/

  T = ;

  while (T 는 완전한 하나의 트리가 아니고 E 는 공집합이 아님) {

    for (F 내의 각각의 트리 t 에 대하여) {

      T 와 또 다른 트리를 연결하는 E 의 간선 중 최소비용 간선(u, v)를 선택;

      T = T (u, v) ;

      E 에서 간선 (u, v)를 제거;

    }

    T 에 새로 추가된 간선을 포함하여 F 를 수정;

  }

}

15

최단경로 알고리즘

▣ 정의

- 방향 그래프 G(V,E)에서 n개의 정점이 존재하고 연결선에 가중치가 주어졌을 때 시작 정점 Vi에서 종착 Vj에 도달하는 여러 경로 중에서 가장 짧은 경로. 즉, 가중치의 합이 최소인 경로를 찾는 알고리즘

▣ 유형

- Dijkstra 알고리즘 : 최소비용 경로 설정

- A* 알고리즘 : 휴리스틱 순서 탐색

- Bellman-Ford 알고리즘 : 음의 가중치 허용한 경로

- Floyd-Warshall 알고리즘 : 동적계획 기반 고차원 기법

16

 다익스트라 (Dijkstra)

▣ 개념

- 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘

▣ 탐색원리

1) 시작정점과 최초 연결한 근접 정점을 집합 S로 규정

2) 집합 S에 포함되지 않은 정점 중에서 시작 정점으로부터 가장 가까운 정점을 탐색(집합 S에 이웃한 정점 중 하나)

3) 결정된 정점을 집합 S로 포함

4) 새로운 정점이 없어질 때까지 반복

5) 모든 정점이 집합 S에 포함되었다면 종료

▣ 조건

- 시작점이 있으면 모든 정점의 최단거리 구함

- 가중치가 주어진 유향 그래프

- 음의 가중치가 있는 경우 사용 불가

▣ 알고리즘

Step-1) 초기화

1) 집합 S 초기화 : S = V(G)

2) 시작 노드 r에서 다른 노드 w 사이의 거리(yw) 초기화, 노드 r과 연결되지 않는 노드들의 거리는 모두 ∞(무한대)로 설정한다.

Step-2)

1) 집합 S 중에서 최단 거리를 가진 노드 yv를 찾아서 이를 S에서 제거

2) 노드 v에 인접한 노드 w에 대해서 다음 조건 검사를 실시

yw = yv + cvw, if yv + cvw < yw (단, 노드 w는 S에 포함된 노드)

Step-3)

집합 S에 모든 노드가 제거될 때까지 Step 1을 반복

17

에이 스타 (A*)

▣ 개념

- 그래프의 시작점에서 도착점에 이르는 최단 경로를 찾는 알고리즘으로 최적 우선 탐색 기법을 이용하는 알고리즘

▣ 탐색원리

1) 시작 정점으로부터 목표정점 방향의 가장 근사한 정점을 선택(휴리스틱 함수 사용)

2) 이미 조사된 정점을 닫힌 목록으로, 조사 대상의 정점을 열린목록으로 규정

3) 열린목록에서 가장 유망한 정점을 취하며 조사된 정점은 닫힌목록으로 소속

4) 목표정점에 도달할때까지 열린목록을 조사하여 닫힘목록으로 변환시키는 작업을 반복

▣ 조건

- 최초 시작 정점이 주어짐

- 최단경로 보장 (단, h*(n) <= h(n) 일 경우)

- 알고리즘 평가함수 사용

▣ 특징

- 휴리스틱 함수를 활용

- 모든 정점이 아닌 목표정점까지의 최단거리 탐색

- 최적경로 탐색을 위한 평가함수 사용

- 시스템의 자원을 가장 적게 사용

 

18

벨만-포드(Bellman-Ford)

▣ 정의

- 가중 유방향 그래프에서 간서니 음수인 경우 최단 경로 문제를 결정하는 알고리즘

▣ 특징

- 경로의 음의 가중치 허용

- 다익스트라 알고리즘 보다는 수행 속도가 효율적이지는 못함

- 음의 가중치를 가져 다익스트라 알고리즘을 사용하기 힘든 경우 사용

19

플로이드(Floyd)

▣ 개념

- 그래프 상의 모든 노드에서 다른 모든 노드 사이의 최단 경로를 구하는 알고리즘

▣ 특징

- Dijkstra 알고리즘과 동일한 접근 방법 사용 (최단 경로를 수정하는 전략이 동일함)

- 시작 노드가 1개가 아니라 여러 개

20

백트래킹 알고리즘

▣ 정의

- 여러 후보해 중에서 특정 조건을 충족시키는 모든 해를 찾는 알고리즘

▣ 특징

- Non-Promising : 전혀 해답이 나올 가능성이 없는 마디

- Promising : 해가 나올만한 유망한 마디

- 모든 해

- 후보 해

▣ 방식

- 깊이우선탐색(Depth First Search : DFS)

- 너비우선탐색(Breadth First Search : BFS)

- 최선우선탐색(Best First Search/Heuristic Search)

▣ 목적

- 해가 될 조건을 만족시키는 "진짜 해"를 효율적으로 찾는 것

▣ 절차

1) 상태공간트리의 깊이 우선검색실시

2) 각 마디가 유망한지 점검

3) 만일 유망하지 않으면 그 마디의 부모마디로 돌아가서 검색을 계속

▣ 알고리즘

void checknode(node v)

{

  for (each child u of v)

    if (promising(u))

      if(there is a solution at u)

        write the solution;

      else

        checknode(u);

}

21

그리디(Greedy, 욕심쟁이) 알고리즘

▣ 정의

- 선택 시 마다 그 순간 최적의 해를 선택하여 최종적인 해를 도출하는 알고리즘

▣ 특징

- 최적성의 원리 : 주어진 선택 시점마다 최상의 해를 선택

- 최적해 미보장 : 결론적인 해가 최적의 해라는 보장은 불가능

- 효율성 개선 : 동적 계획법 대비 효율성(수행시간) 개선

▣ 수행절차

1) 해 선택 : 부분 해 집합에 더해질 다음 항목 선택

2) 적합성 검증 : 제약조건 위반여부 검사

3) 해 검증 : 주어진 문제의 해인지를 검사

▣ 알고리즘

int coin[4] = {500, 100, 50, 10}; //동전 종류 정의

int count[4];

int main() {

  int m = 770, i = 0, f = 0; //m=목표 거스름돈

  while(i < 4) {

    if(coin[i] > m)

      i++;

    else if(coin[i] < m) {

      m -= coin[i]; //코인 값 차감

      count[i]++;

    } else {

      f = 1;

      count[i]++;

      break;

    }

  if(f)

    print("%d 원 %d 개, %d 원 %d개, %d 원 %d개, %d 원 %d개 입니다.\n", coin[0], count[0], coin[1], count[1], coin[2], count[2], coin[3], count[3]);

  else

   printf("해를 구하지 못하였습니다. \n");

  return 0;

 

22

베이즈 정리

▣ 개념

- 새로운 정보 B에 의해 이를 근거로 어떤 사건 A가 발생할 조건부 확률, P(A|B)를 계산하는 이론

▣ 절차

- 사전확률 P(A) -> 추가정보 B -> 사후확률 P(A|B)

▣ 전확률의 정리

- 임의의 사건 B에 대하여 아래의 관계가 성립

- P(B) = P(A1)P(B|A1) + P(A2)P(B|A2) + ..... + P(An)P(B|An)

- P(A) = P(B1)P(A|B1) + P(B2)P(A|B2) + P(B3)P(A|B3) + P(B4)P(A|B4)

▣ 조건부 확률

- 사건 B 하에서 사건 A가 일어날 확률

- P(B1|A) = P(A∩Bi) / P(A)

23

딥뷰

▣ 인공지능의 특이점의 정의

- 인공지능 기술이 발전을 거듭하여 어느 순간 기술적 진보가 폭발적으로 빨라지는 순간으로, 즉, 인공지능의 연구 또한 인공지능이 스스로 하게 되는 기술 변화의 무한 가속 지점

▣ 특이점이 이루어지는 방향

- 인공지능 기술의 진보 : 인간의 지능 선회

- 인공지능의 확장 : 뇌를 인공신경망으로 대체

- 데이터베이스의 이용 : 데이터 기반 인공지능 결합

- 유전자 기술 : 인공 DNA 번역

▣ 액소브레인(Exobrain) 소프트웨어 개념

- 내 몸 바깥에 있는 인공두뇌로써 기계가 자연어를 이해하고 지식을 학습해 생산하는 인간과 기계와의 의사소통을 뛰어넘어 지식 소통이 가능한 인공지능 소프트웨어

▣ 액소브레인 소프트웨어의 기술요소

- 자연어 이해 및 질의 응답 기술

- 자가학습 및 추론 기술

- 인간모사형 학습 지능 원천

- 자율 협업 지능 기술

▣ 딥뷰의 개념

- 대규모 이미지 동영상을 분석하여 내용 이해 및 상황 예측을 실시간으로 수행, 대규모 시각 빅데이터의 분석 및 예측 가능한 시각지능 기반 시각 인공지능 소프트웨어

▣ 딥뷰의 기술요소

- 수집관리 기술 : 시각 데이터 뱅크 (대용량 시각 데이터 저장)

- 대규모 처리 기술 : 시각 데이터 처리 파이프 라인 SW (분산처리, CPU-GPU)

- 내용 분석 기술 :  다차원 시각 데이터 내용 분석 및 이해 SW (시각 텍사노미, 시각 데이터 처리, 시각 데이터 이해, 시공계열 공간 이해)

24

전문가 시스템(Experts System)

▣ 정의

- 전문가가 지니고 있는 지식이나 노하우 등을 컴퓨터에 집어넣어 전문가와 같은 판단이나 추론을 컴퓨터가 행하게 하는 시스템

▣ 특징

- 전문가 작업 자동화

- 고신뢰성 및 비용절감

▣ 활용 분야

- 의료, 화학, 국방

▣ 구성요소

- 사용자 I/F : 의사소통

- 추론엔진 : 지식 처리기

- 설명기관 : 도출과정, 규칙 제공

- 지식베이스 : 사실 저장

▣ 전문가 시스템의 추론방법

- 연역법 : 일반적 사실 -> 특수한 사실 이나 원리 추리 (삼단논법)

- 귀납법 : 개별적 특수한 사실 전제 -> 일반적 사실이나 원리 결론 (인과관계)

▣ 전문가 시스템의 추론방향

- 전방향 추론

- 후방향 추론

25

전문가 시스템 추론방향 - 전방향 추론

▣ 정의

- 데이터 지향방식으로 규칙의 조건부가 일치하면 결론부를 적용하는 추론 방법

▣ 특징

- 이용 가능한 정보로부터 출발하여 적절한 결론을 얻는 방법

- 규칙의 개수가 적을 때 유용한 방식

- 주어진 사실에서 유도되는 모든 것을 찾기 위한 문제에 적용

▣ 장점

- 추론 방법이 간단

- 주어진 문제에 해당하는 모든 해를 찾을 수 있음

▣ 단점

- 추론엔진의 동작이 비효율적

- 규칙의 수가 많을 경우 추론하는 시간이 많이 소요

- 문제와 관련없는 많은 규칙 수행

- 불필요한 새로운 사실을 많이 만듦

▣ 활용분야

- 진단 시스템

- DENDRAL : 유기화합물의 분자구조 파악

- CASNET : 녹내장 진단 및 치료

- NEOMYCIN : 뇌막염 류의 진단/치료

26

전문가 시스템 추론방향 - 후방향 추론

▣ 정의

- 어떤 목표를 하나 정한 후 이 목표가 성립하기 위한 조건들을 하나씩 맞춰가는 방법

▣ 특징

- 목적지향 추론방식

- 특별히 주어진 결론을 입증하기 위한 문제에 적용

▣ 장점

- 목표와 관련 없는 사실과 규칙 찾지 않음

- 특정한 목표의 참, 거짓 조사

▣ 단점

- 초기상태에서 모든 데이터가 주어져야 함

- 목표나 가정을 정하기 어려움

▣ 활용분야

- MYCIN : 박테리아로 인한 질병에 대한 의료진단시스템

- DART : 컴퓨터 하드웨어 고장진단 시스템

- GCA : 컴퓨터학과 대학원생의 과정계획을 도와주는 시스템

27

음성인식 기술

▣ 정의

- 마이크로 입력 받은 음성을 컴퓨터가 분석하고 특징을 추출한 후 미리 입력된 음성 데이터베이스와 비교하여 문자 혹은 명령어로 변환하는 기술

▣ 음성인식 에이전트 구조

- 음성인식

- 규칙기반시스템 (학습, 추론, 지식베이스, 문맥인식)

- QA 시스템

- 앱서비스

- TTS(음성합성)

▣ 음성인식 기술 처리 절차

1) 사용자의 음성을 인식하여 텍스트로 변환

2) 규칙기반 시스템에서 구축된 규칙에 의해 사용자의 음성 입력에 적절한 답이 이미 구축된 지식베이스에서 찾은 다음

3) 음성 합성(TTS)을 하여 사용자에게 다시 전달하는 구조

▣ 요소기술

- 끝점 추출 : 음성 시작점 끝점 추출 (에너지 기반 VAD)

- 특징 추출 : 특징 백터 추출 (MFCC, LPCC)

- 잡음 처리 : 특징 백터에서 잡음 제거 (Wiener Filter)

- 발화 검증 : 수락/거절 결정 기술 (반모델, 필러모델)

- 음형 모델 : 발음 특성 모델링 (HMM)

- 규칙 기반 : 학습, 추론, 지식베이스, 문맥인식 (Rule-Base System)

▣ 용어

- VAD(Voice Activity Detection) : 묵음 검출

- HMM(Hidden Markov Model) : 시계열 완전/불완전 데이터 통계 모델링

- MFCC(Mel-Frequency Cepstral Coefficient) : 단구간 신호의 파원 스펙트럼 표현

- LPCC(Linear Prediction Cepstrum Coefficient) : 선형예측 계수

- Rule-base System : 구축된 경험 지식을 기반으로 최적결과 도출

28

SIRI

▣ 정의

- 자연어 음성 질문을 통해 개인 비서 기능을 수행하는 애플의 Network 기반 지능형 개인 비서 서비스

▣ 특징

- 인공지능 : 음성질문 통한 정보 판단

- 대화방식 : 마이크 통한 음성인식, TTS 엔진 통한 대화

- 자연어 처리 : 의미분석, 담화분석

▣ 기술요소

1) Device Service

- 음성인식

- TTS, STT

- 자연어 처리

2) NW/Server Side

- 액티브 온톨로지

- 이동통신/무선 NW

29

NLQA (Natural Language Question Answering System)

▣ 정의

- 사용자의 질의에 대한 답변이 될 수 있는 정답을 문서 집합 내에서 탐색하여 사용자에게 제시해 주는 시스템

▣ 절차

1) 자연언어 입력

2) 단어사전 -> 구문해석 -> 구문해석

3) 의미사전 -> 의미해석 -> 의미구조

4) 지식베이스 추론 -> 결과

5) 응답문 생성 -> 응답문

6) 응답문 출력

▣ 구성요소

- 후보검색 단계 : 정답 선별

- 정답추출 단계 : 질의에 대한 응답

30

튜링 테스트

▣ 정의

- 판단자가 기계(컴퓨터)의 출력과 사람의 출력을 구별할 수 없다면, 그 기계는 인간과 같은 사고를 하였다고 규정할 수 있다는 테스트

▣ 테스트 절차

1) 차단된 2개의 방 한쪽에 텔레타이프와 피실험자A가 있고, 다른 한쪽 방에는 텔레타이프와 피실험자B 및  자연 언어 시스템으로 구성

2) 피실험자A는 텔레타이프를 통해 다른 방 피실험자B 혹은 시스템 중 어느 쪽과도 대화 가능

3) 피실험자 A에게는 대화의 상대가 피실험자 B인지 시스템인지 모르도록 함

4) 피실험자A 와 피실험자B 사이에는 서로를 알리는 어떠한 방법도 없음

5) 격리된 다수의 심사위원이 A, B 중 어느 쪽이 사람인지에 대한 평가를 함

31

유전자 알고리즘

▣ 정의

- 자연세계의 진화현상에 기반한 계산 모델로 진화론의 적자생존과 자연선택의 유전학에 근거한 적용 탐색과 최적화 문제 해결을 위한 알고리즘

- 생물의 진화과정을 모델링한 알고리즘으로, 현 세대를 구성하는 모집단에서 적합도(fitness)에 따라 염색체들을 선택하고, 유전 연산자를 적용하여 새로운 세대의 모집단을 생성해 나가는 과정

▣ 특징

- 최적의 해 탐색 : 진화 반복 최적 해 도출

- 비선형/계산불가 문제 해결 : 복잡한 문제 해결

- 개체군 사용 : 탐색공간에서 창조한 개체 집합 사용

- 자연계 진화과정 모방 : 생물유전학에 기본이론

- 코딩사용 : 파라미터를 코딩

- 군 탐색 : 점(point)이 아닌 다점(multi points : 군(population) 탐색

- 비용기반 검색 : fitness function이용, blind search

▣ 중심이론 (Darwin 이론)

- 적응도 (fitness) : 개체가 장래의 세대에 영향을 주는 범위 결정

- 번식 오퍼레이터 (reproduction operator) : 다음세대 자손 생성

- 유전 오퍼레이터 (genetic operator) : 자손 유전자 결정

▣ 구성

- 개체군 : 입력값들의 집합

- 적합도 함수 : 최적화 기준함수

- 선택 : 교배연산 적용 염색체 선정

- 교배 교차 : 새로운 자식 형성 과정

- 돌연 변이 : 자식 비트 값 변경

▣ 알고리즘 흐름도

- 1단계 : 유전자형의 결정

- 2단계 : 초기유전자 집단의 결정

- 3단계 : 각 개체의 적용도의 평가

- 4단계 : 선택(도태와 증식)의 실행

- 5단계 :  교배의 실행

- 6단계 : 돌연변이의 실행

▣ 유전자 알고리즘의 적용

- 교배 : 2개체간 염색체 교환

- 돌연변이 : 대립 유전자의 값으로 변경

- 역위 : 비트 순서 반대로 바꿈

- 치환 : 일부분 대치

▣ 선택법 (개체의 생존 분포 결정)

- 적응도 비례 방식 : 적응도에 비례한 확률로 전색

- 엘리트 보존 방식 : 가장 적응도가 높은 개체는 다음세대에 남음

- 기대치 방식 : 적응도의 분포에 기초하여 각 개체가 선택될 개수 계산

- 순위 방식 : 각 개체를 적응도 순으로 나열

- 토너먼트 방식 : 적응도 순으로 나열

 

32

지도 학습

▣ 정의

- 원하는 결과가 표현된 학습데이터를 이용한 학습 방법

▣ 알고리즘 종류

- 신경망 (Neural Network)

- 은닉 마르코프 모델 (Hidden Markov Model)

- 의사결정 트리

- 다층 신결망

- 지지 벡터 머신

- 베이지안 망

33

비지도 학습

▣ 정의

- 원하는 결과가 표현되지 않은 학습 데이터를 이용한 방법

▣ 알고리즘 종류

- 군집화

- K-Means

- 계층적 군집화

- 자기조직지도

- 주성분 분석

- 독립성분 분석

34

k-means 알고리즘

▣ 정의

- 주어진 데이터를 사전 정의된 k 개의 클러스터로 묶는 알고리즘

▣ 특징

- 데이터 중심점 : 상호배타적 포함

- 거리기반 분류기법 : 유클리디안 거리 최소화

- 데이터군 양자화 : 분할 시 오류 최소화

- 속도 및 구현 : 빠른 결과 산출

▣ 알고리즘

1) 군집의 수 K를 정의

2) 초기 K개 군집의 중심(Centroids) 선택

3) 각 관측 값들을 가장 가까운 중심의 군집에 할당

4) 새로운 군집의 중심 계산

5) 재정의 된 중심값 기준으로 다시 거리기반 군집 재분류

6) 군집 경계가 변경되지 않을 때가지 반복

35

단어구름

▣ 정의

- 문자 텍스트 상의 복수개의 단어들을 대상으로 그 단어들의 출현 빈도에 비례하는 글자의 크기나 글자의 색깔로 중요도를 나타내는 텍스트 시각화 방법

▣ 표현방법

- 텍스트 크기, 색상, 단어구름 형태 이용한 시각화

▣ 유형

- 문서 구름 : 단어 시각화

- 데이터 구름 : 숫자 시각화

▣ 도구

- Wordle, ABCYa, DoodleBuz

▣ 단어 선택 방법

1) 단어 동시 출현 : 여러 단어 관계 가정

2) 단어 동시 출현 확률 분포 : 확률분포 이용 단어 선택

3) Kullback-Leibler Divergence : 시간 변화 측정

4) Freshness : Kullback-Leibler Divergence 로 평균한 값

▣ 측정 방법

- 범위 : 단어구름 연결 웹문서 개수

- 중복 평균 : 중복된 문서 개수

- 중복 표준 편차 : 중복 문서 표준 편차

36

코워드 분석

▣ 정의

- 문장 안에서 함께 사용되는 단어들의 규칙을 조사해서 문서의 주제와 관련된 핵심 개념이 무엇이고 이들의 관계가 어떤지를 식별하는 내용분석 기법

▣ 핵심 절차

1) 데이터 수집 : 텍스트 수집

2) 데이터 전처리 과정 : 텍스트 마이닝(불용어 제거, 품사 태깅, 주석)

3) 동시출현단어 분석 과정 : 대표 키워드 도출