1. Introduction

 

• 알고리즘의 필요성
  • 실용적 이유(Practical reasons)
  • 이론적 이유(Theoretical reasons)

 

---

 

• 알고리즘이란 무엇인가

 

---

 

• 간단한 알고리즘 문제: the greatest common divisor 
  • Find thr greatest commom divisor (최대공약수) of two nonnegative, not both zero integers m and n
  • Examples: gcd(60, 24) = 12, gcd(60, 0) = 60
  • 세 가지 해결 방식 있음: Euclid's Algorithm, Consecutive integer checking Algorithm,  Middle-school procedure

 

• Euclid's Algorithm
  • 가장 기본 베이스:  gcd(m, n) = gcd(n, m mod n), gcd(m, 0) = m
  • Example: gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12
  • (아주 간단하게만..) 이유? 두 양의 정수 a, b가 있다고 할 때, a, b (a>b) 의 gcd를 n이라고 한다면 a=na', b=nb' 로 표현가능. 그렇다면 a-b=n(a'-b')이므로 a와 b, a-b의 gcd는 같음. mod는 -를 여러 번 한 것과 같으므로.. 
  • 자연어                       
  • pseudo code                                                         

 

• Consecutive integer checking Algorithm
  • 자연어                 
  • 두 수가 양수인지 확인 먼저 해야됨 (0으로는 나눌 수 없기 때문)
  • t 의 시작 값: min(m, n) -> t = t - 1 -> t의 한계 값: 1

 

• Middle-school procedure
  • 자연어 
  • 이 과정은 알고리즘이라고 할 수 없음!