[컴퓨터알고리즘] Ch 2. 알고리즘을 배우기 위한 준비

PDF 정리본 (출력 가능)

[컴퓨터알고리즘] Ch 2. 알고리즘을 배우기 위한 준비.pdf

0.05MB

 

---

 

 

2.1 알고리즘이란

 

- 알고리즘이란

 

  : 문제를 해결하는 단계적 절차 또는 방법

  : 컴퓨터를 이용해 해결할 수 있어야 함.

  : 입력이 주어지고, 수행 결과인 해(답)을 출력.

 

 

- 알고리즘의 일반적 특성

 

정확성	주어진 입력에 대해 올바른 해를 주어야 함. (랜덤 알고리즘은 예외)
수행성	알고리즘의 각 단계는 컴퓨터에서 수행 가능해야 함.
유한성	알고리즘은 유한 시간 내에 종료되어야 함.
효율성	알고리즘은 효율적일수록 그 가치가 높아짐.
일반성	같은 type의 문제에 항상 해당 알고리즘을 적용할 수 있어야 함.
확정성	알고리즘은 동일한 입력에 대해 동일한 출력을 가져야 함.

 

 

2.2 최초의 알고리즘

 

- 유클리드의 최대공약수 알고리즘

 

  : 기원전 300년경에 만들어진 가장 오래된 알고리즘

  : 최대공약수란 2개의 자연수의 공약수들 중에서 가장 큰 수

 

 

- 2개의 자연수의 최대공약수는 큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수와 같다.

 

 

- 유클리드의 최대공약수 알고리즘에서 뺄셈 대신 나눗셈을 사용하면 빠르게 해를 찾는다.

Alg EuclidRecur(a, b) 1. if b == 0 return a 2. return EuclidRecur(b, a mod b)

 

 

- 재귀 호출 대신 반복문을 이용하면 더 빠르게 해를 찾는다.

Alg EuclidIter(a, b) input integer a, b (a >= b) output integer gcd 1. gcd <- 1 2. for i <- 1 to b     if(a % i == 0 && b % i == 0)         gcd <- i 3. return gcd

 

 

- 반복문을 수정하면 더욱 효율적인 알고리즘이 된다.

Alg EuclidIterDown(a, b) input integer a, b (a >= b) output integer gcd 1. gcd <- 1 2. for i <- b down to 1      if(a % i == 0 && b % i == 0)         return i

 

 

2.3 알고리즘의 표현 방법

 

- 일반적으로 알고리즘은 의사 코드(pseudo code)로 표현

 

 

- 알고리즘의 각 단계는 보통 말로 서술할 수 있으며, 컴퓨터 프로그래밍 언어로만 표현할 필요는 없음.

 

 

- 표현 가능한 방식

 

  : 보통 말로 표현

  : 의사 코드로 표현

  : 플로우 차트

 

이후 생략

시간 복잡도 등등.. 자료구조와 동일