[한 권으로 읽는 컴퓨터 구조와 프로그래밍] 11. 알고리즘 아이디어

책에서 나온 예시들은 핵심 내용을 가릴 만큼 지나치게 복잡해, 조금더 간단한 예시로 바꾸어서 핵심 아이디어만을 전달하고자 했다.

중요한 것은 각 예시를 이해하는 것이 아니라 성능과 효율성을 높이기 위해 문제를 바라보는 관점을 달리하는 것이 유용하며 이런 관점도 있구나를 살펴보고 가는 것이다. 따라서 본문의 예시에서 이해되지 않는 부분이 있더라도 큰 그림을 위주로 읽기를 권한다.

 

 

 

 

기상청이 보유한 슈퍼컴퓨터 5호기

 

 

컴퓨터의 성능을 높이는 방법은 간단하다. 더 좋은 컴퓨터를 사면 된다.

예를 들어, 우리나라 기상청에서는 정밀한 날씨 예측을 위해 슈퍼컴퓨터를 보유하고 있다. 1초에 무려 5경2천900조번 연산이 가능하다.

 

 

 

 

그러면 해당 컴퓨터의 가격은 얼마일까? 

 

 

더 성능이 좋은 컴퓨터를 구매하는 것은 쉬운 방법이지만 쉽사리 선택하기는 어렵다. 대신, 계산을 피하거나 최소화해서 성능과 효율을 향상시킬 수도 있다. 바로 알고리즘을 활용하는 것이다.

 

프로그래밍을 공부하는 사람이라면 여러가지 알고리즘들을 많이 접했을 것이다. 하지만 여기서는 구체적인 알고리즘 기법이 아닌, 아이디어에 대해 접근해보려 한다.

 

 

 

 

 

표 찾기

 

 

피타고라스 공식은 빗변을 구하기 위해 다른 두 변의 길이를 이용하는 공식이다. 빗변 C의 제곱을 구하기 위해서, a^2과 b^2의 합을 구하는 것쯤은 컴퓨터에게 부담이 가지 않는다. 하지만 이런 반복적인 계산이 수억, 수백번 이루어진다면 효율성을 저하시킬 수 밖에 없다.

 

반복적인 계산을 피하기 위한 간단한 아이디어로, a와 b에 대한 c^2의 값을 표를 만들어두고, 표에서 이미 계산된 값만 가져올 수도 있다. 이 아이디어는 한 번의 계산의 공식이 복잡할 수록 빛을 발할 것이다.

	1	2	3	4
1	2	5	10	17
2	5	8	13	20
3	10	13	18	25
4	17	20	25	32

 

 

 

 

조금 더 복잡한 예시를 보자. 아스키 코드 값에 대해 이 코드가 의미하는게 숫자인지, 16진수인지, 문자인지, 대문자인지 어떻게 구별할 수 있을까?

 

public boolean isDigit(char c) {
    if (c >= '0' && c <= '9') {
        return true;
    }
    return false;
}

 

이와같은 검사를 여러번 수행하면 문자 종류를 판별할 수 있겠지만, 효율적인 방법은 아니다. 대신 아스키 코드에 대해 8비트의 2진수를 매칭할 수 있다.

 

	대문자	소문자	숫자	16진수	구두점	화면 출력 문자	제어문자	공백문자
48 ('0')	0	0	1	1	0	1	0	0
65 ('a')	0	1	0	1	0	1	0	0
90 ('z')	0	1	0	0	0	1	0	0
97('A')	1	0	0	1	0	1	0	0

 

48이라는 아스키코드의 문자를 판별하고 싶다면, 각 비트가 1인지만 확인하면 된다. 숫자에 해당하는 비트가 1이므로, 이 코드는 숫자로 판별할 수 있다!

 

 

 

 

 

 

 

 

수를 활용하는 연산

 

연산의 종류에 따라 연산의 속도에는 차이가 있다. 일반적으로, 덧셈, 뺄셈 < 곱셈, 나눗셈 < 부동소수점 연산 < 삼각함수, 로그함수 계산 순으로 속도가 더 오래 걸린다. 또한 해야할 연산이 많을 수록 더 오랜 속도가 걸린다. 이는 만약 복잡한 계산을 프로그래머가 공식을 활용해 간단한 연산으로 바꾸어서 계산시키면 속도가 줄어들 수 있다는 이야기와 같다.

 

 

평면도형의 넓이를 구하기 위해 구분구적법을 활용할 수 있다. 구분구적법이란 작은 직사각형으로 쪼개서 그 합을 구하는 방법이다. 최대한 정밀한 값을 구하기 위해서는 사각형을 더 잘게 쪼개야만 한다.

 

 

 

하지만 정적분을 이용하면 훨씬 더 짧은 연산을 거쳐서 평면도형의 넓이를 구할 수 있다.

 

 

 

 

𝜋는 순환하지 않는 무리수의 일종이다. 원의 둘레를 소수 두자리수에서 반올림해서 나타내려고 할 때, 굳이 3.141592 ..... 라는 길고 긴 범위를 모두 계산할 필요 없이 간단하게 3.14를 곱한 다음 반올림을 해도 충분하다. 즉, 정밀도에 따라 계산을 더 간단하게 변환할 수도 있다는 이야기다.

 

 

 

 

 

 

 

재귀적 분할

 

 

해결하기 힘든 만큼 커다란 문제를 더 작은 문제로 쪼개서 해결하는 것도 좋은 방법이다.

예를 들어 2의 1000승을 구한다고 생각해보자. 2를 1000번이나 곱하는 것은 쉬운 일이 아니다 (컴퓨터에게는 쉽지만, 1000이 아니라 1000조라고 생각하면 컴퓨터도 힘들어할 것이다!)

 

그런데 2^1000은 2^500 * 2^500으로도 생각할 수 있다. 한 번 나누는 것만으로도, 1000번의 곱셈이 501번의 곱셈으로 줄어들었다. 2^500승은 다시 2^250 * 2 ^250으로 나눌 수 있다. 이같은 과정을 계속 반복해서, 더이상 쪼갤 수 없을때까지 (2^0) 문제를 쪼개면 더 간단하게 결과를 구할 수 있다.

 

 

 

 

 

정리

 

좋은 성능의 컴퓨터를 가지고 있더라도, 알고리즘이 적합하지 않으면 높은 성능을 기대하기 어렵다. 뛰어난 한 명의 프로그래머가 값비싼 컴퓨터보다 더 가치있는 일을 하기도 한다. 그렇기 때문에 항상 문제를 어떻게 더 효율적으로 해결할 수 있을지 고민하는 것이 필요하다.

 

 

 

 

 

 

 

-- 확인문제 --

 

A는 입력받은 아스키 코드가 숫자를 가리키는지, 문자를 가리키는지 파악하기 위해 다음과 같은 알고리즘을 세웠다.

 

public String check(char c) {
    if (c >= '0' && c <= '9') {
        return "숫자"
    } else if (c >= 'a' && c <= 'z') {
    	return "소문자"
    } else if (c >= 'A' && c <= 'Z') {
    	return "대문자"
    } else {
        return "숫자도 문자도 아닙니다.";
    }
}

 

문자를 판별해야하는 경우가 너무 많아, 성능을 향상시키기 위해 리팩토링을 하려는 A는 어떤 아이디어를 적용할 수 있을까?

 

 

-- 정답 --

결과값을 미리 계산해서 반복 사용한다 (표 찾기)