이산 수학 - 20 알고리즘

 

 

알고리즘

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

 

 

알고리즘의 이해

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개의 원소를 비교해 기준에 따라 순서를 바꾸는 방식의 정려 알고리즘