사진을 클릭하면 PDF 정리본 다운로드 링크로 이어집니다.
알고리즘이란
문제를 해결하는 단계적 절차 또는 방법
컴퓨터를 이용해 해결할 수 있어야 함.
입력이 주어지고, 수행 결과인 해(답)을 출력.
특성 | 설명 |
---|---|
정확성 | 주어진 입력에 대해 올바른 해를 주어야 함. (랜덤 알고리즘은 예외) |
수행성 | 알고리즘의 각 단계는 컴퓨터에서 수행 가능해야 함. |
유한성 | 알고리즘은 유한 시간 내에 종료되어야 함. |
효율성 | 알고리즘은 효율적일수록 그 가치가 높아짐. |
일반성 | 같은 type의 문제에 항상 해당 알고리즘을 적용할 수 있어야 함. |
확정성 | 알고리즘은 동일한 입력에 대해 동일한 출력을 가져야 함. |
최대공약수 알고리즘
큰 수에서 작은 수를 뺀 수와 작은 수와의 최대공약수
와 같다.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
의사 코드(pseudo code)
로 표현시간 복잡도 등등.. 자료구조와 동일