한빛출판네트워크

작성: 한동훈(traxacun at unitel.co.kr)

작성일: 2003. 2. 24

알고리즘 분석은 여러분에게 미신적인 이야기가 아닌 과학적인 이야기를 하기 위해 필요한 도구다. 프로그래머들 사이에는 수 많은 미신들이 있다. 제가 들었던 미신중에 가장 인상적인 미신에는 다음과 같은 것이 있다.

 

“암호화나 스트림을 처리하는데 있어 루프를 반복하게 되는데, 보통 이 루프의 수는 몇 백만 번을 훌쩍 뛰어넘게 된다. 이 경우에 루프 카운터를 0부터 1씩 증가시키는 게 아니라 가장 큰 값에서 1씩 감소시키면서 실행하면 루프가 더 빨라진다! 왜 빨라지냐면 MSB로 값이 저장되기 때문에 가장 큰 숫자부터 비교하게 되면 가장 먼저 비교가 수행되며, 코드에서 값을 비교할 때 비트 단위로 비교하기 때문에 결과적으로 비교할 비트의 수가 줄어들기 때문에 큰 수에서 1씩 빼가면서 작은 수로 비교하게 되면 비교할 비트 수가 줄어들기 때문이다!”

 

얼핏듣기에는 그럴듯해보이고, 개발 경력이 꽤 있다는 개발자들도 무릎을 탁 치게 되곤한다. 위 이야기를 듣고 큰 깨달음(?)을 얻었다고 생각하는 사람들은 종종 신봉자가 되는 것 같다. 하지만, 실제로는 그렇지 않다. 프로그래밍 언어는 비트 단위로 비교를 하고, 비교가 만족한다고 비트 단위로 수행하는 비교를 그만두지도 않는다. 32 비트와 32 비트를 비교하면 32 비트를 모두 비교하지요.

 

이와 비슷한 이야기로는 이진 가산기(binary adder)가 있다. 이진 가산기라고 꽤 거창한 용어로 포장하고 있긴 하지만, 사실 대단한 것은 아니다. 그저 1씩 더해갈 뿐이지요. 우리가 보통 다음과 같이 쓰는 것이죠.

 

result = a + 1;

 

실제로 이진 가산기처럼 계속해서 더해가는 것들은 간단한 for 루프라고 할 수 있다.

 

for ( int loopctr = 0; loopctr < loop_count; loopctr++ );

 

보통은 이런 것들이 이진 가산기와 같은 것들이다.

 

우리가 보통 정수형이라 부르고, 값을 저장하는 것은 메모리에 이진수로 다음과 같이 저장된다. 왼쪽에는 십진수를, 오른쪽에는 이진수로 썼다. 이진수는 편의상 8개의 비트만 표현했다.

 

0 - 0000 0000
1 - 0000 0001
2 - 0000 0010
3 - 0000 0011
4 - 0000 0100
5 - 0000 0101
6 - 0000 0110
7 - 0000 0111

8 - 0000 1000

 

우리가 루프를 사용할 때 컴퓨터의 메모리에서 실제로 일어나는 과정이다. 한 번 살펴보자. 0과 1 사이에서는 비트가 몇 개 바뀌었는가? 1개가 바뀌었다. 1과 2 사이에는 비트가 몇 개 바뀌었는가? 2개의 비트가 바뀐다. 2와 3 사이에는 1개의 비트가 바뀌고, 3과 4 사이에는 3개의 비트가 바뀌는 것을 알 수 있다. 4와 5 사이에는 1개의 비트가, 5와 6 사이에는 2 개의 비트가, 6과 7 사이에는 1개의 비트가, 7과 8 사이에는 4개의 비트가 바뀌는 것을 알 수 있다. C#의 int 형식과 같이 32비트 데이터 형이라면 최고로 큰 수라면 한 번에 32개의 비트가 바뀌는 순간도 있다는 것을 알 수 있을 것이다. 어떤가요? 과연, 우리는 1개의 비트가 바뀔때와 2개의 비트가 바뀔 때, 그리고 32개의 비트가 한 번에 변경될 때 수행시간이 같다고 이야기할 수 있을까? 컴퓨터의 수행시간이 빠르니까라는 식의 이야기는 전혀 도움이 되지 않는다. 대부분의 독자들은 이러한 것들에 대해서 단 한 번도 생각해 보지 않았으리라는 것을 알고 있다. 전공자라면 그저 데이터 구조론 시간이나 알고리즘 분석 시간에 O(1)과 같은 빅O 표기법에서 상수의 계산은 수행시간 1, 즉 상수라고 외웠을 뿐이라는 것을 잘 알고 있다.

 

위 비트가 바뀌는 순서를 보면 일련의 규칙성이 있다. 규칙성을 써보면 다음과 같다.

0 - 0000 0000

        - 1 bit
1 - 0000 0001

- 2 bit
2 - 0000 0010

- 1 bit
3 - 0000 0011

- 3 bit
4 - 0000 0100

- 1 bit
5 - 0000 0101

- 2 bit
6 - 0000 0110

- 1 bit
7 - 0000 0111

- 4 bit

8 - 0000 1000

 

이와 같은 비트수의 변화를 일렬로 계속 쓰면 1, 2, 1, 3, 1, 2, 1, 4, …과 같다는 것을 알 수 있다. 이진수에서 비트의 변화를 살펴보면 비트가 1인 곳은 비트가 1이 아닌 곳을 감싸고 있다는 것을 알 수 있다. 즉, 1, 2, 1은 3을 감싸고 있으며, 1, 2, 1, 3, 1, 2, 1은 4를 감싸고 있다는 것을 알 수 있다. 이러한 규칙성을 n개의 비트에 대해서 확장할 수 있다는 것을 알 수 있다. 32 비트 데이터 형식에 대해서 생각해 보면 32개의 비트가 변하는 수는 1번, 31개의 비트수가 변하는 경우는 2번, 30개의 비트가 변하는 경우는 4번, 29개의 비트가 변하는 경우는 8번… 이라는 규칙을 유추할 수 있다.

즉, 다음과 같은 수식을 유추할 수 있다.

　

이것을 일반화시키면 다음과 같다.

 

 

그리고 위 식을 다시 일반화시키면 다음과 같은 공식이 나타난다.

 

과연 이게 맞는가 틀린가는 여러분이 직접 숫자를 대입해보면 알 수 있다. 비트의 변화수가 정확히 일치한다는 것을 알 수 있을 것이다. 그리고 이미 알아챘겠지만, 우리가 알고자하는 비트의 변화수는 등비수열이라는 것을 알 수 있다. 등비수열을 무한대로 보낼 경우, 익히 고등학교 수학시간에 배웠을 등비수열의 합 공식이 나타난다. 비트의 변화수를 나타내는 수열의 첫번째 항은 1이고, 등비는 라는 것을 알 수 있다. 등비수열의 합 공식이 기억나지 않는 분을 위해 적어보면 라는 것이며, 위 등비 수열을 무한대로 보낼 경우 2라는 숫자가 나온다. 즉, 아무리 비트수가 많아져도 2라는 시간밖에 걸리지 않는다는 것을 알 수 있다. 빅O 표기법은 상수에 대해서는 O(1)과 표기하기 때문에 이진 가산기의 알고리즘 수행시간 역시 O(1)로 표기할 수 있다. 정말로 아직도 이해가 안가고 호기심이 많은 분이라면 를 직접 계산해보기 바란다.

 

다행히도 필자의 후배, 정진일군이 이 문제를 아주 멋지게 풀어주었다. 어차피 같은 이야기지만 여기에 그 증명을 옮겨보자.(수식편집은 사실 괴롭지만… )

　

또 다른 증명

0 0 0 (0)
0 0 1 (1)
0 1 0 (2)
0 1 1 (3)
1 0 0 (4)
1 0 1 (5)
1 1 0 (6)
1 1 1 (7)
- - -
| | |-----> 0번째 자리인 경우를 보면 2^0(2의 0승)마다 toggle이 일어납니다.
| |
| |-------> 1번째 자리인 경우를 보면 2^1(2의 1승)마다 toggle이 일어납니다.
|
|---------> 2번째 자리인 경우를 보면 2^2(2의 2승)마다 toggle이 일어납니다.

위와 같은 현상을 봤을 때, n-bit일 경우 toggle하는 총 횟수 b_tog(n)는

　

 

그러나 위 식은 n을 무한대로 보낼 경우 tog(∞) -> ∞가 된다. 그러므로 여기서 평균이라는 개념을 써서 avg_b_tog(n)을 정의한다.
　

여기서 n을 무한대로 보내면, avg_tog(∞)은 초기값 a는 1이고 곱해지는 값 r은 1/2 인 등비수열이 된다.

그러므로 binary는 1씩 증가될 때 마다 평균 2번 toggle되는 성질을 갖고 있다. 

 

또 다른 증명은 이것으로 끝이다. 이해가 되지 않는다면 조금 더 찬찬히 살펴보길 바라고, 그래도 안되면 정석이라도 먼저 펼쳐보길 바란다.

 

사실, 후배의 증명은 여기서 끝나지 않았다. 바이너리 카운터가 아닌 그레이 코드에 대해서도 소개하고 있지만, 그것은 우리의 논의를 벗어나니 살짝 피해가자.(필자의 퀴즈에 하드웨어 설계 구현 얘기까지 해주신 분들에게 경의를 표하자!!)

　

우리가 흔하게 쓰고 있는 정수의 덧셈이 늘 일정한 알고리즘 수행시간(constant)을 갖는 이유가 여기에 있다. 그렇지 않다면 단순히 숫자의 크기가 커지는 것만으로도 연산이 느려질 수 있을 것이다.

 

알고리즘 분석은 여러가지 면에서 분석을 한다는 의미이다. 해당 코드 즉, 알고리즘이 차지하는 공간(메모리의 크기 등)을 분석하고, 수행 시간을 분석하는 것들을 모두 합해서 말한다. 하지만, 여기서는 주로 수행시간에 대해서 이야기할 것이다. 현재와 같이 발전된 하드웨어에서는 공간보다는 수행 성능에 더 많은 관심을 갖기 때문이다.

 

처음에 꺼낸 이야기는 binary adder에 대한 이해가 빠졌다는 것 뿐만 아니라 결정적으로 컴퓨터에는 뺄셈에 대한 연산이 없다는 문제가 있다. 따라서 어셈블리를 보면 뺄셈 루프를 사용하는 것이 덧셈 루프를 사용하는 것보다 더 많은 기계어 명령이 들어간다는 것을 알 수 있다.(CPU는 뺄셈을 계산하는 명령이 없으며 이진수의 보수에 의해 계산하고 비트를 뒤집어서 뺄셈에 대한 결과를 얻는다) 자신이 어떠한 프로그래밍 언어를 사용하더라도 결국에는 CPU에 정의된 Op_Code로 변한된다. 또한 뺄셈 연산은 덧셈 연산에 비해 두 개의 op_code가 추가되고, 보수 연산을 위한 임시 저장소(레지스터) 연산이 추가된다. - 이 이야기가 이해되지 않거나 호기심이 많은 독자라면 인터넷에서 이진법과 보수 연산에 대해서 검색하면 많은 이야기를 볼 수 있으며, 어셈블리 언어와 x86 CPU 아키텍처에 대한 자료를 인텔(intel.com)에서 받아볼 수 있다. 물론, op_code 목록도 인텔 사이트에서 받아볼 수 있다.

 

지금까지의 이야기로 처음에 꺼낸 이야기가 왜 틀렸는지 알았을 것이다. 이제, 수행 시간 분석에 대해서 이야기 해보자.

 

 

알고리즘 수행 시간 분석: a detailed model

저 영어를 한글로 어떻게 얘기하는지 잘 모른다. 전산학이 전공이 아닌 탓도 있다. 그러니 조금은 너그럽게 봐주길 부탁한다.

 

result = counter;

 

이와 같이 두 개의 변수가 있는 경우에 result에는 값을 저장하는 과정이 일어나며 이 때의 수행시간을 T_store라고 한다. T는 시간(Time)에 대한 의미다. counter는 메모리에 저장된 값을 가져오기 때문에 T_fetch라고 한다. 따라서 총 수행시간은 T_fetch + T_store가 된다.

 

result = 3;

 

이와 같은 경우에도 알고리즘 수행시간은 T_fetch + T_store가 된다. 즉, 첫번째와 전혀 변하지 않는다. 숫자 3이 상수라 하더라도 저장되는 공간이 필요한 것은 마찬가지이므로 T_fetch라는 수행시간을 갖는다.

 

loopctr = loopctr + 1;

 

과 같은 경우에는 T_store + T_fetch + T_+ + T_fetch라는 수행시간이 걸린다. 연산 기호에 대해서도 마찬가지로 T_+와 같이 표현한다. 다른 연산 기호들도 마찬가지이다.

 

++loopctr;

loopctr++;

loopctr += 1;

 

위 세가지는 모두 loopctr = loopctr + 1로 풀어쓸 수 있기 때문에 수행시간은 모두 동일하다. 값을 반환하는 경우에는 T_return, 함수를 호출하는 경우에는 T_call과 같이 표기하며, 함수 F(x)를 호출하는 경우에는 수행시간을 T_F(x)와 같이 표기한다.

 

 

이와 같은 코드에 대한 알고리즘 수행시간을 계산해보자. for 루프의 첫번째는 T_fetch + T_store이며 1회만 수행된다. for 루프의 두번째 부분은 (2T_fetch + T_<)이며 n + 1번 수행하기 때문에 (n +1)을 곱해준다. 마찬가지로 세번째 루프를 계산하면 (2T_fetch + T_+ + T_store) * N이라는 것을 알 수 있다. 이들을 모두 더하면 위 코드의 알고리즘 수행시간이 된다.

 

배열의 경우에는 다음과 같이 분석한다.

 

a[5]

 

이와 같은 배열이 있을 경우 a는 메모리상에서 배열이 시작하는 위치를 가리킨다. 따라서 T_fetch 라는 수행시간이 발생한다. 메모리 상에 배열이 연속되는 공간으로 배치되며, 여러 개의 방들로 나뉘어 있다. 이중에 6번째 방에 있다는 것을 나타내므로(C#, C/C++등은 0부터 인덱스가 시작하므로 5는 6번째를 뜻한다), 6번째 위치를 가져오는 역할을 한다. 따라서 T_fetch라는 수행시간이 발생한다. 이제는 해당 메모리 위치에 저장된 값을 가져와야하므로 T_fetch라는 수행시간이 발생한다. 따라서 배열 연산에서는 총 3T_fetch라는 수행시간을 필요로 한다.

 

이외에 다차에 대한 수행시간 계산에는 Honer’s rule을 적용하고, n개의 데이터 입력에 대한 계산을 수행하기 위해 평균값의 정리를 도입한다.

위와 같이 모든 것을 세분화한 것을 detailed model이라 하며, 지나치게 복잡하기에 사용하지 않는다. 대신에 simplified model을 도입한다. simplified model은 detailed model을 간단하게 한 것이다. 이러한 가정을 위해 T로 표현되는 모든 매개변수를 클럭 사이클의 단위로 표현한다고 가정한다. 즉, T = 1이라고 가정한다.

 

따라서 위에 지금까지 구분했던 모든 수행시간을 1로 계산하여 식을 간단하게 할 수 있다.

 

다음과 같은 계산 결과를 구하는 코드를 작성한다고 생각해보자.

　

　

 

알고리즘 수행시간을 분석하면 첫번째는 2이고, for 루트는 각 부분을 나눠보면 2, 3(n+2), 4(n+1) 이라는 것을 알 수 있고, 루프안의 int prod = 1는 2(n+1)이라는 것을 알 수 있다. 마찬가지로 두번째 for 루프의 수행시간을 살펴보면 2(n+1), 과 같다는 것을 알 수 있다. prod += x; 부분역시 과 같은 수행시간을 필요로 하며, 나머지 두 줄 역시 각각 4(n+1)과 2라는 수행시간을 갖는 것을 알 수 있다. 충첩된 루프의 수행 횟수를 계산하기 위해 가 필요하다는 것은 전혀 이상한 일이 아니다. 마찬가지로 고등학교 수학 실력을 발휘해서 풀어보면 다음과 같다.

 

 

보통 위와 같은 알고리즘 수행시간을 가질경우 이 데이터의 개수 n에 대해서 가장 비중있는 역할을 하기 때문에 빅O 표기법에서는 O()으로 표기한다. 일반적으로 과 같은 수행시간은 중첩 루프안에서 나타난다. 따라서 데이터의 크기가 큰 경우에는 중첩 루프를 사용하지 않아야한다는 것을 알 수 있다. 마찬가지로 삼중 루프를 사용하는 경우에는  항이 나타나고, 이는 O()의 알고리즘 수행시간을 갖는다고 얘기한다.(물론 4개의 중첩 루프를 가짐에도 불구하고 nlogn 정도의 수행시간을 갖는 알고리즘도 있으므로 루프의 중첩 단계만으로 알고리즘 수행시간을 단정짓는 것은 많은 오류를 가질 수 있지만 대부분의 경우에 이와 같은 생각이 받아들여진다.)

 

위 코드를 작성하게된 배경은 다음과 같다.

　

즉, 덧셈에 대해서 첫번째 루프를 수행하고, 세로 행에 대한 각 X의 곱에 대해 두번째 루프에서 수행한다는 아이디어를 코드로 옮긴 것에 불과하다. 코드를 보면서 이해하는 바보스러움 보다는 아이디어를 이해하는 것으로 족하다고 생각한다. 아이디어를 이해한다면 코드는 얼마든지 작성할 수 있다.

 

위 코드를 다음과 같이 다시 작성해보자.

 

 

이 코드에 대한 각 항목을 분석하면 2, 2, 3(n+2), 4(n+1), 6(n+1), 2라는 수행시간을 가지며, 모든 항목을 더하면 13n + 22의 수행시간을 갖는다는 것을 알 수 있다. 즉 O(n)의 수행시간을 갖는 알고리즘이라 얘기할 수 있다.

 

이 알고리즘의 아이디어는 다음과 같다.

　

　

즉, 현재 항까지의 총 합은 ‘이전 항까지의 합 + 현재 항’이라는 간단한 아이디어를 표현한 것임을 알 수 있다. 코드를 보고 1일 때는, 2일 때는 식의 지엽적인 분석은 절대로 하지마라. 그것은 여러분 스스로 남의 코드를 이해할 수 없게 만드는 지름길이다. 문제가 있는 코드라면 세밀한 분석이 필요하지만 대부분의 경우에 그 정도의 분석은 필요하지 않다. 게다가, 이러한 세밀한 분석이 필요하다면 여러분의 나쁜 기억력과 자신의 졸필에 의존하지 말고 디버거에 의존해서 정확하게 분석해내는 습관을 들여라. 이런 경우가 아니라면 코드를 보면서 아이디어를 이해해라. 아이디어를 이해하면 같은 코드를 얼마든지 작성할 수 있을 것이다.

 

지금까지 살펴본 것으로 간단한 알고리즘의 수행시간을 알아낼 수 있을 것이다. 항상 좋은 알고리즘 수행시간을 가질 수는 없지만, 현실적으로 어떤 코드가 빠른지 개인적인 분석은 할 수 있을 것이다.

 

프로그래머 역시 엔지니어다. 뺄셈 루프가 빠르다느니, 요즘 CPU가 얼마나 빠른데 그런건 순식간이에요. 라는 이야기를 다시 듣게 되는 날이 없기를 바란다.(2Ghz일 경우에 1초에 2G 만큼의 op_code(연산)을 수행한다는 뜻이니 1/2G = 0.5ns 밖에 안된다. 빠르다는 생각은 하지말자)

　

마치며

소프트웨어가 아닌 하드웨어를 전공으로 하고 있는 탓에 이진 가산기에 대한 이야기나 또는 하드웨어적인 부분이 많이 등장했지만 수행시간에 대한 기본적인 이해가 되었다면 그것으로 의미있다고 생각한다.