336x280(권장), 300x250(권장), 250x250, 200x200 크기의 광고 코드만 넣을 수 있습니다.
저번에 포스팅한 최대 공약수 찾는 알고리즘은 큰 문제점이 하나 있습니다.
만약 50000과 1의 최대공약수를 구하기 위해서는 무려 50000번의 연산을 해야하기 때문입니다.
그런데 저번 포스팅에 사용한 예시 get_gcd(110.33)에서 뺄셈을 모두 끝내면 (11,33) 이 되는건 다 알 고 계실겁니다. 여기서 자세히 살펴보면 110을 33으로 나누고 나머지가 11이 나온다는걸 발견할 수 있습니다. 즉 11=110%33으로 대체가능하며 이 방법으로 많은 뺄셈 연산을 나머지 연산으로 대체가능합니다.
그렇다면 이번에는 함수를 이렇게 짜봅시다.
GCD(a,b)=(a%b,b)
이렇게 불필요한 연산을 삭제함으로써 프로그램을 좀더 능률적이게 만들수 있습니다.
아래 프로그램은 이를 이용한 프로그램입니다.
오타 & 지적 환영합니다.
//프로그램 짜다 &와 % 오타내서 몇분 보낸거는 안비밀
'IT > 알고리즘' 카테고리의 다른 글
| [알고리즘 자료구조] 연결 리스트 (Linked List) 2. 단순 연결 리스트(Simple Linked List)의 기본 뼈대 (0) | 2012.04.26 |
|---|---|
| [알고리즘 자료구조] 연결 리스트 (Linked List) 1. 연결 리스트란? (0) | 2012.04.26 |
| 입력된 정수를 반대로 출력하는 프로그램 (0) | 2012.04.26 |
| 최대 공약수 찾는 알고리즘(유클리드의 알고리즘(Euclid's algorithm)) (2) | 2012.04.26 |
| 홀수 짝수 구하는 알고리즘 (0) | 2012.04.26 |
