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

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번은 기억해야한다.

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


1. 알고리즘 기본개념

1) 알고리즘 생성단계
    설계 > 표현/기술 > 정확성 검증 > 효율성 분석

2. 기본 자료구조

1) 알고리즘에서 자료구조는?

1-1) 자료구조
    - 컴퓨터 기억공간 내에 자료를 표현하고 조직화 하는 방법
    - 프로그램 = 자료구조 + 알고리즘
    - 자료구조에 대한 고려 없는 효율적인 알고리즘의 선택, 또는 알고리즘에 대한 고려 없는 효율적인 자료구조의 선택은 무의미

기본 자료구조 =

배열, 연결리스트 , 스택 , 큐 , 트리 , 그래프

선형 자료구조 : 배열 , 연결리스트 , 스택 , 큐
    ㄴ 데이터에 순서가 있다.
비선형 자료구조 : 트리, 그래프
    ㄴ 데이터에 순서가 없다.


2) 배열

정의: 같은 자료형을 갖는 여러 개의 데이터를 하나의 변수에 저장해놓고 각각의 원소에 접근할 때에는 인덱스 첨자를 사용해서 접근하는 자료구조

특징: 논리적인 순서와 물리적인 순서가 같다.

단점: 삽입과 삭제가 발생하게되면 순서를 유지하기 위해서 자리의 이동이 불가피하다.

장점: 배열은 인덱스를 가지고 해당 원소에 직접접근하는 특징을 가지고 있다. 배열은 데이터가 어디에 저장되어있든지 어디로든 접근의 시간이 동일하다.

3) 연결리스트

하나의 원소는 노드라고 한다. 데이터가 들어가는 곳을 필드라고 한다.
하나의 노드는 하나의 데이터필드와 하나의 링크필드로 표현된다.

특징: 논리적순서와 물리적인순서가 같지 않다. 링크필드의 의미는 다음 노드의 메모리 주소값을 저장하고 있다.

장점: 삽입과 삭제가 간단하다.

단점: 특정 데이터를 찾아갈때는 처음부터 찾아가야 한다는 단점이 있다.


2-1,3-1) 배열과 연결리스트의 종류

배열 : 1차원 2차원 다차원배열

연결리스트: 단일 연결, 단일 원형 연결, 이중 연결, 이중 원형 연결

주어진 문제에 따라 자료구조를 선택해야 함.

접근을 빨리 하고싶으면 배열을 쓰는게 좋고 데이터의 접근보다는 데이터의 삽입과 삭제가 많다면 연결리스트 사용이 효과적일 수 있다.


4) 스택

정의: LIFO (Last In First Out) 후입선출 입구와 출구가 하나밖에 없는 구조

top : 스택에 데이터가 어디까지 쌓여져 있는가를 알림.

push: 삽입하는 연산

pop: 삭제하는 연산

데이터가 삽입 삭제때마다 top이 가리키는 위치가 달라짐.

5) 큐

정의: FIFO (First In FIrst Out) 선입선출 입구와 출구가 정방향

front: 삭제와 관련

rear: 삽입과 관련

삽입이 이뤄질경우 rear가 가리키는 값이 바뀜.

삭제가 이뤄질경우 front가 가리키는 값이 바뀜.


6) 트리

정의: 하나 이상의 노드로 구성된 유한 집합 T

조건1: T의 원소 가운데 단 하나의 루트 노드가 존재
조건2: 루트 노드를 제외한 나머지 노드는 n개의 서로 분리된 부분집합 T1, T2, TN(서브트리) 으로 나누어진다

주요 용어:

차수

리프노드(단말노드)

부모,자식,형제 노드

조상(선조) 후손(자손)

레벨 높이 깊이

6-1) 이진트리

정의: 각 노드의 차수가 2이하인 순서 트리

특성:
    - 레발 i에서 최대 노드의 개수 = 2의 i승
    - 높이 h에서 이진 트리의 최대 노드의 개수 = 2의 h승 - 1
    - 단말 노드(자식이 없는 노드)의 수 n0 = 차수가 2인 노드의 수에 +1 하면 된다. 
        n0 = n2 + 1

종류:
    - 포화 이진트리 : 높이 h 까지 중간에 빈 자리 없이 꽉 차있는 트리
    - 전 이진트리: 각 노드의 차수 = 0 이거나 2. 전 노드의 차수가 1인 경우가 없는 트리
    - 완전 이진트리: 노드의 레벨의 마지막 레벨 전까지가 포화 이진트리이고 마지막 레벨의 노드들이 왼쪽에서부터 마지막까지 중간에 빠짐없이 채워져있는 트리
    - 균형 이진트리: 왼쪽 서브트리와 오른쪽 서브트리의 노드레벨 차이가 1 이내인 트리

구현:
      * 배열을 이용하는 방법

* 연결리스트를 이용하는 방법

7) 그래프

정의: 그래프 G=(V,E)
    V: 정점의 집합, E: 간선의 집합

간선이 방향성이 있느냐에 따라 무방향과 방향그래프로 나뉜다.

각 정점을 잇는 선이 간선이다.

간선들에 값을 줄 수 있다. 비용이라 칭함. 간선들에 비용이 있는 그래프를 가중그래프(가중치그래프)라 한다.

7-1) 무방향 그래프

간선의 표현: (1,2) = (2,1)

그래프 표현: V(G) = { 1,2,3,4,5 } , E(G) = { (1,2),(1,3),(2,4),(3,5) }

7-2) 방향 그래프

간선의 표현: <1,2>


주요 용어:

인접,부수, 부분그래프, 경로, 경로의 길이, 차수(방향그래프 > 진입 차수 , 진출 차수), 단순 경로, 사이클, 루프, 연결, 강력 연결

구현

1) 인접 행렬

2) 인접 리스트

© 2015 Jundol in 음 아마 비둘기보단 똑똑할꺼야
Designed by DH / Powered by Tistory
180 / 48 / 117,633