안녕하세요 부산 멤버십 21기 박현우라고 합니다.^^
태어나서 첫 포스팅이라, 긴장도 되고 설레기도 하는데요.
처음이니까 제가 좀 부족하더라도, 넓은 아량(?)으로 이쁘게 봐주시길바랍니다^^
| 1. 알고리즘의 정의 |
| 2. 알고리즘과 자료 구조 |
| 3. 알고리즘 선택의 문제 |
| 4. 경험적 분석과 수학적 분석 |
| 5. 최악의 경우, 최선의 경우, 평균의 경우 |
| 6. O-표기법 |
| 7. 시간소요량과 공간소요량 |
알고리즘이란? 알고리즘의 정의는 다음과 같습니다.
- 주어진 문제를 해결하기 위한 잘 정의된 동작들의 유한 집합 -
위의 정의에서 보듯이 알고리즘에는 우선 주어지는 문제가 있고, 이 문제를 해결하기 위한 순서적인 동작들이 있습니다. 이 동작을 이루기 위해서는 자료 구조를 필요로 하게 됩니다.
먼저, 알고리즘을 개발할 때 선행되어야 할것 중에 하나는 주어진 문제를 잘 이해하는 것입니다. 주어지는 문제는 문제 자체만이 아니라, 문제가 주어지는 상황도 포함이 되기때문에, 문제를 해결하는데 이용할 수 있는 자원들을 포함하고 있고, 이러한 문제를 잘 이해하고 나서 알고리즘을 생각하는 것이 좋습니다.
알고리즘을 적절히 한글로 표현해본다면 '방법(?)'이라고도 할 수 있습니다. 간단히 예를 들어서, 만약에 의자를 만들어야 하는 문제가 있다고 합시다. 의자에는 철 의자도 있고, 나무 의자도 있습니다. 만약 철 의자를 만들어야 한다면 그것은 나무 의자를 만드는 방법과는 매우 다를 것입니다. 비록 형태적으로는 비슷한 모양의 의자일지라도, 철 의자는 철을 가지고 절단하고 용접하는 과정이 필요할 것이고, 나무 의자의 경우에는 목재를 가지고 자르고 못질하는 과정이 필요할 것입니다. 이러한 나무 의자를 만들것인가, 철 의자를 만들 것인가 하는 것은 문제를 잘 이해하고 있다고 볼 수 있습니다. 문제를 잘못 이해한다면 방법을 잘못 선택할 수도 있다는 것입니다.
그렇다면, 알고리즘과 자료구조의 관계는 어떠할까요? 그것은 마치 계란의 노른자와 흰자와도 같다고 할 수 있습니다. 계란은 껍질 속에 한정된 양만의 노른자와 흰자가 있을 수 있습니다. 그래서 만일 노른자가 커진다면 흰자는 줄어야 하고, 노른자가 작아진다면 흰자가 커져야 하는 것입니다. 마찬가지로 자료 구조가 잘 조직화되어 복잡한 구조라면 알고리즘은 간단하게 할 수 있고, 자료구조가 단순한 구조이면 알고리즘은 복잡해 진다고 할 수 있습니다.
다음은, 어떠한 알고리즘을 선택해야 올바른 선택을 했다고 할 수 있는가에 대해서 생각해봅시다. 하나의 문제에 대해 그 해결 방법은 여러가지일 수 있습니다. 예를 들어, 정렬을 위한 알고리즘의 경우, Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Radix Sort, Merge Sort 등등 수많은 종류의 알고리즘들이 개발되어 있습니다. 이러한 알고리즘들 중 어떠한 것을 택해야 할까요?? 먼저 알아두어야 할 것은 절대적으로 최상의 알고리즘은 없다라는 것입니다. 즉, 어떤 상황에서도 가장 잘 맞는 알고리즘은 존재하지 않고, 항상 주어진 문제의 상황과 제한점이 주어질 때에만 최상의 알고리즘을 선택할 수 있다는 것입니다.
또한, 알고리즘의 속도와 메모리 소요의 관계도 이해하는 것이 좋습니다. 정렬 알고리즘의 경우 가장 빠른 것은 Quick Sort이지만, Quick Sort는 재귀 호출이나 스택에 필요한 정보를 저장하는 방식으로 자료의 저장에 소요되는 메모리 외에도 부가적인 메모리가 필요하게 됩니다. 즉, 속도를 위해서 메모리를 희생하는 것인데, Selection Sort의 경우, 속도는 Quick Sort에 비해서 느리지만 추가적인 메모리가 필요하지 않습니다. 단순히 자료의 저장에 소요되는 메모리만 있으면 되기 때문입니다. 이렇게 알고리즘을 선택하는 데는 확정된 기준이 없기 때문에 많은 알고리즘을 알고 있는 사람은 항상 선택에 고민을 하게됩니다. 이 고민의 해결방법은 바로 여러분들이 알고리즘을 충분히 이해하는 방법밖에 없습니다...(;;)
너무 난해한 방법일 수도 있지만, 알고리즘을 충분히 이해하고 주어진 상황에 가장 적합한 알고리즘을 쉽게 찾아내어 문제 해결에 도움이 될 수 있을 것입니다.
다음은 알고리즘의 경험적 분석과 수학적 분석에 대해 알아보겠습니다. 경험적 분석이라 함은 흔히들 쉽게 알고리즘을 프로그래밍 언어로 구현을 한 뒤에 이를 실행시켜 보아 실행시간을 비교하는 것입니다. 저희들이 가장 많이 쓰는 방법 중에 하나죠. 이것은 쉽게 납득할만한 신빙성 있는 자료를 제공하며 수학적인 지식이 필요없다는 장점이 있습니다. 수학적 분석은 알고리즘을 프로그래밍 언어로 구현하지 않고, 단지 알고리즘 자체만을 가지고 수학적 분석을 하는 것입니다. 수학적 분석의 경우 알고리즘을 프로그래밍하는 과정이 없기 때문에 프로그래밍하는 과정에서 같은 알고리즘이더라도 프로그래머의 능력에 따라 나타날 수 있는 성능의 편차를 없앨 수 있다는 장점이 있습니다. 각자 분석의 장점을 이용해, 프로그래밍에 적절히 이용한다면, 최적의 알고리즘을 찾을 수 있는 발판이 되지 않을까 생각해 봅니다.
알고리즘의 경우 보통 O-표기법을 이용한 최악의 경우, 최선의 경우, 평균의 경우를 나눠 볼 수 있는데요, 최악의 경우는 알고리즘의 성능을 표현하는데 많이 사용이 됩니다. 최악의 경우는 아무리 시간이 오래 걸린다고 해도 최악의 경우는 넘지 않는 다는 것을 보장합니다. 평균적 경우도 알고리즘의 성능을 표현하는데 사용이 가능합니다. 하지만, 평균적인 경우를 사용하는 데에는 몇가지 문제점이 존재합니다. 첫째, 평균적인 경우라는 자체가 수학적으로 매우 어려운 개념이어서 확정짓기가 굉장히 힘이듭니다. 둘째, 평균적인 경우가 실제의 상황과 같지는 않다는 점입니다. 치명적이죠. 이 점은 착각하기 쉬운 점으로 평균적인 경우가 실제로 많이 입력되는 빈도를 따지는 것이 아니라, 확률적으로 가장 고르게 분포되는 경우를 의미하기 때문입니다. 따라서 실제로 많이 입력되는 자료와 평균적인 자료는 같은 개념이 아니라고 할 수 있겠네요.. 여하튼 알고리즘의 성능을 나타내는 데에는 최악의 경우에 한해서 나타내는 것이 보통이며 실제로 알고리즘은 최악의 경우보다 빠른 속도로 실행되게 됩니다
다음은 O-표기법에 대해서 알아보겠습니다.
O-표기법에 대한 정의는 다음과 같습니다.
만약에 실행 시간 함수 T(N)이 N0보다 큰 N에 대하여 항상 C0f(N)보다 작거나 같은 C0와 N0가 존재한다면 T(N)은 O(f(N))이라고 한다. 즉 N>=N0인 모든 N에 대하여 T(N)<=C0f(N)이 만족하면 T(N)=O(f(N))이다.
실제의 실행 시간 함수 T(N)이 갖는 상수는 프로그래머의 능력에 따라 달라질 수 있는 것이기 때문에 순수한 알고리즘의 성능 표시를 위해서는 이 상수의 요소가 없어져야 합니다. 상수의 요소를 없앤 입력 자료수 N에 따른 실행 시간의 추이만을 나타낸 것이 바로 O-표기법입니다. 그리고 O-표기법은 정의상 알고리즘 실행 시간의 최악의 경우를 나타냅니다. 결론적으로, O-표기법은 최악의 경우라도 넘지않는 실행 시간의 함수이기 때문에 실제 입력되는 일반 자료에 대한 실행 시간보다는 훨씬 큰 값을 가집니다. 일반적인 경우에는 매우 뛰어난 속도를 보이지만 최악의 경우에만 극도로 성능이 좋지 않은 알고리즘의 경우 O-표기법은 과장되게 성능이 나쁜 것으로 판단되기도 합니다. O-표기법 말고도 성능을 표기하는 방법은 Ω(오메가)표기법도 존재합니다.
지금까지 알고리즘의 성능을 말할 때 시간을 얼마나 잡아먹느냐만 따져왔네요.. 이렇게 어떤 알고리즘이 얼마만큼의 시간을 필요로 하는가를 시간 소요량(Time Complexity)라고 합니다. 반면에 알고리즘의 수행을 위해서 얼마만큼의 공간을 필요로 하는지는 중요한 점입니다. 이렇게 알고리즘이 얼마만큼의 공간을 필요로 하는가를 공간 소요량(Space Complexity)이라고 합니다. 이 시간 소요량과 공간 소요량 둘다 알고리즘의 성능을 나타내기 위해서는 필수적인 자료가 됩니다. 물론 표기법을 이용해서 나타내어질 수도 있습니다.
이렇게 간단하게 알고리즘의 대략적인 개요에 대해서 알아보았는데요.. 여기까지 읽어주시느라 수고하셨습니다^^ 아직 부족하지만, 공부를 계속하고 노력해서 좀 더 퀄리티있는 포스팅을 하도록 하겠습니다 감사합니다.
안녕하세요 부산 멤버십 21-2기 김은진 입니다.
Data Structure & Algorithm 시그에 참여하고 있으며, 이번에 유클리드 알고리즘과 소수구하는 알고리즘을 주제로 포스팅하게 되었습니다.
유클리드 알고리즘에 관하여 다음의 순서로 진행하도록 하겠습니다.
| 1. 최대공약수란? |
| 2. 유클리드 알고리즘 |
| 3. C로 풀어본 유클리드 알고리즘 |
| 4. 유클리드 알고리즘의 개선 |
1. 최대공약수란?
최대공약수란
두수의 약수를 구했을 때, 공통인 수중 가장 큰 수를 말합니다.
예를 들어, 280과 30의 공약수를 구한다고 했을 때,
---------------------------------------------------------------
280의 약수 : 1, 2, 4, 5, 7, 8, 10, 14, 20, 28, 40, 56, 70, 140, 280
30의 약수 : 1, 2, 3, 5, 6, 10, 15, 30
---------------------------------------------------------------
위와 같이 노란색으로 친한 1,2,5,10 이 280과 30의 공통된 약수 즉 공약수이며
그 중 가장 큰 수인 10 이 두 숫자의 최대공약수가 되는 것입니다.
수학 교과서에서 최대공약수를 구할 때에는 소인수 분해를 이용하여 구합니다.
공통으로 나누어 떨어지는 수가 1 외에 없을 때까지 소인수 분해한 뒤 좌변의 수들을 모두 곱하면 최대공약수가 되는 것입니다.
손으로 풀기엔 가장 좋은 알고리즘이지만 공통되는 인수를 구하는 작업과 그것을 나누는 작업이 컴퓨터에게는
힘든 작업이기 때문에 컴퓨터로 구현하기엔 무리가 있습니다.
그렇다면 유클리드의 최대공약수를 구하는 알고리즘은 어떤 것인지 알아봅시다.
2. 유클리드 알고리즘
유클리드 알고리즘은 최대공약수의 성질을 이용하여 뺄셈과 두 값의 교환이라는 기본적인 동작으로만 최대공약수를 구할 수 있습니다.
우선, 최대공약수의 성질을 알아보도록 하겠습니다.
A와 B라는 정수가 있다고 했을 때, 이 A와 B는 최대공약수로써 G를 갖는다고 한다면 A와 B는 다음과 같이 표현 할 수 있습니다.
괄호안의 숫자는 위에서 사용한 280과 30으로 예를 든 것입니다. 소문자로 쓴 a와 b는 각 A와 B에서 G외의 인수들을 모두 곱한 값을 의미하고 a와 b는 서로소(공통되는 약수가 1밖에 없는 경우)입니다.
그렇다면 A-B와 B의 최대공약수는 얼마일까요
(a-b)와 b 역시 서로소이므로
A-B와 B의 최대공약수도 역시 G입니다.
즉, 쉽게 말해 아래 식과 같이 GCD(u,v)라는 함수가 있어 이것이 u와 v의 최대공약수를 구하는 기능을 한다고 할 때 이런 성질을 가지게 됩니다.
식1[GCD(Greatest Common Divisor)는 최대공약수를 뜻합니다.]
식2 최대공약수는 정수의 순서에 관계없으므로 다음과 같은 식도 성립 합니다.
식3 0이 아닌 u라는 수와 0의 최대공약수는 얼마일까요? 0은 어떤 수와 곱해도 0이기 때문에 0의
약수는 정의상 모든 정수가 됩니다(0=u*0), 그래서 다음 식이 성립합니다.
이해가 잘 안되신다면 실제로 숫자를 대입해 보시면 식이 성립한다는 것을 알게 되실겁니다^^
식 1,2,3을 바탕으로 해서 280과 30의 최대공약수는 다음과 같이 구할 수 있습니다.
맨 첫번재 줄부터 식 1에 대입한 방식입니다
두번째 파란색 줄부터 식 2를 이용한 방식이며, 마지막줄이 식 3을 이용한 방식입니다.
매우 긴 과정이지만 컴퓨터는 이런 것을 더 좋아합니다. 사용된 동작이라고는 정수의 뺄셈, 정수의 교환, 그리고 정수가 0인지 확인하는 것 밖에 없기 때문이죠.
이상의 유클리드이 알고리즘을 말로 표현하면 다음과 같습니다
1. 두 정수 u와 v를 입력 받는다.
2. v가 u보다 크다면 v와 u의 값을 교환한다.
3. u에다 u-v의 값을 저장한다.
4. u가 0인가? 아니면 2번으로 돌아간다.
0이면 v가 최대공약수이다.
3. C로 풀어본 유클리드 알고리즘
책에서 제시된 위의 get_gcd함수를 main을 포함한 '두 정수의 최대공약수를 출력하는 프로그램' 을 작성해 봅시다.
4. 유클리드 알고리즘의 개선
유클리드 알고리즘은 입력되는 두수의 차이가 클 때 실행시간이 오래 걸립니다. 위에서 보신바와 같이 250과 30의 경우 뺄셈을 하여 10과 30으로 만드는 데 무려 9번이나 뺄셈을 합니다. 만약에 32767과 1의 최대공약수를 구하는 경우는 무려 32767번이나 뺄셈을 하게 되는 것입니다. 해서 좀 더 효율적이고 경제적인 개선 방안이 필요합니다.
250과 30을 뺄셈하여 만든 결과 10과 30을 자세히 살펴보면 10은 250을 30으로 나눈 뒤의 나머지임을 알수 있습니다. 즉, 10 ==250 % 30 인 것입니다. 이런 식으로 나머지 연산을 이요하면 9번의 뺄셈 대신에 한번의 % 연산으로 대체할 수 있다. 그래서 다음과 같이 식 4가 성립합니다.
식 4
정말 간단해 졌죠?
a % b == c일 때 c 는 항상 b보다 작은 성질이 있습니다. 즉 나머지는 젯수(나누는 수)보다 작다는 것인데 이를 이용하면 뺄셈을 이용할 경우 항상 u와 v의 대소 비교를 했던 것과는 반대로 %연산을 이용하면 대소가 분명해져서 % 연산 후 무조건 두 값을 교환하면 되므로 if(u<v)..와 같은 문장을 없앨수 있습니다.
다음은 나머지 연산을 이요하여 최대 공약수를 구하는 방법입니다.
1. 임의의 두 정수 u와 v를 입력받는다.
2. v가 0인가? 0이면 u가 최대공약수이다. 끝.
2.2 u와 v의 값을 교환한다.
3. 2로 돌아간다.
위와 같은 알고리즘을 c로 표한한 것입니다.
두 정수의 입력시 u가 v보다 커지도록 조정하지 않아도 자연스럽게 두 값이 교환되기때문에 그와 같은 조건은 필요없습니다.
이상으로 유클리드 알고리즘에 대해 알아보았습니다.
다음으로는 소수를 구하는 알고리즘에 대해 포스팅 해보도록 하겠습니다.
소수를 구하는 알고리즘에 대해 다음과 같은 순서로 진행하도록 하겠습니다.
| 1. 소수란? |
| 2. 소수를 구하는 알고리즘 |
| 3. 알고리즘의 개선 |
| 4. 에라토스테네스의 체 |
1. 소수란?
소수를 구하는 알고리즘에 대해 알아보기 전에 소수가 무엇인지부터 기억을 대뇌어 봅시다.
소수의 정의는
" 1과 자기자신 외에는 나누어 떨어지는 정수가 없는 양의 정수 "
입니다. 이것을 만족하는 수는 예를 들어 2, 3, 5, 6, 11, 13, 17, 19 같은 숫자가 되겠죠
참고로, 소수의 반대가 되는 수는 바로 [합성수]입니다. 또한, 1은 소수도 합성수도 아닌 바탕수(기초수)이죠.
만약 어떤 수 N이 주어졌을 때, 이 ,N이 소수인지 아닌지를 판별하는 프로그램을 한번 짜보라는 문제를 받았다고 합시다. 우선 가장 먼저 떠오르는 알고리즘은, 위의 정의대로 주어진 N을 2부터 N-1까지의 정소로 나누어 보아서
만약 나누어 떠어지는 수가 있으면 소수가 아니고,
나누어 떨어지는 수가 없으면 N은 소수가 되겠지요
양의 정수 A와 B가 있을 때 A가 B로 나누어 떨어지는 지는 A%B 연산의 결과를 확인하면 됩니다.
위의 방법을 알고리즘으로 표현해봅시다.
2. 소수를 구하는 알고리즘
1. 정수 N을 입력받는다.
2. 정수 i에 2를 대입한다.
2.1 N이 i로 한번에 딱 나누어 떨어지는가?
2.1.1 나누어 떨어지면 소수가 아니다. 프로그램 종료.
2.2 i를 하나 증가시킨다
2.3 i가 N보다 작은가?
2.3.1 작으면 2.1로 돌아간다.
3. 정수 N은 소수다. 프로그램 종료.
[ 리턴값중 1은 TRUE, 0은 !TRUE 으로 define 합니다. ]
main() 함수를 포함하여 위의 함수가 잘 작동하는 지 한번 실행시켜 봅시다.
결과화면입니다.
마지막 printf 문을 보면 is_prime(n) ? "" : "not" 이라고 되어있습니다
결과가 TRUE 이면 형식문의 %s 에는 "" 이 대응되어서 아무것도 출력되지 않고,
!TRUE(TRUE가 아니면) 이면 %s에는 "not"이 대응 되어서 소수가 아니라는 메시지가 출력됩니다.
3. 알고리즘의 개선
위의 알고리즘도 개선의 여지가 있습니다. 방법자체를 개선하는 것이 아니고, 소수 판별을 위해 N에 나누는 i의 범위를 좁혀보자는 것입니다.
13이라는 숫자를 예로 들어봅시다 13이라는 숫자가 소수인지 아닌지를 판별하기 위해 굳이 2부터 12까지의 숫자로 나누어 볼 필요가 있을까요? 잘 생각해보면 2부터 13의 제곱근까지의 정수로만 나누어도 된다는 것을 알 수 있을 것입니다.
12라는 숫자를 예로 들어본다면 12는 2*6, 3*4, 4*3, 6*2 라는 조합이 생깁니다.
여기서 앞쪽의 두 조합과 뒷쪽의 두 조합은 서로 대칭되는 모양임을 알수 있습니다 그래서 아까 13이라는 숫자는 13의 제곱근까지만 나누어 보면 되는 것이죠.
이 사실을 이용하여 주어진 N에 대해 2부터 sqrt(N)까지의 숫자로만 나누어서 소수를 판별하는 함수를 만들어보겠습니다.
[ sqrt() 는 제곱근 함수입니다 ]
[ 이 함수를 이용하려면 include 선언으로 math.h 를 추가로 해주어야합니다 ]
앞에서 만든 함수와 다른 점이 있다면 for 반복문이 sqrn(==sqrt(n))까지라는 것뿐입니다...
검사하는 수가 훨씬 줄었기 때문에 실행속도는 보다 빨라질 것 같지만, 항상 그렇지는 않습니다.
왜냐하면 sqrt()라는 함수는 실수형만 받는 수학함수이기 때문입니다.
4. 에라토스테네스의 체
소수를 구하는 알고리즘인 에리토스테네스의 체에 대해서 알아보도록 하겠습니다.
에라토스테네스의 체는 매우 간단한 알고리즘입니다 간단한 예로 30까지의 소수를 모두 구해보겠습니다.
2~30까지의 수 중
2를 제외한 모든 2의 배수들을 지웁니다.
이와 같은 방법으로 소수를 구하는 것입니다.
이러한 알고리즘의 구조를 알아보겠습니다.
1. 정수 N을 입력받는다. ( N까지의 소수를 구함) ( 위에선, 30으로 예를들었었죠 )
2. 정수 N만큼의 배열 array[N] 을 확보한다.
3. array[N]을 초기화시킨다. ( 당연히 모든 요소를 일단 0으로 )
4. for ( i=2; i<N; i++ )
4.1 만약 array[i] != 0 이면 ( 즉 소수가 아니라서 지워진 수라면) 네번째줄로 돌아간다.
4.2 ( j=i+i; j<=N; j+=i ) ← j는 i의 배수 라고 해석되죠
4.3 array[i]에 1을 대입 ( 즉 소수가 아니라서 지움 )
5. for ( i=2; i<=N; i++ )
5.1 array[i]==0인 i를 출력 ( i는 소수 )
이 구조로 999까지의 소수를 알아보는 프로그램을 만들어 봅시다.
결과입니다.
자 이렇게 에라토스테네스의 체까지 소수를 구하는 알고리즘에 대해서 알아보았습니다.
저는 책만 보고는 이해가 안되는 부분도 있어 다른 회원분들께 물어보기도 하고 검색도 하면서 공부가 많이 된 것 같습니다. 이 글을 보시는 회원 분들에게도 조금이나마 도움이 되는 포스팅이었으면 좋겠습니다.^^
앞으로도 Data Structure & Algorithm 시그와 블로그 운영이 날로 발전하도록 노력하겠습니다.
'IT 놀이터 > IT Storehouse' 카테고리의 다른 글
| [PhysX] 1부 PhysX 입문! (0) | 2011/10/15 |
|---|---|
| Android ADK란? (3) | 2011/10/15 |
| [Data Structure & Algorithm] 알고리즘이란 무엇인가? (0) | 2011/10/14 |
| [Android System 분석] 01. 안드로이드란? (1) | 2011/10/08 |
| OpenGL로 만드는 2D 비행슈팅 게임. (1) | 2011/10/08 |
| 루비 프로그래밍 언어 시작하기 (2) | 2011/10/08 |
