알고리즘이란 어떤 주어진일을 처리하기 위한 프로시저이다. 광범위하게 보자면 어떤일이든지 수행하려면 복잡하든지 단순하든지 간에 고유의 알고리즘이 사용될 것이다. 똑같이 주어진 일이라도 어떠한 방식을 사용하느냐에 따라서 비용에 있어서 많은 차이가 난다. 작업의 정석, 승진잘하기, 부동산으로 떼돈벌기 식의 제목의 책들이 담고 있는 내용이란 것은 이성을 잘 꼬시는 효과적인 알고리즘, 부동산 투자를 잘하는 효과적인 알고리즘들에 대한 것들일 것이다. 똑같은 시간을 들여서 작업을 걸더라도 얼마나 효과적인 방법을 알고 있느냐에 따라 결과가 달라지다 보니, 베스트셀러에 두서너권 정도 이런책이 끼어있기 마련이다.
컴퓨터 역시 마찬가지다.
알고리즘에서의 사소한 차이가 처리시간, 처리에 필요한 컴퓨터 댓수, 컴퓨팅 파워등 품질과 비용에 결정적인 영향을 끼치게 되므로, 매우 중요하게 생각한다. 특히 컴퓨터는 대량의 데이터를 처리하는데 특화된 기계다. 수많은 데이터를 반복처리하는 일을 잘 한다는 얘기다. 요즘 같은 시절에는 수천만건의 데이터를 처리하는게 매우 일반적이다.
단순하게 생각해서, 천만건의 데이터를 처리하는데 좋지 않은 알고리즘으로 0.05초씩의 시간손해가 발생했다고 하면 무려 5일의 시간손해가 발생하게 된다.
컴퓨터는 충분히 빠르다 ?
컴퓨터는 확실히 빠르긴 하다. 인간의 뉴런세포 하나가 초당 계산할 수 있는 양이 수백건 정도라고 들은적이 있는거 같다. 반면 컴퓨터는 초당 기가 byte(:12)단위로 비교할 수 없을 정도로 빠르다. 문제는 처리해야 하는 데이터양으로 컴퓨터가 데이터의 양을 따라가지 못할 정도로 급격하게 증가하고 있다.
10년전이라면 로드파이터 정도의 게임으로도 소비자를 만족시킬 수 있었을 것이다. 지금은 FULL HD 슈퍼 리얼 드라이빙 3D 시뮬레이션정도의 수식어는 달고 나와야 좀 할만하네하는 평가를 받고 있다. 범용적인 컴퓨터로는 이러한 수준의 게임을 제대로 처리하지 못하고 있으며, 게임만을 위해 특화된 게임기를 구입해야 게임을 즐길 수 있다. 게임이 컴퓨터 하드웨어를 리드하고 있다는 것은 굳이 말할 필요도 없을 것이다.
검색의 경우도 전세계 문서를 상대로 할 경우 페타바이트 단위의 문서를 처리해야 한다. 간단한 지역검색을 한다고 해도 최소한 천만건은 되어야 서비스하는 모양이다라는 소리를 듣는다.
아마존과 같은 온라인 서점의 경우 경쟁력의 확보를 위해서 개인화 서비스를 실시한다. 도서추천과 같은 서비스를 한다고 가정해 보자. 나와 비슷한 구매성향을 가진 구매자들이 많이 구매해서 본 책을 추천하는 식으로 이루어질 것이다. 만약 천만 구매자를 대상으로 서비스를 계획 하고 있다면 10000000 * 10000000 의 크기를 가지는 테이블을 분석해야 한다.
그렇다고 알고리즘이 실질적으로 중요하나요 ?
아마존, 구글 그런 대형의 사이트들은 그렇다 치고 우리 모두가 그런 서비스를 만들건 아니잖아요 ? 라고 물어볼 수도 있을 거 같다. 현장을 뛰어보면 알겠지만 (특히 기업형 제품들의 경우) 하루에 기가바이트 단위의 데이터를 처리해야 하는 경우는 흔히 발생한다.
자료구조 알고리즘 같은 관련된 좋은 책들도 많이 나와 있고, 훌륭한 라이브러리들도 많이 있다. 그냥 필요할 때, 찾아서 쓰면 되는거 아냐? 라고 말하기도 한다.
이는 서점에 가면, 작업 책도 많고 부동산 책도 많다. 인터넷에는 관련 정보가 넘쳐 있다. 책하나 사서 보면 나도 카사노바, 나도 부동산 재벌, 나도 CEO 라고 하는 것과 같다. 이 정보들은 일반적인 정보들일 뿐이다. 이걸 실제 현실에 적용시키기 위해서 얼마나 많은 고민과 노력을 했느냐의 차이가 전문가와 아마추어의 간격을 만들어낸다.
간단한 예를 들어보자. 검색쪽 일을 하고 있으니 검색관련 예를 들어보도록 하겠다.
색인된 데이터만 10기가인 10,000,000 건의 문서가 있다고 가정하자. 이 색인 테이블은 Key가 단어 이고 Value는 단어를 포함한 {문서의 번호,Score}의 리스트로 구성되어 있을 것이다.
문제
A와 B 단어에 대해서 두개의 {문서번호,Score} 목록을 가져왔다. 이 결과를 Score를 기준으로 정렬해서 가장 높은 10개의 문서번호를 얻어오라. 문서번호가 중복될 경우 Score를 더햇서 정렬하라. 조건 : Value는 문서번호로 정렬되어 있다.
Merged Sort를 이용하면 된다는걸 알고 있다면 일단 30점 획득이다. STL(:12)과 같은 라이브러리에서 제공하는 set_union 과 같은 합집합 함수를 적용하면 되지 않는냐라고 생각할 수 있을 것이다. 혹은 두개의 값을 map 컨테이너에 집어 넣고 iterator로 돌리면서 동일한 문서번호일 경우 Score를 더해서 (Score가 Key)가 되는 map에 넣으면 될 것이다.
확실히 돌아가긴 할 것이다. 문제는 지불해야 하는 비용이다. 문약 문서번호가 천만개씩 검색되었다면, Score가 Key가 되는 map에 집어 넣기 위한 공간만 10000000 * 8byte 가 된다. 게다가 맵에 집어 넣을 때마다, 정렬연산을 수행해야 한다. 좀더 나은 방법은 merged Sort된 결과를 Priory Queue에 집어 넣는 것이다. 관련된 내용은 Priority Queue를 읽어 보기 바란다. 많은 시간과 메모리를 절약할 수 있을 것이다.
학습을 통해서 문제 해결능력 혹은 IQ가 향상이 될까 ?
나는 왜 학습을 이야기 하는가
학습을 통한 효과에 대해서 참고할 만한 글이 있어서 링크를 건다.
http://agile.egloos.com/3111334
얘긴 즉슨, 더 좋아질 수 있다고 믿고 노력하고 경험하면, 더 좋아진다라는 얘기가 되겠다.
경험하고 고민하라
attachment:expert.jpg
당연하지만 카사노바의 자서전을 읽었다고 해서 카사노바가 되는건 아니다. 그걸 실제 생활에서 경험하고 어떻게 더 잘 적용시킬 수 있을 까 고민하는 사람이 제 2의 카사노바가 될 기회가 주어진다.
경험과 고민.. 그러니까 인간은 어떤 부분에 대해서 생각을 많이 하면 할 수록 그러한 류의 일을 더 잘할 수 있도록, 뇌세포가 조직화 된다고 한다. 뇌세포끼리 네트워크를 형성하게 되고, 그 네트워크를 자주 사용하게 되면, 전기적 신호가 더 잘 통하는 일종의 통로가 만들어진다고 한다. 더 빠르게 더 효율적으로 생각을 하게 된다는 얘기가 되겠다. 많은 훈련을 통해서 만들어지는 프로게이머도 그렇고 바둑선 수도 그렇고 스포츠 선수도 그렇다.
TV에서 프로게이머들이 대전하는 거 자주보고 빌드오더를 꿰고 있다고 해서 프로게이머가 될 수 있는 것은 아닐 것이다. 스티븐 아저씨의 시스템 프로그래밍 책을 봤다고, 전문 프로그래머가 되는게 아니듯이 말이다.
수학자체가 중요한게 아니다. 정말 중요한건 수학을 하게 됨으로써 얻는 수학적 사고력이란 말이 있다. 자료구조와 알고리즘 역시 마찬가지로 봐야 할 것이다.
좋은 알고리즘을 생각해 내기
전문가가 되기 위한 왕도는 없다고는 하지만, 효율적인 방법은 있을 것이다. 이에 대해서 나름 다루어보려고 한다.
아래는 꽤 유명한 문제로, 구글에서 입사지원자를 테스트하기 위해 사용한 것으로도 알려져 있다.
1부터 n까지의 정수중에서, 각 정수 속에 들어있는 숫자 '1'의 개수의 합을 f(n)이라 정의하고, f(n)=k라 하자.
* ex) f(13)=6 (=> 1,10,11,12,13) (총 1이 6개)
처음으로 n=k가 되는 n은 1이다.
두번째로 n=k가 되는 n을 구하라.
이 문제를 다양 하게 풀어보면서 어떻게 주어진 문제를 해결해야 되는지에 대해서 고민해 보도록 하겠다.
용감하게 풀기
컴퓨터의 파워를 믿는 단순한 방법으로 1부터 n까지 루프를 돌면서 계산하는 방식이다. 아마 몇시간은 돌려야 할 것으로 생각되는데, 돌리다가 그만 두었다. 단순한 알고리즘을 사용하고 있다.
#include <stdio.h>
#include <string.h>
int main(int argc, char **argv)
{
int i;
int n = 0;
int j = 0;
char buf[12] ={0x00,};
int value = 1;
while(1)
{
value++;
n = 0;
for(i = 1; i < value+1;i++)
{
sprintf(buf, "%d", i);
for (j = 0; j < strlen(buf); j++)
{
if(buf[j] == '1') n++;
}
}
if (value == n) break;
}
}
입력된 숫자보다 작은 모든 숫자에 대해서 1이 포함되어 있는지를 검사하는 코드다. 계산해야 되는양이 1+2+3+4+5.... 로 계속 늘어난다.
좀 더 똑똑하게 풀기 - 이미 계산된건 건너뛴다.
위의 코드는 문제를 풀 수는 있지만 매우 비효율 적이다. 위의 코드를 약간만 변경하는 정도로도 많은 이득을 가져올 수 있다. 이전에 찾아낸 1의 갯수를 계속 누적해서 더하는 방법을 사용하는 것이다. 값을 누적하게 되므로, 이전에 계산했던 것을 반복해서 계산하지 않아도된다. 아래의 코드를 테스트 해보면, 0.1 초 이내에 답을 찾아내는걸 확인할 수 있을 것이다.
#include <stdio.h>
#include <time.h>
int count = 0;
void find_one(int value)
{
int p_num = value / 10;
if (value % 10 == 1)
{
count++;
}
if (p_num > 0)
{
find_one(p_num);
}
}
int main()
{
clock_t stime, etime;
stime = clock();
int i = 1;
while(1)
{
find_one(i);
if (count == i)
{
if (i != 1) break;
}
i++;
}
etime = clock();
printf("%d = %d\n", i, count);
printf("Time = %.3fs\n", (double)(etime - stime)/CLOCKS_PER_SEC);
}
다음은 실행결과다
# ./findnum
199981 = 199981
Time = 0.030s
패턴을 찾아내라 : 일반적으로 사용가능한 알고리즘 생성
복잡한 현상도 일정한 규칙을 가지고 있다. 이 규칙을 찾아내면 현상에 대한 더 나은 인식이 가능해진다.
우선 어떤 패턴을 가지는지 확인해 보도록 하자.
이제 이것을 재귀호출 하면 될 것이다.
그러나 이걸로 완성된 것은 아니다. 각 재귀 호출에서 처음 숫자가 1이 아닌 것은 상관이 없겠지만, 1인 경우에는 모든 값이 늘어나는 것에 대해서 자릿수만큼 1 이 덤으로 발생하기 때문이다. 그러므로 처음 숫자가 1인 경우에는 다음과 같은 공식을 적용해야 할 것이다.
위의 공식을 적용시킨 결과에 현재 자리의 크기 만큼을 더해줘야 한다.
예를 들어 1100 이라면
(301+(1000*0 )+ (21+(100*1) ) + (0 + (10*1)) + (0 + 0)= 422 이다.
1120 이라면
(301+(1000*0 )+ (21+(100*1) ) + (12 + (10*1)) + (0 + 0)= 444 이다.
여기에서 하나의 가정을 더 세울 수 있다.
1로 시작되는 수 중에서 가장 큰 수를 포함하는 수는 처음을 제외한 모두가 9인 수이다. 그러므로 전부 검사할 필요가 없이 1로시작되는 가장 작은수와 큰수가 주어진 값보다 큰지를 확인한 후 계산하면 된다. 고로 위의 공식을 5번 적용한 후 우리가 원하는 숫자가 100000 ~ 199999 사이에 있음을 확인할 수 있게 된다.
f(100000) = 50001
f(199999) = 200000
이 방식은 두번째 방식에 비해서 그다지 효율적으로 보이지 않는다. 실제 시간테스트를 해도 두번째 방식보다 빠르진 않을 것이다. 그리고 공식이 지나치게 복잡한 감이 있다. 완벽한 공식을 만들어내기 위해서는 상당히 많은 테스트를 해야 할것이다. 이러한 단점이 있는 반면, 이 경우 일반적인 적용이 가능하다는 장점이 있다.
이 공식을 이용한 코드는 f(n) 이 얼마인지를 계산하라 라는 일반적인 문제는 훨씬 효율적으로 풀어낼 수 있을 것이다. 두번째 방식의 경우 n만큼 순환을 해야 하지만, 이 방식은 자릿수 만큼의 재귀호출만으로 값을 얻어올 수 있기 때문이다. 문제가 임의의 수 수천 수만에 대한 f(n)을 구하는 것이라면 더욱 효율적으로 작동할 것이다.
Key를 찾아라
문제를 쉽게 해결하는 또다른 방법은 범위를 좁혀서 하나의 핵심 Key를 찾는 것이다. 이것은 특히 복면산문제를 풀때 유용하다. 다음의 문제를 보기 바란다.
FORTY
TEN
+ TEN
=======
SIXTY
이 문제를 크게 확대해서 보면 답이 잘 눈에 들어오지 않는다. 핵심은 Y+N+N=Y 이부분이다. 이 식에서 Y가 결과값으로 나올려면, N이 0이 되어야 함을 알 수 있다. 이것을 알면 쉽게 문제를 해결할 수 있다.
이제 아래의 문제를 한번 풀어보기 바란다.
Solve this cryptic equation, realizing of course that values for M and E could be interchanged. No leading zeros are allowed.
WWWDOT - GOOGLE = DOTCOM
Contents
소개
컴퓨터는 충분히 빠르다 ?
그렇다고 알고리즘이 실질적으로 중요하나요 ?
학습을 통해서 문제 해결능력 혹은 IQ가 향상이 될까 ?
나는 왜 학습을 이야기 하는가
- http://agile.egloos.com/3111334
얘긴 즉슨, 더 좋아질 수 있다고 믿고 노력하고 경험하면, 더 좋아진다라는 얘기가 되겠다.경험하고 고민하라
좋은 알고리즘을 생각해 내기
1부터 n까지의 정수중에서, 각 정수 속에 들어있는 숫자 '1'의 개수의 합을 f(n)이라 정의하고, f(n)=k라 하자. * ex) f(13)=6 (=> 1,10,11,12,13) (총 1이 6개) 처음으로 n=k가 되는 n은 1이다. 두번째로 n=k가 되는 n을 구하라.용감하게 풀기
#include <stdio.h> #include <string.h> int main(int argc, char **argv) { int i; int n = 0; int j = 0; char buf[12] ={0x00,}; int value = 1; while(1) { value++; n = 0; for(i = 1; i < value+1;i++) { sprintf(buf, "%d", i); for (j = 0; j < strlen(buf); j++) { if(buf[j] == '1') n++; } } if (value == n) break; } }좀 더 똑똑하게 풀기 - 이미 계산된건 건너뛴다.
#include <stdio.h> #include <time.h> int count = 0; void find_one(int value) { int p_num = value / 10; if (value % 10 == 1) { count++; } if (p_num > 0) { find_one(p_num); } } int main() { clock_t stime, etime; stime = clock(); int i = 1; while(1) { find_one(i); if (count == i) { if (i != 1) break; } i++; } etime = clock(); printf("%d = %d\n", i, count); printf("Time = %.3fs\n", (double)(etime - stime)/CLOCKS_PER_SEC); }패턴을 찾아내라 : 일반적으로 사용가능한 알고리즘 생성
- 처음 숫자가 1인 경우 : (자릿수 * 10) + 1
- 처음 숫자가 1이 아닌 경우 : (10^(자릿수-1))+(n/10)*(자릿수-1))
이제 이것을 재귀호출 하면 될 것이다. 그러나 이걸로 완성된 것은 아니다. 각 재귀 호출에서 처음 숫자가 1이 아닌 것은 상관이 없겠지만, 1인 경우에는 모든 값이 늘어나는 것에 대해서 자릿수만큼 1 이 덤으로 발생하기 때문이다. 그러므로 처음 숫자가 1인 경우에는 다음과 같은 공식을 적용해야 할 것이다.- 위의 공식을 적용시킨 결과에 현재 자리의 크기 만큼을 더해줘야 한다.
예를 들어 1100 이라면 (301+(1000*0 )+ (21+(100*1) ) + (0 + (10*1)) + (0 + 0)= 422 이다. 1120 이라면 (301+(1000*0 )+ (21+(100*1) ) + (12 + (10*1)) + (0 + 0)= 444 이다. 여기에서 하나의 가정을 더 세울 수 있다.- 1로 시작되는 수 중에서 가장 큰 수를 포함하는 수는 처음을 제외한 모두가 9인 수이다. 그러므로 전부 검사할 필요가 없이 1로시작되는 가장 작은수와 큰수가 주어진 값보다 큰지를 확인한 후 계산하면 된다. 고로 위의 공식을 5번 적용한 후 우리가 원하는 숫자가 100000 ~ 199999 사이에 있음을 확인할 수 있게 된다.
f(100000) = 50001 f(199999) = 200000 이 방식은 두번째 방식에 비해서 그다지 효율적으로 보이지 않는다. 실제 시간테스트를 해도 두번째 방식보다 빠르진 않을 것이다. 그리고 공식이 지나치게 복잡한 감이 있다. 완벽한 공식을 만들어내기 위해서는 상당히 많은 테스트를 해야 할것이다. 이러한 단점이 있는 반면, 이 경우 일반적인 적용이 가능하다는 장점이 있다. 이 공식을 이용한 코드는 f(n) 이 얼마인지를 계산하라 라는 일반적인 문제는 훨씬 효율적으로 풀어낼 수 있을 것이다. 두번째 방식의 경우 n만큼 순환을 해야 하지만, 이 방식은 자릿수 만큼의 재귀호출만으로 값을 얻어올 수 있기 때문이다. 문제가 임의의 수 수천 수만에 대한 f(n)을 구하는 것이라면 더욱 효율적으로 작동할 것이다.Key를 찾아라
관련 문서
Recent Posts
Archive Posts
Tags