728x90

등(차)비 수열

- 각 항마다 일정한 값을 더하거나 곱하는 수열

 

등(차) 비 수열 문제

- 수열 : 2, 6, 18, 54, 162, 486, ...

- 문제 : 위 등비 수열에 대해 100번째 항까지 합을 구하는 알고리즘을 제시하라

 

피보나치 수열

- 피보나치 수는 1과 1로 시작하며 다음 피보나치 수는 바로 앞 두 피보나치 수의 합이 되는 수열임

 

피보나치 수열 문제

- 수열 : 1, 1, 2, 3, 5, 8, 13

- 문제 : 위 피보나치 수열에 대해 100번째 항까지 합 구하는 알고리즘 제시하라

피보나치 수열 생성 과정

 

 

팩토리얼 수열

- N!은 자연수 N에 대한 누승(Factorial)으로서 1부터 N까지의 곱을 말하며 팩토리얼이라 함

 

팩토리얼 수열 문제

- 수열 : 1부터 100까지 누승의 합 -> S = 1! + 2! + 3! + 4! + ... + 100!

- 문제 : 위 팩토리얼 수열의 합을 구하여 출력하는 알고리즘을 제시하라

 

 

 

 

 

300x250
728x90

재귀 알고리즘과 점화식

1. 점화식의 이해

2. 병합 정렬의 점화식을 이용한 수행시간 분석

 

 

재귀 알고리즘

- 자기 호출을 사용하는 알고리즘

- 명시적으로 자기 호출을 사용하지 않더라도 그 속에서 자신과 똑같지만 크기가 다른 문제를 발견할 수 있는 경우 재귀적 성질을 포함하는 알고리즘의 복잡도는 점화식을 이용하여 접근이 가능함

 

점화식

- 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현하는 방법

- ex.1 등차수열의 점화식 : a_n = a_(n-1) + 2

- ex.2 팩토리얼의 점화식 : n! = n * f(n - 1)

 

 

병합정렬의 점화식을 이용한 수행시간 분석

mergeSort(A[], p, r) // A[p .. r]을 정렬한다.
{
    if (p < r) then{
        q <- (p+r)/2;                     p, r의 중간지점 계산
        mergeSort(A, p, q);                      전반부 정렬
        mergeSort(A, q + q, r);                  후반부 정렬
        merge(A, p, q, r);                            병합
    }
}

merge(A[], p, q, r)
{
   정렬되어 있는 두 배열 A[p ... q]와 A[q+1 ... r]을 합하여
   정렬된 하나의 배열 A[p ... r]을 만든다.
}

 

수행시간의 점화식

- T(n) = 2T(n/2) + 오버헤드

- 크기가 n인 병합정렬 시간

-> 크기가 n/2인 병합 정렬을 2번하고, 나머지 오버헤드를 더한 시간

 

 

점화식의 점근적 분석 방법

1. 점화식의 점근적 분석 방법의 종류

2. 반복 대치

3. 추정 후 증명

4. 마스터 정리

 

 

 

 

점화식의 점근적 분석 방법의 종류

- 점화식으로 표현된 식의 점근적 복잡도를 구하는 방법

- 반복 대치, 추정 후 증명, 마스터 정리

 

 

반복 대치

- 더 작은 문제에 대한 함수로 반복해서 대치해 나가는 방법

T(n) = T(n-1) + n

T(1) = 1
T(n) = T(n-1) + n
     = (T(n-2) + T(n-1)) + n
     ....
     = T(1) + 2 + 3 + ... + n
     = 1 + 2 + ... + n
     = n(n+1)/2
     = 세타(n^2)

 

 

예제 1 - n!를 구하는 문제

factorial(n)
{
     if (n = 1) return 1;
     return n * factorial(n - 1);
}

- T(n) = T(n - 1) + c

- 상수 시간 c : if문을 수행하는 시간과 곱셈을 한번 수행하는 시간

- 크기가 1(즉 , n = 1)인 경우 T(1) <= c이므로 T(n)을 다음과 같이 전개

T(n) = T(n-1) + c = T(n-2) + c + c = T(n - 2) + 2c = T(n - 3) + 3c

      = T(1) + (n - 1) c <= c + (n - 1) c = cn

 

 

추정 후 증명

- 식의 모양을 보고 점근적 복잡도를 추정한 다음 그것이 옳음을 귀납적으로 증명하는 방법

- T(n) <= 2T(n/2) + n의 점근적 복잡도는 T(n) = O(nlogn)임

 -> 즉, 충분히 큰 n에 대해서 T(n) <= cn log n인 양의 상수 c가 존재함

 

마스터 정리

- 특정한 모양을 가진 재귀식에 대해 바로 결과를 알수있는 정리

- T(n) = a T(n/b) + f(n)

  -> 입력 크기 n인 문제를 풀기 위해 입력 크기 n/b인 문제를 a번 풀고, 나머지 f(n)의 오버헤드가 필요한 알고리즘

- 병합 정렬 :  a = b = 2, f(n) = n인 경우

 

마스터 정리 가정

- a >= 1, b > 1에 대해 T(n) = a T(n/b) + f(n)인 점화식 -> n^(log_b a) = h(n)이라고 가정함

 

 

 

 

 

 

 

 

 

 

 

 

300x250
728x90

 

 

알고리즘 수행 시간 분석

1. 알고리즘 수행 시간

2. 알고리즘 수행 시간 분석 방법

 

 

알고리즘의 수행 시간

1. 알고리즘의 효율성을 분석하는 방법은 다양하지만 많은 경우에 알고리즘의 수행 시간을 이용하여 효율성 분석

- 실제로 구현하는 것이 필요함

- 동일한 하드웨어를 사용해야 함

 

2. 입력 크기에 대해 시간이 어떤 비율로 소요되는지 중요함

- 숫자의 정렬, 탐색의 입력 크기 : 숫자의 개수

- 지하철 최단 거리 탐색의 입력 크기 : 관련 노선도의 지하철 역의 개수

 

 

알고리즘 수행 시간 분석 방법

1. 수행시간이 상수인 예제

2. 수행 시간이 입력 n에 비례하는 예제

3. 수행 시간이 입력 n^2에 비례하는 예제

4. 수행 시간이 입력 n^3에 비례하는 예제

 

 

 

1. 수행시간이 상수인 예제

example1 (A[], n)
{
   i <- floor(n/3);
   return A[i];
}

- 입력 크기인 n이 변하여도 n의 개수에 비례하여 시간은 변하지 않음

- 상수 시간 소요

 

 

2. 수행 시간이 입력 n에 비례하는 예제

example2 (A[], n)
{
    sum <- 0;
    for i <- 0 to n-1 do
        sum <- sum + A[i];
    return sum;
}

 

- 입력 크기인 n이 변하면 수행 시간은 n의 개수에 비례하여 증가함

- 입력 n에 비례하여 수행 시간 소요

 

2. 수행 시간이 입력 n에 비례하는 예제 - 2

factorial(n)
{
   if (n=1) return 1;
   return n * factorial(n-1);
}

- 펙토리얼 예제

- 재귀 알고리즘 예제

- 함수 팩토리얼이 몇 번 수행되는지가 수행 시간을 좌우함

- 총 호출 횟수 n

 

3. 수행시간이 입력 n^2에 비례하는 예제

example3 (A[], n)
{
   sum <- 0;
   for i <- 0 to n-1 do
      for j <- 0 to n-1 do
          sum <- sum + A[i] * A[j];
   return sum;
}

- 입력 크기 n이 변하면 수행 시간은 n^2에 비례하여 증가함.

 

 

4. 수행 시간이 입력 n^3에 비례하는 예제

example4 (A[], n)
{
   sum <- 0;
   for i <- 0 to n-1
      for j <- 0 to n-1
         tmp <- A[]에서 임의로 n/2개를 뽑았을 때 이중 최대값;
         sum <- sum + tmp;
    return sum
}

- A[]에서 임의로 n/2개를 뽑았을 때 이중 최대 값 -> n에 비례하여 증가함

- 입력 크기인 n이 변하면 수행 시간은 n^3에 비례하여 증가함 -> n^3에 비례하여 수행 시간 소요

 

 

 

재귀와 귀납적 사고

1. 재귀 함수

2. 수학적 귀납법

 

 

재귀 함수

1. 문제를 해결하는 과정에서 해결하는 문제와 크기만 다르고, 자신의 해결 방법을 동일하게 적용하여 해결할 수 있는지 파악하여 주어진 문제를 푸는 방법

-> recursion, 되부름, 자기 호출 등으로 불림

2. 많은 알고리즘에서 사용

- 대표적으로 병합 정렬, 퀵 정렬, 하노이의 탑 문제, 팩토리얼 등

- 예시

 -> factorial : N! = N x (N-1)!

 -> 수열의 점화식 : a_n = 2 * 2 a_(n-1)

 

 

수학적 귀납법

1. 어떤 성질이 모든 자연수에 대해 성립함을 증명하기 위해 사용되는 방법

- 첫 번째 자연수에 대해서 참임을 증명

- 어떤 자연수에 대해서 참이면, 다음 자연수도 참임을 증명

 

2. 재귀 호출의 정당성은 수학적 귀납법과 관련됨 즉, 자기보다 작은 문제에 대해서 이 알고리즘이 제대로 작동한다고 가정

-> 자신보다 작은 문제에 대해 결론이 참임을 가정

-> 작은 문제와 자신의 문제의 관계를 파악하고, 자신의 문제에서도 결론이 맞음을 보임

 

3. 알고리즘 설계 시 유의점

-> 무한 루프에 빠지지 않도록 주의해야함

-> 재귀적인 관계를 잘 파악해야함

 

 

점근적 표기법

1. 복잡도의 점근적 표기

2. O(빅오)표기법

3. $\Omega$(빅 오메가) 표기법

4. $\Theta$(세타)표기법

5. 효율적인 알고리즘이 필요한 이유

 

 

복잡도 점근적 표기

1. 입력의 크기가 작은 문제

- 알고리즘의 효율성이 중요하지 않음

- 비효율적인 알고리즘도 무방

2. 입력의 크기가 충분히 큰 문제

- 알고리즘의 효율성이 중요함

- 비효율적인 알고리즘은 치명적임

3. 입력의 크기가 충분히 큰 경우에 대한 분석을 점근적 분석이라고함.

 

점근적 표기

- 복잡도는 입력도 크기에 대한 함수로 표기하는데, 이 함수는 주로 여러 개의 항을가지는 다항식

- 다항식을 단순한 함수로 표현하기 위해 점근적 표기를 사용함

- 입력의 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법

표기법 내용
빅오 표기법 최악의 경우 : 어떠한 경우에도 표기된 함수만큼의 성능은 보장(점근적 상한)
빅오메가 표기법 최선의 경우 : 운이 좋다면, 알고리즘은 표기된 함수만큼의 성능을 낼 수도 있음(점근적 하한)
세타 표기법 알고리즘이 거의 정확한 성능

 

 

알고리즘의 성능차

- 대규모의 데이터를 다룰때 확연하게 드러남

- ex. 연산 회수가 n^2+n인 알고리즘과 53n인 알고리즘 비교

- 데이터의 개수가 많을 수록 차수가 가장 큰 항이 가장 영향을 크게 미치고 다른항들은 상대적으로 무시함

 -> 이때문에 점근적 표기법에서는 최고차항만으로 알고리즘의 성능을 대략적으로 표기

 

 

 

O(빅-오) 표기법

- 점근적 상한선

- 최악의 경우 알고리즘 수행 시간을 나타냄

 -> 최악의 경우에도 성능을 보장하기 떄문에 가장 많이 사용하는 알고리즘 성능 표기법

-복잡도 f(n)과 O-표기를 그래프로 나타낸 것

- n이 증가함에 따라 O(g(n))이 점근적 상한이 됨.

- 빅오 표기법 종류 및 그래프

O 표기법 설명 해당 알고리즘
O(1) 최악의 경우에도 상수 시간 안에 종료됨 해시 테이블
O(log n) 최악의 경우에도 입력 개수 n이 배로 증가하더라도, 수행 시간의 증가가 일정한 속도 안에 종료됨
- ex : 입력데이터 10개를 처리하느데 1초걸린경우, 100개를 처리하는데 2초, 1000개를 처리하는데 3초걸리는 경우
이진 탐색
O(n) - 최악의 경우에 입력의 개수 n만큼 수행 시간 안에 종료됨
- 입력의 개수 n이 증가하는 속도만큼 수행 시간도 일정하게 증가함
순차 탐색
O(n log n) - log n이 상수 시간보다 증가율이 크기 때문에 n log n은 n과 n^2 사이에 존재함 병합 정렬
O(n^2) - 최악의 경우 입력 개수 n에 대한 제곱 만큼 수행 시간 안에 종료 됨 버블 정렬, 삽입 정렬
O(n^3) - 최악의 경우 입력 개수 n에 대한 3제곱 만큼 수행 시간안에 종료됨 행렬 곱셈
O(2^n) - 최악의 경우 입력 개수 n에 대해서 최대 2의 n제곱 만큼 수행 시간 안에 종료됨  

 

$\Omega$(빅 오메가) 표기법

- 점근적 하한선

- 최선의 경우 알고리즘 수행 시간을 나타냄 -> 거의 쓰이지 않음

- 복잡도 f(n)과 $\Omega$-표기 그래프

- n이 증가함에 따라 $\Omega$(g(n))이 점근적 하한이라는것

- 즉, g(n)이 $n_0$보다 큰 모든 n에 대해서 항상 f(n)보다 작다는 것을 보여줌



 

$\Theta$ 표기법

- 점근적 상한선과  점근적 하한선의 교집합

- 복잡도 f(n)과 $\Theta$-표기를 그래프로 나타낸 것

 

 

300x250
728x90

목표

 실세계에서 해결하고자 하는 모든 문제들에 대한 최적의 해결 방법을 전산학 적으로 고찰하기 위해 최적의 알고리즘을 학습하고, 각종 알고리즘에 대한 복잡도와 성능 및 특성을 고찰해 실세계에 적용할수 있는 능력을 배양한다.

 

 

 

알고리즘이란?

1. 알고리즘의 기원

2. 알고리즘의 정의

3. 알고리즘의 특징

4. 알고리즘의 분류

 

 

알고리즘 단어 유래

- 페르시아 수학자인 무함마드 이븐 무사 알콰라즈미 라틴 이름인 라고리즈미로부터 유래

- 무하마드 이븐 무사 알콰리즈미는 대수학의 아버지라 불리며, 수학 뿐만아니라 천문학, 지리학 등에도 많은 업적을 남김

 

유클리드 호제법

- 가장오래된 알고리즘

- 기원전 300년경 유클리드에 의해 증명됨

- 2개의 자연수 사이의 최대 공약수를 구하는 알고리즘

 

입력 : 자연수 m, n 단 m >= n > 0
출력 : m, n의 최대 공약수

Euclid(m, n)
if n = 0
    return m
return Euclid(n, m mod n)

 

 

알고리즘

- 어떠한 문제를 해결하기 위한 여러 동작들의 모임을 기술한 것

- 컴퓨터 공학에서 알고리즘은 명확한 입력과 출력을 가지고 있어야 함

 

 

프로그램 작성

- 프로그램 = 자료구조 + 알고리즘

- ex. 최대값 탐색 프로그램 = 배열 + 순차 탐색

 

 

알고리즘을 공부하는 이유

- 문제를 해결하기 위한 효율적인 과정을 습득하기 위함

- 기존의 알고리즘을 분석하여, 체계쩍으로 생각하는 훈련을 수행하기 위함

 

 

알고리즘의 예시

1. 학생 100명의 성적을 입력받아 가장 최저 점수를 출력하는 작업

- 입력 : 학생 100명의 성적

- 출력 : 입력된 100개의 성적 중 최소 값

 

2. 숫자 카드 74, 58, 45, 100, 32, 88 중 32 숫자카드를 찾는 작접

- 입력 : 숫자카드 74, 58, 45, 100, 32, 88

- 출력 : 32 숫자카드의 위치

 

 

 

알고리즘이 가져야 하는 요건

1. 입출력 : 입력과 출력을 가져야 함

2. 정확성 : 주어진 입력에 대해 항상 올바른 답을 주어야 함

3. 유한성 : 유한 시간 내에 종료 되어야 함

4. 효율성 : 시간적, 공간적 효율성을 가져야 함

5. 수행성 : 컴퓨터로 수행 가능해야함

 

 

알고리즘 분석 기준

1. 정확 성

- 모든 유효 입력에 대해 유한 시간 내 올바른 해를 찾아내는가 판단

2. 기억 장소 사용량

- 해를 찾아내는 데 사용되는 기억 장소의 사용량

- 입력 개수에 따른 증가율이 중요함

3. 수행 시간

- 해를 찾아내는데 걸리는 시간

- 절대 시간보다는 입력 개수에 따른 증가율이 중요함

 

 

알고리즘의 분류

분류 방식 분류
문제 해결 방법에 따른 분류 1. 분할 정복 알고리즘
2. 그리디 알고리즘
3. 동적 계획 알고리즘
4. 근사 알고리즘
5. 백트래킹 알고리즘
6. 분기 한정법
문제에 따른 분류 1. 정렬 알고리즘
2. 그래프 알고리즘
3. 기하 알고리즘

 

 

1. 분할 정복 알고리즘

- 주어진 문제의 입력을 분할하여 문제를 해결하는 알고리즘

- 분할된 입력에 똑같은 알고리즘을 적용(재귀를 이용하는 경우가 많음)

- ex. 병합 정렬, 퀵 정렬, 선택 정렬 등

 

2. 그리디 알고리즘

- 가능한 해들 중에서 가장 좋은 해를 찾는 알고리즘

- 수행 시점에서 가장 좋은 해를 찾아 나감

 -> 근시안적인 최적해를 찾는다고 할 수 있으며, 근시안적인 최적해를 모아서 문제의 최적해를찾음

- ex. 동전 거스름 문제, 최소 신장 트리 문제, 최단 경로 찾기 문제, 부분 배낭 문제

 

3. 동적 계획 알고리즘

- 최적회 문제 해결 알고리즘

- 입력 크기가 작은 부분 문제를 해결하고, 이를 이용해서 보다 큰문제를 해결하여, 최종적으로 주어진 입력크기의 문제를 해결하는 방법

- ex. 모든 쌍 최단 경로, 연속 행렬 곱셈, 배낭 문제, 동전 거스름돈 문제

 

4. 근사 알고리즘

- 지수 시간이 걸리는 문제(NP 문제)에 대한 근사해를 찾는 알고리즘

- ex. 여행자 문제, 정점 커버 문제, 통 채우기 문제, 클러스터링

 

5. 백트래킹 기법

- NP 완전 문제의 해를 탐색하기 위한 알고리즘

- ex. 여행자 문제, 체스 퀸 배치 문제

 

6. 분기 한정 기법

- 큰 입력에 대해 백트래킹 기법이 갖는 단점을 보완하기 위해 고안된 기법

- ex. 여행자 문제 등

 

 

알고리즘 분석

1. 알고리즘을 분석하는 이유

2. 알고리즘의 수행 시간

3. 알고리즘의 공간 사용량

 

알고리즘을 분석하는 이유

1. 정확성 확인(무결성 확인)

- 모든 유효한 입력에 대해 유한 시간 내에 올바른 해를 찾아내는가 판단하기 위함

2. 효율성 확인

- 한정된 자원(기억 장소 사용량, 수행 시간)에서 효율적으로 작동하는지 확인하기 위함

3. 궁극적으로 알고리즘을 분석하여 얻는 이점

- 알고리즘 분석 -> 체계적이고 효율적으로 생각하는 훈련을 할 수 있음

- 문제를 해결하기 위해 중요한 것과 중요하지 않은 것을 판단할 수 있음

- 문제를 단순화 하여 생각 할 수 있음

- 다른사람의 아이디어에 대한 효율성을 판단 할 수 있음

 

 

알고리즘 수행 시간

1. 알고리즘의 효율성을 분석하는 방법은 다양하지만 많은 경우 알고리즘의 수행시간을 이용하여 효율성 분석

2. 시간 복잡도

 - 입력 크기에 비례하여 작업시간이 어떠한 비율로 증가하는지 확인함.

3. 시간 복잡도를 사용하는 이유

- 실측으로 시간을 측정하는 경우 프로그래밍 언어, 컴퓨터 성능, 프로그래머의 실력 등의 다양한 변수에 따라 달라질 수 있음

 

 

수행 시간 분석 방법

- 최선 경우 분석

- 최악 경우 분석

- 평균 경우 분석

 

 

 

 

가짜 동전 찾기 알고리즘

- 문제 : 많은 수의 동전 중에서 1개의 동전이 가짜 동전인 경우 가짜 동전을 어떻게 찾을까?

- 가짜 동전의 크기와 모양은 진짜 동전과 동이랗며 무게만 약간 가벼움

- 무게의 차이를 감지 할 수 있는 양팔의 저울만 주어짐

 

알고리즘 1

- 해결 방법 : 한쪽에 1개의 동전을 올려놓고 나머지 동전을 하나씩 바꾸어 가면서 무게를 잼

- 수행시간 분석

 -> 최선 경우 분석 : 운이 좋은 경우 1번만에 찾을 수 있음

 -> 최악 경우 분석 : 운이 나쁜 경우 즉, n - 1번 수행해야함

 

알고리즘 2

- 해결방법 : 동전을 2개씩 선택하여 2개의 동전을 양팔 저울에 올려놓고 무게를 잰 후 가벼운 동전을 찾아냄

- 수행 시간 분석

 -> 최선 경우 분석 : 운이 좋은 경우 1번 만에 찾을 수 있음

 -> 최악 경우 분석 : 운이 나쁘면 모든 경우 즉, n/2번 수행해야함

 

알고리즘 3

- 해결 방법

 -> 동전을 똑같은 개수로 반으로 나누어 두 무리를 만들고 무개를 잰 후 가벼운 쪽을 찾고, 나머지를 다시 반으로 나누어 가벼운 쪽을 찾음

- 수행 시간 분석

 -> 일반적인 n에 대해서 log_2 n번 수행해야함.

 

알고리즘 분석 - 동전 개수가 1024개 인 경우

방법 분석 내용
알고리즘1 - 최악의 경우 : 1023번 수행
- 평균의 경우 512번 수행
- 최선의 경우 : 1번 수행 (큰 의미없음)
알고리즘2 - 최악의 경우 : 512번 수행
- 평균의 경우 : 256번 수행
- 최선의 경우 : 1번 수행
알고리즘3 - 최악의 경우 : 10번 수행
- 평균의 경우 : 10번 수행
- 최선의 경우  10번 수행

=> 알고리즘 3은 동전의 개수가 n인 경우 어떠한 경우에도 log_2 n번의 수행으로 동전을 찾을수 있기 때문에 가장 효율적

 

 

알고리즘의 공간 사용량

- 알고리즘의 공간 사용량도 알고리즘의 효율성을 분석하는 방법 중 하나

- 공간 복잡도 : 입력 크기에 비례하여 작업 공간이 어떠한 비율로 증가하는지 분석하는 것

- 공간 복잡도를 시간 복잡도와 함께 사용하는 이유

 -> 실측으로 공간 사용량을 측정하는 경우 프로그래밍 언어, 프로그래머 실력 등 다양한 변수에 따라 달라질 수 있음.

 

 

300x250
728x90

 

 

알고리즘

- 어떤 문제를 해결하기 위한 작업단계를 명확하게 기술한 것

 

 

알고리즘의 이해

1. 프로그램 개발 과정

2. 알고리즘 개념

3. 알고리즘 표현 방법

 

 

 

프로그램

- 어떤 문제를 해결하도록 컴퓨터에게 주어지는 명령어들의 집합

( 유한한 ) 입력 -> 자료(데이터) + 알고리즘 -> 입력에 대응되는 출력

- 알고리즘 : 특정한 작업을 수행하는 명령어들의 집합

- 자료구조 : 주어진 작업을 해결하기 위해 필요한 자료를 효과적으로 표현하고 효율적으로 처리, 저장하기 위한 구조를 설계하는 방법

 

 

 

 

프로그램 개발 과정 - 프로그램 생명 주기

1. 요구 사항 분석

2. 시스템 명세

3. 설계

4. 구현

5. 테스트

6. 유지 및 보수

 

 

 

1. 요구 사항 분석

- 개발할 프로그램의 기능과 제약조건, 목표 등을 프로그램의 사용자와 함께 명확히 정의하는 단계

- 개발할 프로그램의 성격을 정확히 이해하고 개발방법과 필요한 자원 예측

 

2. 시스템 명세

- 시스템이 무엇을 수행하는가를 정의

- 입력, 처리 절차, 출력을 정의함

 

3. 설계

- 시스템 명세 단계에서 정의한 기능을 실제로 수행하기 위한 방법을 결정

- [예시] 시스템을 구성하는 내부 프로그램간의 관계, 사용자 인터페이스 등

- 하향식 설계 방법 : 상위 단계에서 하위 단계로 설계하는 방법

- 상향식 설계 방법 : 하위 단계에서 작은 문제를 먼저 해결하고 이를 이용하여 상위 단계의 큰 문제를 해결하는 방법

- 객체지향 설계방법 : 문제 해결을 위해 객체를 만들고 이를 재사용하는 방법

 

4. 구현

- 설계 단계에서 결정한 문제 해결 방법을 프로그래밍 언어를 사용하여 실제 프로그램으로 구체화 하는 단계

 

5. 테스트

- 개발한 시스템이 고객 요구 사항을 만족하는지, 실행 결과가 맞는지 검사하고 평가함

- 단위 테스트 unit test : 시스템 최소 구성요소인 컴포넌트, 모듈에 대해서 개별적으로 시행

- 통합 테스트 : 단위 테스트를 통과한 모듈을 연결한 전체 시스템에 대해 통합적으로 시행

- 인수 테스트 : 완성된 시스템에 대해 실제 자료를 사용한 최종 테스트

 

6. 유지 및 보수

- 시스템이 설치 된 이후 행하는 모든 활동

- 사용 중에 발견한 프로그램의 오류 수정, 시스템과 관련된 환경 변화에 적응, 시스템의 성능 향상, 앞으로 발생할지 모를 변경 사항 수용 등

 

 

 

알고리즘이란?

- 특정 작업을 수행하는 명령어들의 집합

- 문제를 해결하기 위해 기술한 체계적 단계

 

 

알고리즘의 특성

- 입력 : 문제와 관련된 외부 데이터

- 출력 : 입력을 처리한 결과

- 정확성 : 수행할 작업의 내용과 순서가 명확해야함

- 유한성 : 알고리즘은 유한한 단계를 거친 후 종료되어야 함

- 효과성 : 알고리즘에서 사용하는 작업은 실행이 가능하여야 함

- 일반성 : 같은 유형의 문제에 대해 동일하게 적용 가능

 

 

알고리즘의 표현 방법

1. 자연어를 이용한 서술적 표현 방법

- 사람이 사용하는 언어를 이용하여 알고리즘 표현

- 사람에 따라 언어의 일관성과 명확성을 유지하기 힘듬

- ex. 라면 끓이기

 

2. 순서도를 이용한 방법

- 알고리즘을 도식화 하여 표현

- 순서도의 작성 규칙에 따라 도식화

- 명령의 흐름을 쉽게 파악  가능

- 복잡한 알고리즘을 표현하는데 한계가 있음

- 순서도에서 사용하는 기호들

- 1부터 5까지의 합을 구하는 알고리즘의 순서도 표현

 

3. 프로그래밍언어를 이용한 방법

- 프로그래밍 언어를 이용하여 알고리즘을 표현

- 특정 프로그래밍 언어를 모르는 사람은 이해가 힘들고, 프로그래밍 언어 마다 재작업필요

- ex. C언어, 파이썬, 자바

 

 

4. 의사 코드(Pseudo-code)를 이용한 방법

- 의사 코드 : 프로그래밍 언어는 아니지만 프로그래밍 언어의 형태를 가지는 코드

- 직접 실행이 불가능

- 프로그래밍 언어 사이의 변환이 용이

- ex. 1부터 5까지 합을 구하는 알고리즘의 의사 코드 표현

function sum1to5()
	sum = 0;
    n = 0;
    while (n <= 5)
    	n = n + 1;
        sum = sum + n;
    return sum;

 

의사코드 표현법

1. 지정문

- 변수에 값을 지정

- <- 오른쪽 끝에 있는 값을 왼쪽에 있는 변수에 저장

- 세미 콜론을 사용하여 지정문의 끝을 표시

2. 조건 문

- 조건에 따라 실행할 명령문 결정

- if문

if (조건식)
   명령문 1;
   명령문 2;

- if-else 문

if (조건식)
   명령문1;
   명령문2;
else
   명령문3;
   명령문4;

 

반복문

- 일정한 명령을 반복 수행

- for문

for (초기화; 조건식; 증감식)
    명령문1;
    명령문2;

- while 문

while (조건식)
   명령문1;
   명령문2;

 

함수

- 작은 작업 단위

function 함수이름 (매개변수)
   명령문1;
   명령문2;
   ...
   return 결과값

 

알고리즘의 복잡도와 빅오 표기법

1. 알고리즘의 복잡도

2. 빅오 표기법

 

 

 좋은 알고리즘이란?

- 수행시간이 짧음

- 사용된 메모리 공간이 적음

 

 

알고리즘 평가 기준

1. 공간 복잡도

- 알고리즘 수행에 필요한 메모리 공간

- 고정 공간의 크기 + 가변 공간의 크기

- 고정 공간 : 프로그램 저장 공간 등

- 가변 공간 : 실행 과정에서 자료와 변수를 저장하는 공간, 함수 실행에 관련된 정보를 저장하는 공간 등

 

2. .시간 복잡도

- 알고리즘 수행 시간

- 컴파일 시간 + 실행 시간

- 컴파일 시간 : 고정된 시간

- 실행 시간 : 컴퓨터 성능에 좌우 -> 명령문의 실행 빈도수를 계산

 

 

 

피보나치 수열 알고리즘의 공간 복잡도

피보나치 수열

- f(0) = 0

- f(1) = 1

- f(n) = f(n-1) + f(n-2) (n>=2)

- 피보나치 수열 알고리즘

 

-피보나치 수열의 공간

 

- 피보나치 수열의 실행 빈도

 

 

시간 복잡도 분석 방법

1. 실제 실험을 통한 수행 시간 측정

- 실험에 사용되는 장치에 의존 -> 사용하지 않음

2. 알고리즘에서 수행되는 문장들의 개수 계산

- 실험에서 사용되는 장치에 독립 -> 실제 사용됨

3. 시간 복잡도의 점근적 표기법

- 정확한 문장들의 개수 대신 수학적 기호를 사용하여 시간 복잡도를 표현

- 알고리즘의 입력 크기가 변화함에 따른 수행 시간을 수학적 기호를 사용하여 표현

- 동일 문제에 대한 알고리즘 사이의 수행 시간 비교에 적합

- ex. O-표기법, $\Omega$-표기법, $\Theta$-표기법

 

 

 

빅오 표기법(O-표기법)

- 알고리즘 복잡도 중에서 가장 많은 영향을 미치는 항을 위주로 복잡도를 표기

- f(n) = O(g(n)) : 충분히 큰 n에 대해 f(n) <= c g(n)을 만족시키는 상수 c가 존재

 

 

빅오 표기법의 성질

- O(1) ~ (O($n^3$) : 다항식 시간 복잡도

- O($2^n$) : 지수 시간 복잡도

 

 

여라가지 알고리즘

1. 수연산 관련 알고리즘

2. 행렬식 계산 알고리즘

3. 탐색과 정렬 알고리즘

 

 

 

수연산 관련 알고리즘

1. 유클리드 알고리즘

- 두 자연수의 최대공약수를 계산하는 알고리즘

- 두 자연수 a, b에 대해 a, b의 최대 공약수 GCD(a, b)로 표기

- 최대 공약수의 성질 : 두 자연수 a, b에 대하여 a = bq + r, 0 <= r < b를 만족시키면 GCD(a, b) = GCD(b,r) 성립

- 유클리드 알고리즘의 의사 코드

function Euclid(a, b)
  if (a < b)
    tmp = a;
    a = b;
    b = tmp;
  while (b != 0)
    r = a % b;
    a = b;
    b = r;
    
  return a;

 

2. 재귀 알고리즘

- 알고리즘이 자기 자신을 다시 호출하는 알고리즘

- 피보나치 수열 알고리즘

function fibonacci(n)
  if (n < 0)
     stop;
  if (n <= 1)
     return n;
  
  return fibonacci(n - 1) + fibonacci(n - 2);

 

 

 

행렬식 계산 알고리즘

- 아래의 n x n 행렬식 A에 대하여

- A = (a)에 대해 det(A) = |A| = a

- 행렬식 계산 알고리즘의 의사 코드

 

 

 

탐색과 정렬 알고리즘

탐색

- 어떤 집합에서 특정 원소를 찾는 작업

 

1. 순차 탐색 알고리즘

- 집합의 원소를 처음부터 하나씩 비교하여 탐색하는 알고리즘

 

2. 버블 정렬 알고리즘

- 인접합 2개의 원소를 비교해 기준에 따라 순서를 바꾸는 방식의 정려 알고리즘

300x250
728x90

 

 

확률 변수

- 통계 조사나 실험 데이터로 도출된 개별 자료를 실수와 대응 시키는 자료

 

확률 분포

- 확률 변수의 전체적인 분포를 나타내는 개념

 

정규 분포 곡선

- 종모양의 확률 밀도 함수

- 평균 근처에 가장 많은 자료 위치

- 양 극단에 위치하는 자료가 줄어듬

 

 

확률 변수

1. 확률 변수의 정의

2. 이산 확률 분포

3. 연속 확률 분포

 

 

확률 변수 Random Variable

- 어떤 시행에서 일어날 수 있는 모든 경우의 집합 S (표본 공간)의 각 원소를 실수 집합 R의 한 원소에 대응 시키는 함수

- X : S -> R

- 확률 변수는 보통 문자 X, Y, Z 등으로 표기

 

 

확률 변수 예시

- 한 개의 동전을 2번 던지는 시행에서 앞면이 나오는 횟수를 X라고 한다면

- S = {(앞, 앞), (앞, 뒤), (뒤, 앞), (뒤, 뒤)}

- X : S -> R

  (앞, 앞) -> 2

  (앞, 뒤) -> 1

  (뒤, 앞) -> 1

  (뒤, 뒤) -> 0

 

 

확률 변수

- 이산 확률 변수

- 연속 확률 변수

 

이산 확률 변수

- 치역이 이산 집합인 확률 변수

- ex.1 : 10갸의 동전을 동시에 던질때 앞면이 나온 동전의 개수를 나타내는 확률 변수

- ex.2 : 주사위를 던져서 1의 눈이 나올 때까지 던진 횟수를 나타내는 확률 변수

 

 

연속 확률 변수

- 치역이 연속 집합인 확률 변수

- ex.1 : 10cm 씩 커지는 동심워 10개로 구성된 양궁판에 양궁 선수가 활을 쐇을 때, 화살이 꽂힌 위치와 중심으로부터 거리를 나타내는 확률 변수

- ex 2 : 버스 정류장에서 배차 간격이 10분인 버스를 기다리는 시간을 나타내는 확률 변수

 

 

 

이산 확률 분포의 확률 질량 함수

- 이산 확률 변수 X에 대해 임의의 실수 x를 취할 확률을 대응 시키는 함수

- f(x) = Pr(X = x)로 표기

 

 

이산 확률 분포의 확률 질량 함수의 예시

- 한 개의 동전을 2번 던지는 시행에서 앞면이 나오는 횟수를 x라 한다면

- S = {(앞, 앞), (앞, 뒤), (뒤, 앞), (뒤, 뒤)}

- X : S -> R

 (앞, 앞) -> 2

 (앞, 뒤) -> 1

 (뒤, 앞) -> 1

 (뒤, 뒤) -> 0

 

 

이산 확률 분포 확률 질량 함수의 성질

- 이산 확률 변서 X의 확률 질량 함수 f(x)에 대해서

- 위의 한개의 동전을 2번 던지는 시행 예시를 참고하면 f(0) + f(1) + f(2) = 1

 

 

이산 확률 분포

- 이산 확률 변수 X가 가지는 값과 그 값에서의 확률 질량 함수의 값의 대응 환계 또는 그 대응관계를 나타내는 표

- ex. 한 개의 동전을 2번 던지는 시행에서 앞면이 나오는 횟수를 X라고 한다면

 

연속확률 분포의 확률 밀도 함수

- 연속 확률 변수 X에 대하여 다음을 만족시키는 함수 f를 X의 확률 밀도 함수라고함

- f(x) >= 0

 

연속 확률 분포

- 연속 확률 변수 X가 가지는 값과 그 값에서 확률 밀도함수의 값의 대응 관계

- ex. 정규 분포: 확률 변수 X의 확률 밀도 함수가 다음과 같은 확률 분포

 

 

이산 확률 변수와 이항 분포

1. 이산 확률 변수의 기댓값

2. 이산 확률 변수의 분산과 표준 편차

3. 이한 분포

 

이산 확률변수의 기댓값

- 이산 확률변수 x의 기댓값 E(X)는 E(X) = $\sum_x$ x f(x)로 정의됨

- ex. 한 개의 동전을 2번 던지는 시행에서 앞면이 나오는 횟수를 X라고 한다면

- X의 확률 분포

- E(X) = 0 x $\frac{1} {4}$ + 1 x $\frac{1} {2}$ + 2 x $\frac{1} {4}$=1

 

 

 

이산 확률 변수의 기댓값

- 기댓값 성질 : 이산 확률 변수 X와 실수 c에 대하여

- E(c) = c

- E(c X) = c E(X)

- E(X + c) = E(X) + c

 

 

이산 확률 변수의 분산

- 이산 확률변수 X와 그 기댓값 $\mu$ = E(X)에 대해 X의 분산 V(X)는 다음과 같이 정의

=> V(X) = $\sum_x$ (x - $\mu$ $)^2$ f(x)

- V(X) = E(( X - $\mu$ $)^2$)

 

 

이산 확률 변수의 표준 편차

- 이산 확률 변수 X에 대하여 X의 표준편차 $\sigma$(X)는 다음과 같이 정의함

=> $\sigma$(X) = $\sqrt{V(X)}$

- ex. 한 개의 동전을 2번 던지는 시행에서 앞면이 나오는 횟수를 X라 한다면

 

분산과 표준 편차의 성질

- 확률 변수 X와 실수 c에 대하여

 

 

이산 확률 변수 X의 확률 분포가 다음과 같을 때

- E(X) = 3

- E($X^2$) = 1 x 0.1 + 4 x 0.2 + 9 x 0.3 + 16 x 0.4 = 10

- V(X) = E($X^2$) - E(X$)^2$ = 1

- $\sigma$(X) = 1

 

 

 

베르누이 분포

- 시행 결과가 1(성공) 또는 0(실패) 두 가지 경우만 일어나고 성공 확률이 p인 분포를 베르누이 부포라 하고, B(1, p)로 표기

- 확률 분포 X가 베르누이 분포 B(1, p)를 따르면

 -> E(X) = 0 x (1 - p) + 1 x p = p

 -> E($X^2$) = $0^2$ x ( 1 - p ) + $1^2$ x p = p

 -> V(X) = E($X^2)$ - E(X$)^2$ = p - $p^2$ = p ( 1 - p )

 

 

베르누이 분포의 예시

- 주사위를 한번 던지는 시행에서 1의 눈이 나오면 1의 값을, 그 외 눈이 나오면 0의 값을 갖는 확률 변수 X에 대하여

- X는 베르누이 분포 B(1, $\frac{1} {6}$을 따름

- E(X) = p = $\frac{1} {6}$

- V(X) = p(1-p) = $\frac{5} {36}$

 

 

이항 분포

- 성공률이 p인 베르누이 시행을 n회 반복한 후 성공 횟수를 X라 할때, X의 확률 분포를 이항분포라 하며 B(n,p)라고 표

- 확률 변수 X가 이항 분포 B(n, p)를 따르면

-> f(x) = $\binom{n}{x}$ $p^x$(1 - p$)^{n - x}$, x = 0, 1, ..., n

-> E(X) = np

-> V(X) = np(1-p)

 

이항 분포의 예시

- 흰 공이 6개, 검은 공이 4개가 들어 있는 주머니에서 임의로 공을 한 개 꺼내어 색을 확인한 후, 다시 넣기를 100번 반복할 때, 흰 공이 나오는 횟수를 확률 변수 X라고 하면, 확률 분포 X가 이항 분포 B(n, p)를 따르면

- X는 이항 분포 B(100, 6/10)을 따름

- E(X) = np = 100 x $\frac{6} {10}$ = 60

- V(X) = np(1-p) = 100 x $\frac{6} {10}$ x $\frac{4} {10}$ = 24

 

 

 연속확률변수와 정규분포

1. 연속확률변수

2. 정규분포

3. 이항분포와 정규 분포의 관계

 

 

 

 확률 밀도 함수

- 연속 확률 변수 X에  대해 다음을 만족시키는 함수 f를 X의 확률밀도함수라고 함

- f(x) >= 0

 

 

- 연속 확률 변수 X와 그 확률 밀도 함수 f(x)에 대해 X의 기댓값 E(X)는 다음과 같이 정의됨

 

- 기댓값의 성질 : 연속 확률 변수 X와 실수 c에 대해

 -> E(c) = c

 -> E(cX) = cE(X)

 

- 연속 확률 변수 X와 그 기댓값 $\mu$ = E(X)에 대해 X의 분산 V(X)는 다음과 같이 정의됨

- V(X) = E((X - $\mu$$)^2$)

- $\sigma$(X) = $\sqrt{(X)}$를 X의 표준 편차라 함

 

분산과 표준 편차의 성질

- 연속확률변수 X와 실수 c에 대하여

 

 

정규 분포

- 확률변수 X의 확률밀도함수가 다음과 같이 주어졌을 때

- X는 정규분포를 따른다고 하며 N($\mu$, $\sigma^2$)로 표기

 

- 확률 변수 X가 정규 분포 N($\mu$, $\sigma^2$)

 -> E(X) = $\mu$

 -> V(X) = $\sigma^2$

 

 

표준 정규분포

- N(0, 1)을 표준 정규분포라 함

 

표준 정규분포의 확률밀도함수

 

 

표준 정규분포표

- Z가 표준정규분포를 따르면

- Pr(Z <= 2) = ?

- Pz(-1 <= Z <= 1.96) = ?

표준정규분포표

 

정규분포와 표준 정규분포

- 확률변수 X가 정규분포 N($\mu$, $\sigma^2$를 따르면 Z = $\frac{X - \mu} {\sigma}$는 표준 정규 분포를 따름

 

표준 정규 분포 예시

- X가 정규 분포 N(1, $2^2$)를 따를 떄 -> 표준 정규 분포로 변환 후 계산

Z = $\frac{X - 1} {2}$

2Z = X - 1

2Z + 1 = X

- Pr(X <= 5) = Pr(Z <= 2) = 0. 5 + 0.4972 = 0.9772

 

 

 

 

이항 분포와 정규 분포의 관계

- 확률 변수 X가 이항 분포 B(n,p)를 따르고 n이 충분히 크면 X는 근사적으로 N(np, np(1-p))를 따름

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

알고리즘 - 1 알고리즘의 정의와 필요성  (0) 2020.06.10
이산 수학 - 20 알고리즘  (0) 2020.06.09
이산 수학 - 18 확률  (0) 2020.06.09
이산 수학 - 17 순열과 조합  (0) 2020.06.09
이산 수학 - 16 트리 활용  (0) 2020.06.08
728x90

표본 공간 S

- 시행 또는 실험에 의해 일어날 수있는 모든 경우의 집합

- 시행 : 어떤 일이 일어날 가능성을 조사하기 위해 실험하거나 관찰하려는 행위

- 사건 : 시행의 결과로 일어난 현상들의 집합 또는 표본 공간의 원소들의 집합

 

예시 1. 주시위 하나를 던지는 경우

- 표본 공간 = {1, 2, 3, 4, 5, 6}

- 홀수가 나오는 사건 : {1, 3, 5}

 

예시 2. 1에서 9까지 숫자가 적힌 9장의 카드 중에서 임의로 한 장을 뽑는 경우

- 표본 공간 = {1, 2, 3, 4, 5, 6, 7, 8, 9}

- 8의 약수가 나오는 사건 = {1, 2, 4, 8}

 

 

 

표본 공간의 종류

1. 이산 표본 공간

- 표본 공간에 속하는 원소의 개수가 유한하거나 셀 수 있는 경우

- 주사위를 2번 던지는 시행

- 동전을 3번 던지는 시행

 

2. 연속 표본 공간

- 표본 공간에 속하는 원소의 개수를 셀수 없는 경우

- 학생들의 몸무게를 측정하는 시행

- 연필의 길이를 측정하는 시행

 

 

 

확률

- 어떤 사건이 일어날 가능성을 확률로 표시한 것

- 사건 A에 대해 사건 A가 일어날 확률을 Pr(A)로 표기

- S가 유한 집합인 경우 Pr(A) = |A|/|S|

 

주사위 2개를 던질 때

- S = {(1,1), (1, 2), . . ., (6, 6)} -> |S| = 36

- A = 두 주사위 눈의 합이 5 이하인 사건

- B = 두 주사위 눈의 곱이 3의 배수 인 사건

 

주머니에 흰 공 6개, 파란 공 4개, 노란 공 3개가 있을때 이 중 4개를 순서에 상관없이 꺼내는 경우

- A = 흰 공이 2개, 파란공이 2개인 사건

- B = 모든 공이 흰 공인 사건

 

사건의 종류

- 표본 공간 S와 사건 A, B에 대하여

- A와 B의 합사건

- A와 B의 곱 사건

- A의 여사건

- 차 사건

- 배반 사건 : A와 B의 곱사건(교집합)이 공집합 일떄

 

 

사건 예시

- 표본 공간 S와 사건 A, B에 대해

- 주사위를 1회 던질 때, A는 주사위의 눈이 홀 수가 되는 사건, B의 주사위 눈이 3의 배수인 사건

 

 

 

 

 

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

이산 수학 - 20 알고리즘  (0) 2020.06.09
이산 수학 - 19 확률 분포  (0) 2020.06.09
이산 수학 - 17 순열과 조합  (0) 2020.06.09
이산 수학 - 16 트리 활용  (0) 2020.06.08
이산 수학 - 15 트리  (0) 2020.06.08
728x90

확률

- 우리 일상 생활에서 자주 접하는 수학적 개념

- 확률 계산을 위한 개념 => 순열과 조합

 

순열과 조합

- 확률 계산에서 많이 사용하는 도구

 

경우의 수 관련 용어

- 시행 : 어떤 일이 일어날 가능성을 조사하기 위해 실험하거나 관찰하는 행위

  -> 주사위를 던져 나오는 주사위 눈을 조사하는 행위

- 사건 : 시행의 결과로 나타나는 현상

  -> 주사위를 던져 짝수의 눈이 나오는 현상

- 경우의 수 : 어떤 사건이 일어나는 방법의 가지수

  -> 주사위를 던져 짝수의 눈이 나오는 사건의 경우의 수 = 3

 

 

 

실생활에서 경우의 수

- 동전 2개를 던질때 2개의 동전이 다른 면이 나오는 경우의 수 = 2

 -> (H, T) (T, H)

- 두 사람이 가위바위보 할때 비기는 경우의 수 = 3

 -> (가위, 가위), (바위, 바위), (보, 보)

 

 

 

순열 

- 서로 다른 n개의 원소 중 r (1<= r <= n)개를 중복하지 않고 선택하여 순서대로 나열했을때 경우의 수

순열의 예시

- 1, 2, 3, 4에서 서로다른 3개의 숫자를 나열해서 만들 수 있는 3자리 숫자의 개수

- A, B, C, D, E, F, G를 한 번씩만 이용해 만들 수 있는 단어의 총 가지수

 

순열의 성질

 

문제

- 0, 1, 2, 3, 4, 5, 6을 한번씩만 이용해서(중복 허락 x) 네 자리 정수를 만들면?

- 2가 천의 자리가 되는 경우의 수

- 짝수가 되는 경우의 수

 -> 0이 맨뒤에 오는 경우의 수 : 6 x 5 x 4 = 120

 -> 2가 맨뒤에 나오는 경우의 수 :  5 x 5 x 4 = 100

->  4가 맨뒤에 나오는 경우의 수 :  5 x 5 x 4 = 100

->  6가 맨뒤에 나오는 경우의 수 :  5 x 5 x 4 = 100

=> 420가지

 

 

 

 

중복 순열

- 서로 다른 n개의 원소 중 r개를 중복을 허용해서 선택한 후 나열 한 경우 경우의 수

 

 

예시

- 1, 2, 3, 4에서 3개의 숫자를 나열해 만들 수 있는 3자리 숫자의 개수

- A, B, C, D, E를 이용해 만들 수 있는 단어의 총 가ㅣ쑤

 

중복 집합의 순열

- n개의 원소중에서 p개, q개 .., r개가 같은 원소일때 n개를 순서대로 나열할 때 경우의 수

 

중복 집합의 순열 예시

- 만약 p = q = ... = r = 1인 경우 n개를 일열로 배열하는 경우의 수

 

- A, A, A, B, B, B, B, C, C, D를 일렬로 배열하는 경우의 수

 

 

아래의 그림에서 A에서 B까지 가는 경로 중 최단 경로의 개수는?

- x는 5회, y는 4회 -> 총 9회 이동

 

 

 

조합

1. 조합의 정의

2. 중복 조합

3. 조합의 응용

 

 

 

조합의 정의

- 조합 : 서로다른 n개의 원소 중 r(1<= r <= n)개를 중복없이 선택한 후, 순서에 상관없이 나열한 경우의 수

 

- 예시 : 1, 2, 3, 4에서 서로다른 3개의 숫자를 뽑는 방법의 수

 

 

조합의 성질

 

 

예시

- 남성 회원 13명, 여성 회원 10명 인 동아리에서 5명인 대표를 뽑을 때

- 성별 구분 없이 대표를 뽑는 경우->  23명중 5명

- 남성 3명, 여성 2명을 대표로 뽑는 경우 -> 남성 13명중 3명, 여성 10명중 2명

 

 

조합 2

- 서로 다른 n개의 원소를 p1, p2, ..., pk개의 원소를 가지는 k개의 그룹으로 나누는 방법의 수

- pi가 다 다른 경우

 

- pi가 모두 같을 때

 

-pi중 같은게 m1, m2, ...개가 있을 때

 

조합 2 예시

- 학생 수가 15명인 반에서

-> 5명, 4명, 3명, 2명, 1명으로 나누는 방법의 수

-> 5명, 5명, 5명으로 나누는 방법의 수

-> 4명, 4명, 2명, 2명, 1명으로 나누는 방법의 수

 

 

중복 조합

- 서로 다른 n개의 원소 중 r개를 중복을 허용하여 선택한 후 이를 순서에 상관없이 나열 할 떄 경우의 수

 

중복 조합 예시

- 1, 2, 3, 4에서 중복을 허락하여 3개의 숫자를 선택하는 방법의 수

 

- 1, 2, 3에서 중복을 허락해 5개의 숫자를 뽑는 경우의 수

 

이항 정리

 

 

이항 정리의 예시

- (a + b)^2

 

- (a + b)^3

 

 

집합의 분할

- 분할 : 집합 A를 부분집합 A1, A2 ... , Ak가 다음을 만족시키면 {A1, A2 ..., Ak}를 A의 분할이라고 함

 

 

- S(n, k) = 원소 개수가 n인 집합을 k개의 부분 집합으로 분할하는 방법의 수

- 인도 수학자 라마누잔은 분할의 성질에 대한 연구로 수학 발전에 킁 공헌을 함

 

 

예시 S(5,2) = ?

- 원소의 개수가 1개, 4개인 집합으로 분할하는 경우의 수

- 원소의 개수가 2개, 3개인 집합으로 분할하는 경우의 수

- S(5, 2)는?

 

 

 

 

 

 

 

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

이산 수학 - 19 확률 분포  (0) 2020.06.09
이산 수학 - 18 확률  (0) 2020.06.09
이산 수학 - 16 트리 활용  (0) 2020.06.08
이산 수학 - 15 트리  (0) 2020.06.08
이산 수학 - 14 그래프의 활용  (0) 2020.06.08
728x90

가계도, 조직도, 토너먼트 대진표 등 다양한 분야에 응용되는 트리

-> 트리 구조를 이용하여 새로운 분자구조식설계 가능

 

압축 저장 방법

1. 손실 압축 : 사람의 시각, 청각 능력이 구별하지 못하는 영역을 제거해 전체 파일 크기를 줄임

2. 무손실 압축 : 원래 정보를 그대로 보존하여 압축을 풀었을 때 원래의 파일로 되돌릴수 있는 방식(허프만 코드)

 

허프만 코드

- 무손실 압축에 쓰이는 알고리즘 일종

- 파일에 등작하는 문자의 빈도수에 따라 각 문자에 다른 길이의 부호를 대응 시켜서 파일을 압축

- 트리 구조는 바로 이러한 허프만 코드를 정의하는 알고리즘에 사용

 

 

이진 트리의 순회와 탐색

1. 이진트리의 순회

2. 이진 탐색 트리

 

순회 Traversal

- 트리에 있는 모든 노드를 (한 번씩) 방문하여 노드가 가지고 있는 데이터를 처리하는 체계적인 방법

- (이진) 트리의 계층적인 구조를 이용하여 순회하는 방법을 정의

- 이진 트리 순회의 규칙

 -> 루트 노드에서 시작

 -> 형제 노드 중 왼쪽 노드를 먼저 탐색

- 순회의 종류

 -> 전위 순회, 중위 순회, 후위 순회

 

전위 순회

- 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드 순서로 순회

- A -> B -> D -> E -> J -> K -> C -> F -> M

중위 순회

- 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 순회

- D -> B -> J ->E -> K -> A -> F -> M -> C

 

후위 순회

- 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드 순서로 순회

- D -> J  -> K -> E -> B ->  M -> F -> C -> A

 

 

이진 트리 순회를 이용한 폴더 용량 계산

 

 

전위 순회

- 0.2M(내컴퓨터) + 0.1 M(C:\) + 15M(내문서) + 2M(프로그램) + 200M(자바) + 100M(파이썬) + 0.3M(D:\) + 50M(그림) + 3M(음악) + 70M(팝송) + 90M(클래식) = 530.6M

 

중위 순회

- 내문서 + C\ + 자바 + 프로그램 + 파이썬 + 내커퓨터 + 그림 + DL\ + 팝송 + 음악 + 클래식 = 530.6M

 

후위 순회

- 내문서 + 자바 + 파이썬 + 프로그램 + C:\ + 그림 + 팝송 + 클래식 + 음악 + D:\ + 내컴퓨터 = 530.6M

 

 

이진 탐색 트리 Binary Search Tree

- 노드에 저장된 데이터의 내용에 대한 크기 기준을 정하고 이 기준에 따라 노드의 위치를 정해놓은 이진 트리

1. 모든 노드는 서로 다른 유일한 키를 갖는다.

2. 왼쪽 서브트리에 있는 모든 노드는 루트 노드 보다 작은 키를 갖는다.

3. 오른쪽 서브 트리에 있는 모든 노드는 루트 노드보다 큰 키를 가진다.

4. 왼쪽 서브 트리와 오른쪽 서브트리도 이진 탐색 트리다.

 

 

이진 탐색 트리에서 22를 검색하는 과정

1. 루트 노드는 15로 22보다 작다 -> 오른쪽 자식 노드

2. 21은 22보다 작다 -> 오른쪽 자식 노드

3. 24는 22보다 크다 ->왼쪽 자식노드

 

 

이진 탐색 트리의 삽입

 

이진 탐색 트리의 삭제 1

- 삭제 할 노드가 리프 노드인 경우

 

 

 

이진 탐색 트리의 삭제 2

- 삭제 할 노드가 1개의 자식 노드를 가지는 경우

- 21을 지우는 경우 노드 24를 21자리로 옮김

 

 

이진 탐색 트리의 삭제 3

- 삭제할 노드가 2개의 자식 노드를 가지는 경우

- 왼쪽 서브트리 노드 중 최대 값을 가지는 노드를 이동시키거나 오른쪽 서브트리의 노드 중 최소키를 가지는 노드를 이동

 

이진 탐색 트리 생성

- 18, 10, 25, 20, 14, 8, 23, 17, 29에 대한 이진 탐색 트리

 

생성 트리

1. 생성 트리의 개념

2. 프림 알고리즘

3. 크루스칼 알고리즘

 

 

생성 트리 Spanning Tree

- 그래프의 모든 노드를 포함하는 트리 -> 그래프의 생성 트리는 여러 개가 될 수 있음

그래프

위 그래프에서 아래의 생성 트리를 만들 수 있음

 

 생성 트리 예시

 

 

 

 

최소 생성 트리 Minimal Spanning Tree

- 가중 그래프에 대해서 연결선의 가중치의 합을 최소로 하는 생성 트리

- 네트워크나 도로망 설계 시 비용을 최소로 하거나 효율성을 최대로 하는 경로를 고려할 때 유용

- 최소 생성 트리를 구하는 알고리즘으로 프림 알고리즘, 크루스칼 알고리즘

 

 

프림 알고리즘

1. 임의의 시작 노드 선택

2. 가중치가 가장 작은 연결선을 선택

3. 1에서 선택된 연결선에 의해 연결된 노드와 연결된 모든 연결선 중 가중치가 가장 작은 연결선 선택. 가중치가 같은 연결선이 있으면 임의로 하나를 선택한다

4. 선택된 연결선에 의해 사이클이 형성되면 선택 하지 않는다.

5. 그래프에 포함된 노드 개수가 n일 때, n - 1개의 연결선이 선택되면 종료한다.

 

 

프림 알고리즘

- 노드 A에서 시작

 

 

 

 

크루스칼 알고리즘

1. 가중치가 가장 작은 연결선을 차례로 선택한다. 가중치가 같은 연결선은 모두 선택한다.

2. 선택된 연결선에 의해 사이클이 형성되면 선택하지 않는다.

3. 그래프에 포함된 노드의 개수가 n일 때, n - 1개의 연결선이 선택되면 종료한다.

 

 

크루스칼 알고리즘

- 노드 B에서 시작

 

 

 

아스키 코드

- 문자를 8비트 숫자로 변환하는 표

 

만약 자주 나오는 문자에 더 적은 비트를 할당한다면?

-> 전체 문자 비트 수를 줄일 수 있을텐대 -> 허프만 알고리즘

 

 

허프만 알고리즘

- 발생 빈도가 높은 문자는 적은 비트를 할당하고, 발생 빈도가 낮은 문자에 많은 비트를 할당하야 파일 크기를 줄이는 알고리즘

1. 발생 빈도가 가장 낮은 두 문자를 선택하여 하나의 이진 트리 생성

  -> 왼쪽 노드에 빈도 수가 낮은 문자, 오른쪽 노드에 빈도가 높은 문자

  -> 빈도수가 같으면 사전 순서로

  -> 두 문자의 빈도 합을 그 문자들의 부모 노드로

2. 1을 반복하여 하나의 이진 트리를 생성

3. 생성된 이진 트리의 왼쪽 노드에는 0, 오른쪽 노드에는 1을 부여

4. 루트 노드에서 해당 문자까지의 0 또는 1을 순서대로 나열

 

허프만 알고리즘 예시

1. 가장 빈도수가 낮은 o, z 선택

 - 사전의 순서대로 o를 왼쪽, z를 오른쪽 놓고

 - 두 빈도의 합인 4를 부모 노드로 설정

 

2. 가장 빈도수가 낮은 u(5)와 4

 - 4가 낮으므로 왼쪽 노드, u는 크므로 오른쪽노드

 - 합인 9가 부모 노드

 

3. 다음 가장 빈도수가 낮은 수가 8로 e, j가 존재

- 두 문자는 별도의 자식 노드가 되어

 - 두 수의 합인 16이 부모 노드가 됨

 

 

4. 가장 빈도수가 낮은 문자 b와 ozu

 - ozu가 9 낮으므로 왼쪽, b는 15라 크므로 오른쪽

 - 두 수의 합은 24가 부모 노드가 됨

 

 5. 다음 빈도수 낮은 문자는 ej와 s

 - ej는 16으로 왼쪽, s는 17로 우측

 - 두 수의 합인 33이 부모노드가 됨

6. 다음 빈도수가 낮은 문자 g와 ozub

 - g는 23 왼쪽, ozub는 24 오른쪽

 - 합한 수 47이 부모 노드

7. 다음 빈도수가 낮은 문자 i와 ejs

 - i가 30으로 왼쪽, ejs가 33으로 오른쪽

 - 두수의 합 63이 부모 노드

 

8. 나머지 두 문자 iejs, gozub

 - geozub가 47로 왼쪽, iejs가 63으로 오른쪽

 - 부모 노드는 110

 

허프만 알고리즘 정리

- g의 경우 가장 많이 사용됨 -> 00 비트

- o는 01000

=> 빈도수가 많을수록 비드 수가 짧음

 

 

bgebejlezusuo 의 허프만 코드와 아스키 코드 비교

1. 아스키 코드

00001010 01100010 01100111 01100101 01100010 01100101 01101010 01101100 01100101 01111010 01110101 01110011 01110101 01101111 00100000

 

2. 허프만 코드

01100110001111001101101100010010101111010101000

 

 

 

 

 

 

 

 

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

이산 수학 - 18 확률  (0) 2020.06.09
이산 수학 - 17 순열과 조합  (0) 2020.06.09
이산 수학 - 15 트리  (0) 2020.06.08
이산 수학 - 14 그래프의 활용  (0) 2020.06.08
이산 수학 - 13 그래프  (0) 2020.06.08
728x90

트리의 개념

1. 트리의 정의

2. 노드의 종류

3. 트리의 용어

 

 

 

트리의 정의

- 루트 노드를 가지고 있고, 모든 노드들 사이에 단순 경로가 존재하는 비순환 연결 그래프

- 루트 노드 : 나무의 뿌리에 해당하는, 트리에 가장 높은 곳에 위치하는 노드

- 경로 : 노드에서 노드로 가는, 중복되지 않은 연결선들의 나열

- 단순 경로 : 시작과 끝노드가 중복되는것을 제외하고 노드가 중복되지 않는 경로

- 사이클 : 시작 노드와 끝 노드가 같은 경로

- 비순환 그래프 : 사이클이 존재하지 않는 그래프 -> 트리에는 루프가 없음

- 연결 그래프 : 서로 다른 모든 노드들 사이에 항상 경로가 있는 그래프

 

 

부모 노드

- 한단계 상위 노드

- 노드 A는 노드 B, C, D의 부모 노드

- 노드 B는 노드 E, F의 부모 노드

- 노드 D는 노드 G의 부모 노드

 

 

자식 노드

- 한단계 하위 노드

- 노드 B, C, D는 노드 A의 자식 노드

- 노드 E, F는 노드 B의 자식 노드

- 노드 G는 노드 D의 자식 노드

 

 

형제 노드

- 부모가 같은 노드

- 노드 B, C, D는 서로 형제 노드

- 노드 E, F는 서로 형제 노드

 

 

 

리프 노드

- 자식 노드가 없는 노드

- 노드 C, E, F, G는 리프 노드

 

중간 노드

- 루프 노드나 리프 노드가 아닌 노드

- 노드 B와 D는 중간 노드

 

조상 노드

- 루트 노드에서 임의의 한 노드에 이르는 경로에 포함된 모든 노드들

- 노드 A, B, E는 노드 H의 조상 노드

- 노드 A는 노드 D의 조상 노드

- 부모 노드는 조상 노드

- 루트 노드를 제외한 모든 노드는 조상 노드를 가짐

 

자손 노드

- 한 노드에서 임의의 리프 노드에 이르는 경로에 포함된 모든 노드들

- 노드 A의 자손 노드는 노드 B, C, D, E, F, G, H

- 자식 노드는 자손 노드임

 

 

서브 트리

- 임의의 한 노드를 루트 노드로 하는 트리

- 서브 트리의 개수 = 노드 개수

 

 

노드의 차수

- 노드의 차수 = 자식 노드의 개수

- A 노드 차수 = 3

- B 노드 차수 = 2

- C 노드 차수 = 0

- 트리에서의 노드의 차수 != 그래프에서의 노드의 차수

 

트리의 차수

- 각 노드의 차수의 최대값

- A 노드의 차수 = 3

- B 노드의 차수 = 2

- C 노드의 차수

=> 트리의 차수 = 3

- 트리의 차수 != 그래프의 차수

 

레벨

- 루트 노드는 레벨 0

- 자식 노드로 가면서 레벨이 한 단계 씩 증가

 

 

트리의 높이(또는 깊이)

- 트리의 최대 레벨

 

 

트리의 성질

1. 노드의 개수와 연결선 개수의 관계

2. 트리에 대한 정리

 

노드의 개수와 연결선의 개수 사이의 관계

- 트리의 노드의 개수를 v, 연결선 개수를 e라 하면

=> e = v - 1

 

 

2. 트리에 대한 정리

- n 개의 노드를 가지는 연결 그래프 T에 대해 다음은 동치임

- T는 트리이다.

- T의 연결선의 개수는 n - 1 이다.

- T에서 연결선을 하나 제거하면 단절 그래프가 된다.

- T의 임의의 한 노드에서 그 노드와 다른 노드로 가는 경로가 유일하게 존재한다.

 

 

 

 

이진 트리

1. 이진 트리의 정의

2. 이진 트리의 종류

3. 이진 트리의 표현

 

 

 

이진 트리 Binary Tree

- 차수가 2이하(자식 노드가 2개 이하)인 트리

 

 

이진 트리에 관한 정리

- 레벨 k에서 이진 트리가 가질 수 있는 최대 노드 수 = 2^k

- 높이가 m인 이진 트리가 가질수 있는 최대 노드 수 = 2^(m + 1) - 1

- 높이가 m인 이진 트리가 가질 수 있는 최소 노드 수 = m + 1

 

포화 이진 트리

- 모든 레벨에 노드가 꽉 차서 레벨을 늘이지 않는 이상 노드 추가가 더이상 불가능한 트리

- 높이가 h인 포화 이진 트리의 노드 수 = 2^(h + 1) -1

- 높이가 h인 포화 이진 트리의 리프 노드 수 = 2^h

 

 

 

완전 이진 트리

- 높이가 h일 때, 레벨 0 부터 레벨 h - 1까지의 노드로 이루어진 트리가 포화 이진 트리이고, 레벨 h에서는 왼쪽부터 노드가 채워진 트리

- 2^h <= 높이가 h인 완전 이진 트리의 노드 수 <= 2^(h + 1) - 1

 

편향 이진 트리 skwed binary tree

- 리프 노드를 제외한 모든 노드들이 왼쪽 자식 노드만을 가지고 있거나 아니면 모두 오른쪽 자식 노드만 가지고 있는 트리

- 높이가 h인 편향 이진 트리의 노드 수 = h + 1

 

배열을 이용한 구현

- 배열 : 같은 자료형을 가진 자료들을 메모리에 연속적으로 저장한 자료 구조

-> 인덱스(index)를 이용하여 저장된 자료에 접근 가능

 

 

배열을 이용한 이진 트리 구현

- 트리의 높이가 h면, 높 이가 h인 포화 이진 트리의 노드 번호를 배열의 인덱스로 사용하여 트리 표현

-> 인덱스 계산 편의성을 위해 루트 노드의 경우 인덱스 1을 사용

 

배열을 이용한 이진 트린 구현시 포화 이진 트리를 사용하는 경우의 장점

- 부모 노드의 인덱스가 n이면, 왼쪽 자식 노드의 인덱스는 2n, 오른쪽 자식 노드의 인덱스는 2n + 1

- 자식 노드의 인덱스가 이면 부모 노드의 인덱스 내림 (n/2) -> 내림(1.5) = 1, 내림(2.5) = 2

 

포화 이진 트리를 사용한 경우 단점

- 메모리 낭비가 발생

 

 

 

연결 리스트

- 데이터를 저장할때 다음 순서의 자료가 있는 위치(포인터)를 데이터에 포함시키는 방식으로 저장

 

연결 리스트를 이용한 구현

- 트리에서는 부모 노드와 자식 노드라는 관계가 존재

- 이를 위해 이중 연결 리스트를 사용

- 부모 노드를 나타내는 데이터에 자식 노드의 위치를 함께 저장

 

 

연결 리스트를 이용한 이진 트리 예시

 

 

 

 

300x250

'수학 > 알고리즘' 카테고리의 다른 글

이산 수학 - 17 순열과 조합  (0) 2020.06.09
이산 수학 - 16 트리 활용  (0) 2020.06.08
이산 수학 - 14 그래프의 활용  (0) 2020.06.08
이산 수학 - 13 그래프  (0) 2020.06.08
이산 수학 - 10 관계  (0) 2020.06.07

+ Recent posts