내가 짠 코드가 효율적인 걸까? 알고리즘 평가의 세가지 요소
1. 알고리즘을 평가해야하는 이유
프로그래밍을 배우기 시작하면 가장 많이 듣게 되는 단어중 하나가 알고리즘이라고 할 수 있다.
알고리즘은 컴퓨터를 사용해서 어떤 문제를 해결하는 절차나 방법을 의미한다.
그렇다면 이러한 알고리즘을 왜 평가해야 할까?
다음은 9개의 printf() 함수가 있는 프로그램이다.
1) printf()가 여러개인 프로그램
int main() {
printf("hello world!\n");
printf("merry christmas!\n");
printf("happy new year!\n");
printf("hello world!\n");
printf("merry christmas!\n");
printf("happy new year!\n");
printf("hello world!\n");
printf("merry christmas!\n");
printf("happy new year!\n");
return 0;
}2) for문을 사용한 프로그램
int main() {
for (int i = 0; i < 3; i++) {
printf("hello world!\n");
printf("merry christmas!\n");
printf("happy new year!\n");
}
return 0;
}
두 코드 모두 실행 결과는 같다.
결과만 놓고 보면 두 코드 모두 같지만 그 구현 방법에 대해 차이가 있다.
첫번 째 방법은 이후 반복해서 출력해야 할 문자열이 늘어날수록 코드를 일일히 작성해서 추가해줘야 하지만
for문을 사용한 방법은 종결조건만 바꿔주면 된다는 차이가 있다.
그리고 이 두 방법중 누구나 후자의 방법이 더 효율적인 코드라는 것을 알 것이다.
그렇다면 구체적으로 알고리즘은 어떻게 평가하면 되는 것일까?
알고리즘의 효율성은 크게 3가지로 판단할 수 있다.
- 시간의 효율성
- 공간의 효율성
- 코드의 효율성
2. 시간의 효율성
컴퓨터에서 실행되는 프로그램들은 문제를 해결하는 데 무한대의 시간을 사용할 수 없다.
아래의 두 코드는 1~1000까지의 정수가 차례대로 저장되있는 둘 다 data라는 배열안에서 사용자로부터 입력받은 값을 찾아내는 코드이다.
1) 단순한 프로그램
#include <stdio.h>
int main() {
int i, input;
int data[1000];
for (i = 0; i < 1000; i++) {
data[i] = i + 1;
}
printf("찾을 값을 입력하세요: ");
scanf("%d", &input);
for (i = 0; i < 1000; ++i) {
if (input == data[i]) {
printf("찾는 값은 data 배열의 %d 번째에 있습니다.", i+1);
break;
}
}
return 0;
}
2) 똑똑한(?) 프로그램
#include <stdio.h>
int main() {
int i, input;
int data[1000];
int min=0;
int max=1000;
for (i = 0; i < 1000; i++) {
data[i] = i + 1;
}
printf("찾을 값을 입력하세요: ");
scanf("%d", &input);
i = (min + max) / 2;
while (min <= max) {
if(input==data[i]) {
printf("찾으시는 데이터가 %d 번째에 있습니다.", i);
break;
}
else if (input < data[i]) {
max = (min + max) / 2 - 1;
}
else{
min = (min + max) / 2 + 1;
}
i = (min + max) / 2;
}
return 0;
}
첫번째 코드의 경우, 처음부터 순차적으로 비교하기 때문에
운이 좋아 사용자가 적은 수를 입력했다면 금방 찾게 되지만 최악의 경우 1000번의 비교연산을 거쳐야한다.
두번째 코드의 경우는 사용자가 입력한 값과 배열의 중간값을 비교해서 같지 않을 시
배열을 이등분하여 배열의 중간값보다 작으면 앞부분의 중간값과 비교를 하고
배열의 중간값보다 크면 뒷부분의 중간값과 비교를 한다.
이렇게 비교하면 최악의 경우에도 9번의 비교연산만 하면 금방 원하는 값을 찾을 수 있다.
3. 공간의 효율성
두번째 요소는 공간의 효율성이다.
최근의 메모리 비용이 아무리 저렴하다고 하더라도 무한대의 메모리를 사용할 수는 없다.
그리고 대부분의 운영체제는 여러개 프로그램에서 하나의 물리적인 메모리를 공유해서 사용하므로 메모리를 효율적으로 관리하는 것이 중요하다.
아래의 소스코드를 보자.
int main() {
int i;
int data[1000];
for (i = 0; i < 10; ++i) {
data[i] = i;
}
}
위 코드는 data를 선언하고 0~9까지의 정수값을 저장하는 코드이다.
실제로 사용하는 것은 0~9까지의 숫자인데 data를 선언할 때 1000개의 숫자를 선언해버려서
990개의 불필요한 메모리 공간이 생긴 것이다.
또, 아래는 불필요하게 낭비되는 메모리의 다른 예시이다.
int Add();
int Num_A,Nub_B;
int ret;
int Add(){
//전역변수를 사용해서 메모리가 낭비된다.
return Num_A+Nub_B;
}
void memory2() {
Num_A=100;
Nub_B=10;
ret = Num_A + Nub_B;
}다소 극단적인 형태인 감은 있지만
코딩을 하다보면 간혹 굳이 전역변수로 사용 안해도 될 변수들을
전역변수로 사용하는 코드를 종종 마주칠 때가 있다.
전역변수는 지역변수와 달리 프로그램 실행시점부터 종료 시점까지 메모리 공간을 계속 유지하게 되므로 상당히 비 효율적이다. 때문에 부득이한 경우를 제외하고는 가급적이면 전역변수 사용을 줄여야 한다.
4. 코드의 효율성
마지막으로는 코드의 효율성이다.
코드의 효율성은 프로그래머가 보는 효율성과 컴퓨터가 보는 효율성 두가지가 있다.
4-1) 프로그래머의 코드 효율성
프로그래머가 보는 코드 효율성은 가독성이 좋은 코드를 의미한다.
시간이 지나고 다시 해당 코드를 수정하더라도 쉽게 수정할 수 있어야 하고
다른 프로그래머가 와서 코드를 보더라도 쉽게 이해할 수 있어야 한다.
간혹 암호문처럼 복잡하게 코드를 쓰고 다른사람이 이해하지 못하는 것을 보면서
의기양양해하는 프로그래머들이 있다.
예를 들면 다음과 같은 코드이다.
b=++(a-- *++c)/++d;
위와같은 코드가 1만행정도 있다고 생각해보자.
대부분의 사람의 경우 10행정도 읽고나면 코드 읽기를 포기해 버릴 것이다.
이런 경우에 프로그래머 입장에서 비 효율적인 코드라고 할 수 있다.
대부분의 경우 프로그래밍은 혼자하는 일은 잘 없기 때문에
협업을 가정해서 읽기 쉬운 코드를 작성하는 것은 중요하다.
코드 내용이 어려우면 주석도 달아야 하고,
변수 이름이나 함수 명에도 A(), B()와 같이 단순한 알파벳 나열이 아니라 용도에 맞게 짓는 것이 중요하다.
4-2) 컴퓨터의 코드 효율성
컴퓨터가 보는 효율성은 컴파일러와 하드웨어에 좀 더 최적화된 코드를 의미한다.
아래의 소스코드를 보자.
int main(){
int i;
for (i = 0; i < 10; ++i) {
printf("%d X %d=%d \n", i, i, i * i);
}
}
얼핏 보기에는 별 문제가 없어보이지만 컴퓨터 입장에서는 굳이 i를 int로 선언할 필요가 없다.
int형은 4바이트를 차지하는데 위의 예제 코드에서는 최대 81까지밖에 숫자를 사용하지 않기 때문이다.
이럴 경우에는 char자료형이나 unsigned char 자료형을 사용하는 것이 더 좋을 것이다.
