Problem Solving 의 정수론 분야 중 두 수의 최대공약수와 최소공배수를 이용한 문제들은 매우 자주 등장하는 편이다.
구하는 방법은 여러가지가 있는데...


방법 1) 소인수 분해 (Prime Factorization)
중학교 때 배우게 되는 소인수 분해를 이용한다
어떤 수의 모든 소인수를 구하는 방법은 소수구하기 알고리즘을 이용한다.

소인수분해는, a 와 b 를 소수로 나눌 수 있는 만큼 인수분해하여, 최대공약수는 두 수의 공통된 소인수들 중에서 차수가 최소인 값들의 곱이 되며, 최소공배수는 두 수의 모든 소인수들 중에서 차수가 최대인 값들의 곱이 된다.

#include <iostream> #include <algorithm> #include <vector> #include <cmath> #include <set> using namespace std; int prime[1000]; bool isprime(int n) { if( n <= 2 ) return true; if( n%2 == 0 ) return false; for( int a = 3; a*a <= n; a++ ) if( n%a == 0 ) return false; return true; } int main() { int a, b, i, n, cnt, tmp, lcm = 1, gcd = 1; vector<pair<int,int> > prime1, prime2; for( i = 2; i < 10000; i++ ) if( isprime(i) ) prime2.push_back(make_pair(i,0)); prime1 = prime2; cin >> a >> b; tmp = a, cnt = 0; while(tmp > 1) { n = prime1[cnt].first; while( tmp%n == 0 ) { tmp /= n; prime1[cnt].second++; } cnt++; } tmp = b, cnt = 0; while(tmp > 1) { n = prime2[cnt].first; while( tmp%n == 0 ) { tmp /= n; prime2[cnt].second++; } cnt++; } for( i = 0; i < prime1.size(); i++ ) { if( prime1[i].second > 0 && prime2[i].second > 0 ) { n = min( prime1[i].second, prime2[i].second ); gcd *= (int) pow((double) prime1[i].first, (double)n); } if( prime1[i].second > 0 || prime2[i].second > 0 ) { n = max( prime1[i].second, prime2[i].second ); lcm *= (int) pow((double) prime1[i].first, (double)n); } } cout << gcd << " " << lcm << endl; return 0; }
이 방법은 수학시간에 배운 직관적인 방법이고, 많은 이들에게 익숙하지만 위에서 보듯이 코딩으로 옮기기에는 꽤나 귀찮다는 단점이 있다. 또한 두 수 a, b 의 모든 소인수를 구해서 저장해 놓아야 하므로 별도의 메모리를 필요로 한다. ( 위의 코드는 10000 까지의 소인수에 대해서 구현한 코드 )


방법 2) Brute force
최대공약수의 정의를 이용하여, brute force 방법으로 직접 구한다.
즉, 두 수 a, b 를 나누어서 나머지가 0 이 되는 수들 중에서 가장 큰 숫자를 구하면 이 숫자가 최대공약수가 되며, 두 수 a, b 의 배수를 구하여 공통된 배수 중 가장 작은 숫자를 구하면 이 숫자가 최소공배수가 된다.
int main() { int a, b, i; cin >> a >> b; int n = min(a,b); int m = max(a,b); for( i = n; i >= 1; i-- ) if( a%i == 0 && b%i == 0 ) break; cout << "gcd = " << i << endl; for( i = m; i <= a*b; i++ ) if( i%a == 0 && i%b == 0 ) break; cout << "lcm = " << i << endl; return 0; }
위의 코드에서 만약 a, b 간의 공약수가 존재하지 않는 경우는 두 수의 최대공약수는 자연스럽게 1이 되며, a, b 간의 최소공배수 중 가장 클 가능성이 있는 수는 a*b 가 되므로 a*b 까지만 검사를 하면 된다.

이 방법은 최대 a*b 번의 연산을 해야 하므로,  a 와 b 가 커질수록 수행시간이 급격히 늘어난다.


방법 3) Euclid's algorithm - Using Recursion
사실 최대공약수와 최소공배수를 구하는 것은 고대 그리스의 수학자, 유클리드가 고안한 "유클리드 알고리즘"(Euclid's algorithm) 을 쓰면 간결하게 해결할 수 있다. 이 방법은 The Art Of Computer Programming 의 제 1장에도 소개된 바 있다.
a, b 중 큰 수를 a, 작은 수를 b 라 하자. 이 두 수의 최대공약수를 구하려면 a 를 b 로 나눈다. 이 연산을 한 후에 b 와 a%b 를 갖고 어느 한쪽이 0 이 될때까지 이 과정을 계속 반복한다. a%b 가 0 이 될 때의 b 가 바로 최대공약수가 된다. 이를 코드로 옮기면 다음과 같다.
int recursion(int a, int b) { if ( a%b == 0 ) return b; else return recursion(b, a%b); } int main() { int a, b; cin >> a >> b; int gcd = recursion(a,b); cout << "gcd = " << gcd << endl; cout << "lcm = " << (a*b)/gcd << endl; return 0; }

최대공약수와 최소공배수의 성질을 이용하면 아래와 같이
최소공배수 = (a*b) / 최대공약수
최대공약수 = (a*b) / 최소공배수
가 되므로, 최대공약수나 최소공배수 둘 중 하나만 구하면 나머지 하나는 쉽게 구할 수 있다.


방법 4) Euclid's algorithm - Using Iteration
방법 3 은 매우 간결한 코딩이 가능하지만, 재귀호출을 이용한다는 단점이 있다. 재귀호출은 상당히 비싼 작업이므로 이를 좀더 효율적인 iteration 버전으로 바꿀 수 있다. 실제로 방법 3은 a, b 가 매우 큰 서로소일 경우 답을 얻는데 꽤 오랜 시간이 걸리게 된다.
int gcd(int a, int b) { int tmp; while( b ) { tmp = a; a = b; b = tmp%b; } return a; } int main() { int a, b, g; cin >> a >> b; g = gcd(a,b); cout << "gcd = " << g << endl; cout << "lcm = " << (a*b)/g << endl; return 0; }


방법 5) Euclid's algorithm - Using Iteration, Original Version
유클리드가 처음 이 알고리즘을 제안했을때 사실은 modular 연산을 사용하지 않고, 아래와 같이 뺄셈 연산을 이용했다 한다.
int gcd(int a, int b) { if( a == 0 ) return b; while( b ) { if( a > b ) a = a-b; else b = b-a; } return a; } int main() { int a, b, g; cin >> a >> b; g = gcd(a,b); cout << "gcd = " << g << endl; cout << "lcm = " << (a*b)/g << endl; return 0; }  
방법5 는 방법 4와 비교하여, tmp 변수를 사용하지 않아도 되므로 메모리를 약간 절약한다는 장점이 잇다 ^^

유클리드 알고리즘의 증명 = 자세한 설명은 생략한다 Wikipedia 참고
유클리드 알고리즘의 시간복잡도 = O(n^2), n = length of integer bits, 그 이유는 n-bit 숫자 나눗셈 연산의 시간복잡도가 O(n(m+1)) 이기 때문이다 ( m 은 몫의 길이 )

3개 이상의 수에 대해 최소공배수와 최대공약수를 구할 때는, 두 수의 최소공배수와 최대공약수를 구한 후, 이 수와 나머지 수들에 대해 최소공배수와 최대공약수를 구하면 된다.

유클리드 알고리즘을 처음 보았을 때 무릎을 쳤던 기억이 난다. 그래서 최대공약수와 최소공배수에 대해서 글을 반드시 함 써보려 했는데... 위키피디아에 유클리드 알고리즘이 깔끔하고 멋지게 정리가 되어 있었다 ㅋ

이올린에 북마크하기(0) 이올린에 추천하기(0)

문제

- 모 웹사이트에서 다른 사람이 올린 내가 찍힌 사진을 다운받을 일이 생겼다.
그런데 사진의 장수가 한두장이 아니었다...

더구나 주인장은 센스넘치게 -0- 사진들을 압축으로 묶어서 올려 놓은게 아니고, 아래와 같이 한장 한장을 일일이 따로따로 서버 폴더에 걍 넣어놓고 링크만 걸어놨다.

http://a/1.jpg
http://a/2.jpg
http://a/3.jpg
...

Firefox 의 DownloadThemAll 과 같은 플러그인을 쓸수도 없었다. 왜냐하면 저 사진들이 링크걸린 페이지에는 썸네일만 올라가 있고, 해당 썸네일을 클릭해야 비로소 원본 사진이 리다이렉트로 보여지는 형태로 링크가 걸려있었기 때문이었다. ( 그래서 DownladThemAll 로 다운받으면 썸네일만 다운로드된다 )

수백장 되는 사진을 처음에는 "브라우저로 경로 실행" - "이미지 우클릭" - "다른이름으로 저장" 을 통해서 한장씩 다운받다가... 이 짓을 하고 있는 나 자신이 한심해졌다 -0-

그래서 구글링으로 뒤지다가... URLDownloadToFileA 라는 쌈박한 함수를 찾았다.

해결

URLDownloadToFileA 를 이용해서 아래처럼 특정 URL 의 연속된 파일들을 일괄적으로 다운받는 간단한 프로그램을 만들었다.
#include <urlmon.h> #include <sstream> #include <string> using namespace std; #pragma comment( lib, "urlmon.lib" ) int main() { stringstream out; string url, count, target; LPCSTR lurl, ltarget; for( int a = 1; a <= 100; a++ ) // 1.jpg 부터 100.jpg 까지 { out.clear(); out << a; out >> count; url = "http://a/" + count + ".jpg"; target = "c:\\" + count + ".jpg"; lurl = url.c_str(); ltarget = target.c_str(); if( URLDownloadToFileA( NULL, lurl, ltarget, 0, NULL) == S_OK ) { cout << "success" << endl; } else { cout << "fail" << endl; } } return 0; }

예외처리도 하나도 안되어있고 단순하게 만들었지만 내 요구사항은 완벽히 충족시켰다.  ㅋ
URLDownloadToFileA  이 함수만 잘 활용하면...
파이어폭스의 DownloadThemAll 과 같은 플러그 인도 쉽게 제작이 가능할 것 같다.

어쨌든 노가다 할 뻔한 일을 코딩으로 줄여서 흐믓 ㅋ

이올린에 북마크하기(0) 이올린에 추천하기(0)

요즘 재미있게 하는 것 중 하나가 바로 Google Code Jam 이다.
구글에서 개최하는 프로그래밍 경시대회라 할 수 있는데, 세계 각국의 프로그래머들과 경쟁하면서 나 자신을 돌아볼 수 있는 좋은 기회가 된다 할 수 있다. ^^

구글 코드잼에 대한 소개는 여기를 참조...

지난 7월 16일 예선전 격인 Qualification Round 가 열렸고, 7월 26 - 27일 양일에 걸쳐 1차 예선인 Round1 이 열렸다. 대략 7 천명이 참가하여 ( 실제 대회 등록한 사람 숫자는 이보다 많을 듯.. Qualificaiton Round 에서 한번이상 submit 을 한 사람 숫자가 7천이다 ) Qualification Round 을 6800 명 정도가 통과했고, Round1 을 2520 명이 통과했다. Round 2 에서는 다시 상위 1000 명이 Round 3 에 진출하며, Round3 에서 상위 500 명이 Semi-Final 인 온사이트 Local Contest 에 출전해서 세계 각국의 구글 지사에서 지역예선 최종전을 치룬다. 그리고 여기에서 선발된 최종 100 명은 11월 14일 캘리포니아 마운틴 뷰의 구글 본사에서 결승전을 치룬다.

2008 Google Code Jam Qualification Round 후기
2008 Google Code Jam Round1C 후기

원래 목표가 2 라운드 진출이었는데 목표 달성은 한 셈. ;)

올해의 Google Code Jam 은 어떤 개발 환경이든, 어떤 프로그래밍 언어를 사용하건 전혀 제약을 두지 않는 점이 특징이다. 참가자는 문제에서 주어지는 Input 에 대해서 올바른 Output 만 제출하면 된다.
또 한가지 재미있는 것은, 같은 문제에 대해 Small Input 과 Large Input 으로 나누어 문제 스펙을 달리 한다는 것. Small Input 에서는 Brute Force 로 그냥 풀수도 있는 문제를 Large Input 에서는 제한시간이 초과 되도록 디자인 되어 있다. 이런 부분은 정말 문제 디자인을 잘한것 같다. 알고리즘과 문제해결에 대해 해박한 지식이 없으면 Large Input 에서 제시하는 대용량 인풋 처리가 불가능해 진다. brute force 로 풀릴 수 있는 간단한 문제라 할지라도 입력 횟수가 커지면 새로운 방식으로 접근해야 한다는 것을 몸소 보여주는 좋은 문제들이다.

구글 코드잼 로고도 재미있다. 리프레시 할때마다 하단의 hello world 코드가 조금씩 달라지는데, 다양한 언어로 코드 잼에 참여할 수 있다는 것을 상징적으로 보여준다.

재미있게! 즐겁게! 달려보자 ;)

Perl / Python

C

C++

Java

이올린에 북마크하기(0) 이올린에 추천하기(0)

금년에도 어김없이 ACM-ICPC 의 시즌이 시작되었다. 
ACM = Association of Computing Machinary : 미국 컴퓨터학회,
ICPC = International Collegiate Programming Contest : 세계 대학생 프로그래밍 경시대회

Regional Contest 의 전초전 격이라 할 수 있는 각 지역의 국가별 / 학교별 예선들은 이미 전 세계적으로 한창 진행중이다. 2000 년 처음 치뤄진 이래 9 년째를 맞고 있는 ACM-ICPC 의 서울 지역 대회도 일정이 확정되었다.

ACM-ICPC Asia Regional Contest - Seoul, 대회 홈페이지

ACM-ICPC, 서울지역 대회 등록 페이지

ACM-ICPC Asia Regional Contest - Seoul 대회 스텝의 블로그



올해는 다른 해에 비해 각 지역별 예선의 참가팀 등록이 상당히 지지부진 한 편이다.
가장 큰 이유는 새로 리뉴얼 한 ACM-ICPC 공식 홈페이지가 너무 번잡스럽고 등록과정이 직관적이지 않기 때문이라고 생각한다. 여기에 각 지역별 대회의 일정이 아직 결정되지 않은 곳들도 너무 많다.

올해 ACM-ICPC 의 아시아 지역 대회는 총 15 개 지역에서 치뤄진다.  (TBA = To Be Announced )

이올린에 북마크하기(0) 이올린에 추천하기(0)

대회 홈페이지에 공개된 Final Standing 입니다.

이올린에 북마크하기(0) 이올린에 추천하기(0)

몇몇 컴파일러(VC++ 6.0, VC++ 2005 등... ) 에서 int main() 과 void main() 이 둘다 컴파일 에러없이 잘 동작하는 반면, dev C++, g++ 과 같은 컴파일러에서는 void main() 은 컴파일 에러를 낸다. 늘 습관처럼 int main() 을 쓰던터라 이번기회에 int main() 과 void main() 의 차이에 대해 자세히 찾아보았다.

우선 결론부터 말하자면 int main() 이 C/C++ 표준에 맞는 표기이며, void main() 은 잘못된 표기인 것이다.

int main()
{
 return 0;
}

위의 코드에서 return 0 의 역활은 main() 함수가 정상적으로 종료됨을 의미하는 exit(0) 을 호출하고 main() 함수를 종료하게 된다. exit 의 파라미터인 status 값은 컴파일러마다 약간씩 다르게 정의되어 있으나 일반적으로 0 이면 정상종료를 의미하며 0 이외의 숫자는 pre-defined 된 각각의 에러 타입을 의미한다.
참고로 Visual C++ 2005 에서는 이 status 가 다음과 같이 STDLIB.H 에 정의되어 있다.
#define EXIT_SUCCESS    0
#define EXIT_FAILURE    1

그러므로 void main() 으로 코딩을 한다면 설사 컴파일러가 컴파일 에러를 발생시키지 않는다 할지라도 프로세스 상에서는 main() 이 올바르지 않은 종료조건을 OS 에 리턴하고 자신을 종료할 가능성이 있게 된다.

왜 그렇다면 많은 서적과 예제에서 여전히 잘못된 표기인 void main() 을 쓰고 있을까?

초창기의 C 에서는 void 타입의 함수란 존재하지 않았으며, return 이 의미가 없는 경우에는 int 형 garbage 를 리턴하는 함수를 썼다 한다. 초기의 이러한 전통때문에 리턴값이 별 의미없는 int 형 함수들이 시간이 지나면서 프로그래머들의 취향에 따라 void 형 함수들로 고쳐 사용되었는데 이 과정에서 main() 함수도 void main() 으로 많이 사용되어진 것이 아닌가 추측된다. void main() 으로 실행할 경우 default 로 정상종료를 시키는 컴파일러들이 많아짐에 따라 프로그래머들은 별 문제 없이 이러한 코딩습관을 갖게 되었고, 사용자들이 이런 습관대로 쓰는 경우가 많아지자 컴파일러 제작사들도 사용자들의 습관에 따라 void main() 을 warning 이나 컴파일 에러없이 컴파일 되도록 만들게 되었다... 이것이 유력한 주장이다.

참고 : http://www.eskimo.com/~scs/readings/voidmain.960823.html

또다른 참고 : http://libe.tistory.com/2861180

사실 이건 그렇게 대단한 이슈는 아니지만 가끔 궁금해하는 사람들이 있어서 정리해 보았다. 약간 귀찮더라도 코딩은 표준대로 쓰는 것이 향후의 이식성을 고려할 때 좋을 것 같다 = )

이올린에 북마크하기(0) 이올린에 추천하기(0)

구글 공식 블로그에 불과 몇시간 전에 공개된 내용이다.

http://googleblog.blogspot.com/2007/09/our-plans-for-code-jam.html

즉, 구글이 조만간 Google Code Jam 을 개최하기 위해서 준비하고 있으며, 2003 년 부터 진행되었던 TopCoder 의 플랫폼을 활용한 방식이 아닌, 구글이 자체적으로 준비, 개발하는 새로운 프로그래밍 대회 형식이 될 것이라고 공개한 것이다.

Google Code Jam 이란?
- Google 이 주최, 후원하는 전세계 모든 프로그래머를 대상으로 한 대규모 프로그래밍 문제풀이 대회이다. 작년의 경우 전세계에서 약 2 만명이 참가하여, 최종 결선에 오른 100 명은 뉴욕에서 결선 대회를 치루었다. 구글에서 뉴욕까지 참가하는 대회 경비를 모두 후원하였으며, 1위에게는 1만 달러의 상금이 주어졌다.

작년의 경우 한국에서는 2 명이 최종 결선에 참가하여, 그 중 한명은 Google 에 입사하였고 나머지 한분도 알고리즘 문제풀이 대회에서 굉장히 유명한 활약을 하시는 분이다. ^^

이올린에 북마크하기(0) 이올린에 추천하기(0)

 2005 년 제 15회 JOLT 상 수상작.
컴퓨터 관련 서적으로 꽤 높은 순위로 꾸준하게 팔리고 있음.

많은 사람들이 읽고, 추천한 책이다. 꽤나 여러날을 걸려서 읽었는데, 읽은 소감은 한마디로 "과연 많은 사람들이 공통적으로 추천할만한 이유가 있다" 였다.

이 책은 조엘 스폴스키(Joel Spolsky) 라는 이스라엘 출신의 사업가겸 소프트웨어 엔지니어가 자신의 IT 분야의 경험과 기술적인 지식을 바탕으로 컴퓨터와 IT 업계전반에 걸친 여러가지 주제에 대해서 가볍고 재미있게 다루고 있다. 원래 이글 자체가 조엘의 블로그 (

이올린에 북마크하기(0) 이올린에 추천하기(0)

리퍼러를 분석해 보면 ACM-ICPC(세계대학생 프로그래밍 경진대회) 나 프로그래밍 경시대회 정보를 검색하다 이곳에 오는 분들도 꽤 되는 것 같다. 그래서 오늘은 TopCoder 에 대해서 소개하고자 한다.

프로그래밍 분야가 다른분야와 달리 어려운 점 중 하나는 프로그래머의 역량을 객관적수치로 평가하기가 어렵다는 것이다. 예를 들면 영어 능력은 토익/토플 과 같은 시험 성적을 통해 간접적으로 나마 평가가 가능하고, 운전 능력은 그 사람의 운전 경력과 무사고 몇년~ 이런 숫자를 통해 평가가 가능하다.

하지만 프로그래머의 코딩 실력을 평가해보려면 어떻게 해야 하는가?? 정보통신부 노임단가 기준대로 학력/경력/각종 자격증 소유 여부로 매겨야 하나?? 대답은 분명히 No 다. 프로그래밍 실력이 경력/학력/자격증과 정비례하지 않는 경우가 많다는 사실은 많은 현업 개발자들의 경험을 통해 입증되었다. ( IT 업계특성상 경력/학력이 높아질수록 엔지니어는 프로그래밍에서 멀어지고 아키텍트 or 관리자를 지향하게 된다. )

그래서 프로그래머의 역량을 측정하기 위한 방법중 하나로 도입된 것이 바로 알고리즘과 문제해결 능력을 묻는 코딩문제를 얼마나 잘 푸는지를 평가하는 방식이다. IOI (국제 정보 올림피아드) 나 ACM-ICPC 와 같은 알고리즘 문제풀이 대회를 학교와 교육기관에서 매년 많은 예산을 들여 개최하고, Google, MS 같은 IT 기업들이 개발자들의 입사시험 문제로 알고리즘 코딩 문제를 내는 것은 바로 이러한 이유 떄문일 것이다.

하지만 IOI 와 ACM-ICPC 는 소수의 학생들을 대상으로 한정되어 있고, UVa 나 PKU , USACO 와 같은 프로그래밍 연습 사이트도 존재하나 비영리 사이트인 관계로 정기적인 온라인 대회도 별로 없고, 학습자료나 풀이방법에 대한 친철한 가이드도 부족하여 체계적으로 프로그래밍 연습을 하기엔 불편한 점이 많다.

이 와중에 미국의 한 회사가 정기적으로 온라인상에서 전세계 모든 개발자들을 대상으로 알고리즘 문제풀이 대회를 개최하고, 결과를 Rating 시스템을 도입해 수치/등수화한 것이 있으니 바로 TopCoder 매치이다.

이올린에 북마크하기(0) 이올린에 추천하기(0)