0x00.알고리즘

알고리즘

 

 

알고리즘이란 어떤 문제를 해결하기 위한 절차를 기술해 놓은 것이다.

(여기서의 절차는 어떤 작동을 어떤 순서로 할 것인가를 나열한 것을 말함)

 

 

알고리즘의 특성으로는 다음과 같이 4가지가 있는데, 모두 충족을 시켜야 한다!

1. 엄밀성(Preciseness)

      기술된 내용은 한 가지 이상의 의미를 포함하지 않음

2. 실효성(Effectiveness)

      주어진 상황에 영향을 주어서 실제로 상황을 변화시키는 효과가 있어야 함

3. 입출력(Input/Output)

      입력이 주어지고, 그에 따른 출력이 있어야 함

4. 종료성(Termination)

      기술된 절차는 반드시 종료상태에 도달해야 함

 

 

알고리즘의 간단한 예로 유클리드 호제법을 들어보자.

(쉽게 말해서 두 수의 최대공약수를 구하는 공식임.. 느낌오시죠?)

 

필요조건 : 두 개의 양의 정수 m과 n이 m>n 조건을 만족함

 

① m을 n으로 나눈 나머지를 r로 함

② r=0이면 알고리즘을 끝냄(이 때, n이 최대공약수가 됨)

③ n의 값을 m에 대입하고, r의 값을 n에 대입함

④ ①로 되돌아감

 

이 알고리즘을 c언어로 작성을 해보면

 

int gcd(int m, int n){

    int r;

    while(1){

          r=m%n;

          if(r==0) return n;

          m=n;

          n=r;

    }

}

 

한국어로 표현하는 것 보다 훨씬 간단해보인다?!

 

여기서 중요한 것은, 다음과 같이 작성을 했다고 해서 이게 알고리즘이다!라고 말할 수가 없다. 이건 또 무슨 말이냐하면, 알고리즘을 검토하는 과정을 통해 정당한지를 증명을 해야 한다.

 

정확한 알고리즘은 다음의 조건을 충족해야 한다(알고리즘 정당성의 조건).

1. 어떤 입력 데이터에 대해서도 틀린 답은 계산해 내지 않을 것

2. 어떤 입력 데이터에 대해서도 시간 내에 답을 낼 것(반드시 계산이 끝나야 됨을 의미)

 

그럼 방금 예로 제시한 유클리드 호제법을 가지고 정당성을 증명해보도록 하겠다.

 

m과 n의 gcd(최대공약수)가 d라고 가정을 하면,

 

m=d*mº

 

n=d*nº

그러므로, mº과 nº은 서로소인 양의 정수

 

이 경우에 몫을 u로 두게 되면

r=m-u*n=d*mº-u*d*nº=d*(mº-u*nº)

mº과 nº이 서로소이므로, nº과 mº-u*nº도 서로소임

 

이를 통해, 한번 실행한 후의 변수 m과 n이 가진 값의 d와, 처음의 변수 m과 n이 가진 값의 d가 같다는 사실을 알 수 있고, 이로써 정당성의 첫 번째 조건이 증명이 된다.

 

또한, 알고리즘의 반복을 통해 m을 n으로 나눈 나머지가 새로운 n값으로 변경된다는 사실을 통해 변수 n의 값이 실행 때마다 감소됨으로 정당성의 두 번째 조건도 성립된다.

 

m과 n의 gcd=mº과 nº의 gcd

 

추가적으로 위의 수식과 같이, 어떤 알고리즘의 특정 변수가 갖는 값 사이에 성립하는 주장이 반복 때마다 항상 성립을 하게되면, '루프 불변의 조건'이라고 하는데, 알고리즘의 정당성을 증명하는 기법으로 자주 사용된다.

 

루프 불변의 조건의 증명을 위해서는 다음의 두 가지를 증명하면 된다.

1. 반복이 시작되기 직전에 어떤 루프 불변의 조건이 성립한다는 것

2. 루프 불변의 조건이 성립 시, 반복을 한 번 실행한 뒤에도 다시 그 조건이 성립한다는 것

 

하지만 항상 조건이 설립한다는 것의 증명만으로 알고리즘의 종료성이 증명되는 것이 아니므로, 계산이 끝날 때까지의 최대 반복 횟수를 나타내어 종료성을 증명할 수 있다. 다시 말해, 최대 반복 횟수가 감소한다는 점과, 최대 반복 횟수의 하한값을 나타냄으로써 종료성을 증명할 수 있다.

 

이렇게 만든 여러가지 알고리즘이 하나의 문제를 해결하기 위한 경우에는 어떤 것이 더 좋은 알고리즘인지 알 수 있을까?

 

결론부터 말하자면 문제를 더 빨리 해결할 수 있는, 또는 더 적은 메모리를 사용할 수 있는 알고리즘이 더 좋은 알고리즘이다. 가장 중요한 요소로 답을 계산해 낼 때까지의 소요시간을 들 수 있는데, 이를 시간 복잡도라고 한다.

 

어셈블리 언어를 이용할 경우에는 모든 명령에 대해 각 명령을 몇 번 실행하는가를 세고, 그 명령을 실행하는데 걸리는 시간을 곱한 뒤 합산하여 계산 시간을 구하는데, 프로그래밍 기법의 차이와 수행될 컴퓨터 등 여러 요소를 고려해야 함으로, 다른 언어의 경우에는 잘 사용하지 않는다. 따라서 알고리즘 평가시 프로그램 속에 있는 각 문장이 실행되는 횟수를 세어서 복잡도를 측정한다. 이렇게 알고리즘의 복잡도를 계산하는 것을 알고리즘의 해석이라고 한다.

 

아주 간단한 예로, 복리계산의 경우를 들어보자.

 

 

아마 이것이 위의 식에 대한 가장 단순한 알고리즘일 것이다.

 

50*1.03*1.03*.....*1.03(곱셈 20번)

 

좀 더 감성적인 사람들은 아래와 같이 알고리즘을 작성할 수도 있을 것이다.

 

a=1.03

a²=a*a

a⁴=a²*a²

.

.

 

50 * a16 * a⁴ 

 

보통 알고리즘을 평가할 때에는 어떤 기본 조작을 정하여 그것을 몇 번 실행하는가를 측정하는데, 위 경우에는 곱셈을 기본 연산(조작)으로 보면 된다. 결과적으로 첫 번째 알고리즘은 20번, 두 번째 알고리즘은 6번 곱셈을 실행하게 되는데, 이를 통해 후자가 전자보다 시간 복잡도의 개념으로 보면 3배가 빠르다는 것을 알 수 있다.

 

하지만 몇 개의 기억영역을 필요로 하는가를 측정하는 영역 복잡도의 개념으로 비추어 보면 전자는 곱셈 결과를 기억하는 하나의 기억영역을 필요로 하는 것에 비해, 후자는 a⁴를 기억하는 추가적인 영역을 필요로 하므로 두 개의 기억영역이 필요하다고 볼 수 있다. 따라서 영역 복잡도의 개념으로 보면 전자의 효율이 더 좋다고 볼 수 있다.

 

참고로 알고리즘의 선택에서 복잡도가 가장 중요시되지만, 빠르다고 해서 반드시 좋은 것은 아니다. 알고리즘 또한 프로그램의 일부이므로 프로그램의 조건인 정확성, 신뢰성 등을 만족해야 하기 때문이다. 또한 1회용으로 사용될 알고리즘에 너무 많은 시간을 굳이 투자할 필요는 없다.

 

그 대신, 어떻게 컴퓨터 내에서 데이터를 표현할 것인가에 관심을 가질 필요가 있다. 같은 데이터라도 어떤 방식으로 나열하는가에 따라 성능에 큰 영향이 미칠 수도 있기 때문이다. 이런 메모리에 표현되는 데이터를 자료구조라고 한다. 자료구조에는 아주 다양한 기법들이 있지만 가장 많이 사용되는 방식에는 배열, 연결(링크) 리스트, 스택과 큐가 있다.