Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

2012년 3월 31일 토요일

[Project Euler] 33. 이상한 방법으로 약분할 수 있는 분수 찾기

33. 이상한 방법으로 약분할 수 있는 분수 찾기

분수 49/98에는 재미있는 성질이 있습니다. 수학을 잘 모르는 사람이 분모와 분자에서 9를 각각 지워서 간단히 하려고 49/98 = 4/8 처럼 계산해도 올바른 결과가 됩니다.

이에 비해 30/50 = 3/5 같은 경우는 다소 진부한 예라고 볼 수 있습니다.

위와 같은 성질을 가지면서 '진부하지 않은' 분수는, 값이 1보다 작고 분자와 분모가 2자리 정수인 경우 모두 4개가 있습니다.

이 4개의 분수를 곱해서 약분했을 때 분모는 얼마입니까?
Click
우선 관계를 간단히 하기위해 10의 자리와 1의 자리를 분리하면 (10a+b)/(10b+c) = a/c 가 되고... 이를 좀더 분자 분모를 정리하고, 위에 조건에서 알 수 있는 a,b,c의 범위를 표시하면....
(10a+b)/(10b+c) = a/c
9ac + bc = 10ab
9a + b = 10ab/c

0 < a <= b < 10
0 < a < c < 10
위의 a,b,c범위에서 9a+b=10ab/c 를 만족하는 수를 구해 분모와 분자를 따로 곱한 후 최종적으로 구한 분모, 분자의 최대공약수를 구해서 분모/최대공약수 를 하면 원하는 결과를 얻을 수 있습니다.
<script language="Javascript" type="text/javascript">
function p033(){
    var d = 1, n = 1;       //d:분수  n:분모.
    
    for(var a=1; a<9; a++){
        for(var b=a; b<10; b++){
            for(var c=a+1; c<10; c++){
                if(9*a + b == 10*a*b/c){    //조건 만족시 분수 분모 곱해줌.
                    d *= 10*a + b;
                    n *= 10*b + c;
                }
            }
        }
    }
    
    var g = gcd(d,n);   //약분을 위해 최대공약수를 구함.
    alert(n/g);
}
</script>
최대 공약수는 이전에도 자주 사용 했던 유클리드 호제법을 이용했습니다.
<script language="Javascript" type="text/javascript">
function euclid(a,b){
 if (b == 0) return a;
 return euclid(b, a % b);
}
function gcd(a,b){
 return euclid(Math.max(a,b),Math.min(a,b));
}
</script>

2012년 3월 23일 금요일

[Project Euler] 32. 1~9 팬디지털 곱셈식을 만들 수 있는 모든 수의 합

32. 1~9 팬디지털 곱셈식을 만들 수 있는 모든 수의 합

1부터 n까지의 각 숫자를 한번씩만 써서 만들 수 있는 숫자를 팬디지털(pandigital)이라고 합니다.
예를 들면 15234는 1부터 5의 숫자가 한번씩만 쓰였으므로 1 ~ 5 팬디지털입니다.

7254라는 숫자는 그런 면에서 특이한데, 39 × 186 = 7254 라는 곱셈식을 만들 때 이것이 1 ~ 9 팬디지털이 되기 때문입니다.

이런 식으로 a × b = c 가 1 ~ 9 팬디지털이 되는 모든 c의 합은 얼마입니까?

(참고: 어떤 c는 두 개 이상의 (a, b)쌍에 대응될 수도 있는데, 이런 경우는 하나로 칩니다)

Click
진짜 대충 풀었네요.
사실 요 몇일 나름 바쁜 사정으로 인해 Project Euler 하루 한개씩 올리기로 한 개인 과제를 쉬기로 했습니다. Project Euler를 안하니 블로그 업뎃이 뜸하기도 하고 해서 오랜만에 한문제 풀었는데 좀 귀찮은 문제가 걸렸네요. 머리에서 더 좋은 방법이 떠오르지만 제대로 구현은 안되고 딴 생각만 나고....
<script language="Javascript" type="text/javascript">
function p032_in(){
    var n = 9;
    var sum = 0;
    for(var c=1234; c<=9876; c++){
        /* 팬디지털 체크를 위한 변수들 선언. */
        var check = true;
        var nums = new Array();
        for(var i=1; i<=n; i++)
            nums[i] = true;
        nums[0] = false;

        /* c값이 팬디지털에 적용되는지 확인. */
        var temp1 = c;
        do{
            var temp2 = temp1%10;
            if(!nums[temp2]){
                check = false;
                break;
            }
            nums[temp2] = false;
            temp1 = parseInt(temp1/10);
        }while(temp1!=0);
        if(check){                //c값이 팬디지털를 만족하면 a값 구함.
            for(var a=1; a<=98;a++){
                check = true;

                /* c값에 사용된 숫자 채움. */
                for(var i=1; i<=n; i++)
                    nums[i] = true;
                temp1 = c;
                do{
                    var temp2 = temp1%10;
                    nums[temp2] = false;
                    temp1 = parseInt(temp1/10);
                }while(temp1!=0);
                /*a값이 팬디지털을 만족하는지 확인.*/
                temp1 = a;
                do{
                    var temp2 = temp1%10;
                    if(!nums[temp2]){
                        check = false;
                        break;
                    }
                    nums[temp2] = false;
                    temp1 = parseInt(temp1/10);
                }while(temp1!=0);
                if(check){        //a,c값이 모두 팬디지털을 만족한다면 b값을 구함.
                    check = true;
                    var b = c / a;
                    
                    if(b-parseInt(b)!=0){ //c가 a로 딱 나눠떨어지는지 확인.
                        check = false;
                        continue;
                    }
                    //b값이 팬디지털을 만족하는지 확인.
                    temp1 = b;
                    do{
                        var temp2 = temp1%10;
                        if(!nums[temp2]){
                            check = false;
                            break;
                        }
                        nums[temp2] = false;
                        temp1 = parseInt(temp1/10);
                    }while(temp1!=0);
                    if(check){
                        //모든 수를 사용했는지 확인.
                        for(var i=1; i<=n; i++){
                            if(nums[i]){
                               check = false;
                                break;
                            }
                        }
                        //최종적으로 팬디지털을 만족한다면 c값을 더해 줌.
                        if(check)
                            sum += c;
                    }
                }
                if(check)
                    break;
            }
        }
    }    
    
    alert(sum);
}
</script>

2012년 3월 21일 수요일

[잉여모드] 단순 Image Blending 실험.

검색 중에 우연히 발견한 블로그에서 Image Blending에 관한 글을 보고는 한번 재미삼아 HTML5 Canvas를 이용해 구현해 봤습니다.
따로 논문을 읽고 한 것은 아니고, 어떻게 하면 마스크 이미지 없이 자연스러운 합성 효과를 얻을 수 있는 편법이 없을까... 라는 것이 주요 고민.
가장 기본이 되는 법칙은 위 블로그에도 나와 있듯이

1. 배경과 만나는 부분은 배경과 같은 색을 사용한다.
2. 배경과 만나지 않은 부분은 최대한 색상차가 나지 않도록 메운다.


입니다.
사용한 이미지는 Image Blending에서 자주 사용하는 아래 두 이미지.


가장 먼저 사용한 편법은 정직하게, 외곽은 배경이미지 그대로 칠하고, 그 안쪽은 외곽색과의 차이를 얻어서 이전 색에 더해주는 방법.
dx = src[i][j] - src[i][j-1];
dy = src[i][j] - src[i-1][j];

result[i][j] = ((result[i][j-1] * dx) + (result[i-1][j] * dy))/2;
간단하게 좌측 상단에서 시작하는 것만 해 봤는데 보는데로 자연스러운 효과는 좋은 것 같으나 시작부분이 잘못되면 엉뚱한 결과가 나오는 것을 발견.
거기다 가운데 어두운 부분을 통과하면 잘 나오던 부분도 엉뚱한 결과가 나오는 군요.
탐색 시작을 사각 네 귀퉁이에서 시작하면 좀 더 나은 결과가 나올 수도 있지만 일단 이 방법은 보류.


다음 방법은 같은 x,y외곽 점을 기준으로 기준점과 현재 점의 차이를 얻어, 그 차이를 배경에 더해주는 방법.
top = src[i][0] - src[i][j];
bottom = src[i][h] - src[i][j];
left = src[0][j] - src[i][j];
right = src[w][j] - src[i][j];

result[i][j] = back[i][j] + (top*((h-j)/h) + bottom*(j/h))/2 + (left*((w-i)/w) + right*(i/w))/2;
외곽색의 차이에 따라 새로 붙인 이미지에 가로 혹은 세로의 줄이 가고, 외곽부분이 매끄럽지 않은 현상이 발견되네요.


다음 방법은 아예 고정점을 기준으로 잡고 해당 고정점과의 차이를 얻어, 그 차이를 배경에 더해주는 방법입니다.
tl = src[0][0] - src[i][j];
tr = src[w][0] - src[i][j];
bl = src[0][h] - src[i][j];
br = src[w][h] - src[i][j];

result[i][j] = back[i][j] + (tl*((h-j)/h)*((w-i)/w) + tr*((h-j)/h)*(i/w) + bl*(j/h)*((w-i)/w) + br*(j/h)*(i/w));
확실히 2번째보다 줄무늬도 없고 자연스러워졌지만 기준점으로 잡은 고정점과 차이가 많이나는 외곽부분의 매끄럽지 않은 현상이 더욱 두드러지는 군요.


다음 방법은 단순히 외곽일수록 배경색을 칠하고 내부일 수록 소스이미지의 색을 칠하는 방법.
a = ((h-i)/h)*(i/h)*((w-j)/w)*(j/w) * 16;

result[i][j] = back[i][j]*(1-a) + src[i][j]*a;
연결은 자연스럽지만 물색이 티가 나게 바뀌는 것을 알 수 있습니다.


간단히 생각나는 것은 모두 해봤는데요. 만족할 만한 성과는 없군요.
그렇다면 이게 끝이냐... 하면. 그것은 아니죠.
성질이 약간 다른 1번을 제외한 2,3,4번을 간단하게 혼합해 봅니다.
top = src[i][0] - src[i][j];
bottom = src[i][h] - src[i][j];
left = src[0][j] - src[i][j];
right = src[w][j] - src[i][j];

tl = src[0][0] - src[i][j];
tr = src[w][0] - src[i][j];
bl = src[0][h] - src[i][j];
br = src[w][h] - src[i][j];

result[i][j] = back[i][j] 
    + ((top*((h-j)/h) + bottom*(j/h))/2 + (left*((w-i)/w) + right*(i/w))/2
    +  (tl*((h-j)/h)*((w-i)/w) + tr*((h-j)/h)*(i/w) + bl*(j/h)*((w-i)/w) + br*(j/h)*(i/w)))/2;

a = ((h-i)/h)*(i/h)*((w-j)/w)*(j/w) * 16;

result[i][j] = back[i][j]*(1-a) + result[i][j]*a;
100%라고는 못하겠지만 꽤 만족스러운 결과가 나왔습니다.


어느정도 효과는 얻었지만 완벽한 것은 아니겠죠. 자세히 보면 부자연스러운 부분도 보이고, 합성하고자하는 물체가 외곽으로 접해있다면 지워지는 결과가 나올 수도 있을 것입니다.
2,3,4번 외에 1번은 효율적으로 적용하면 더욱 뛰어난 결과가 나올 수도 있을 것 같구요.
아무튼 이번 시도는 여기까지.
다음에 기회가 닿는다면 논문도 살펴보고 좀더 전문적으로 접근 해 봐야겠습니다.

2012.4.3. updated
이전에 결과가 만족스럽지 않아 다른 방법을 생각해 보던 중 이번에는 좀 더 만족스러울만한 방법을 찾아 냈습니다.
방법은 1번 방법을 응요한 것이구요. 이때 모든 값을 이전 점을 기준으로 해서 변환하는 것이 아닌 배경과 일정 값 이상이 차이 날때만 주변 점들과의 차이만큼 더해주도록 하였습니다.
top = src[i][0] - src[i][j];
if(Math.abc(src[i][0]-src[i][j])< criterion) {
    result[i][j] = back[i][j];
}
else {
    dx = src[i][j] - src[i][j-1];
    dy = src[i][j] - src[i-1][j];

    result[i][j] = ((result[i][j-1] * dx) + (result[i-1][j] * dy))/2;
}
결과는 꽤 만족스럽습니다. 따로 논문등은 찾아보지 않았지만 생각나는 대로 간단히 구현한 것에서는 꽤 괜찮게 나온걸로 보입니다.

결과를 확인하고 싶으신 분은 아래서 TEST가 가능합니다.

이곳에 소스 파일을 드랍해 주세요...

이곳에 배경 파일을 드랍해 주세요...

아래 Canvas에서 Mouse Click & Drag로 소스 이미지의 위치를 조정 할 수 있습니다.

1. 인접한 점과의 색 차이

2. 가로세로 외곽 점과의 색 차이

3. 고정 점과의 색 차이.

4. 외부와 내부의 정도

5. 2,3,4 혼합

6. 배경과 값 차이에 따른 분기

2012년 3월 17일 토요일

[G+ 번개] 워커힐 딸기 디저트 뷔페

세번째 참석한 Google + 번개.
오늘의 번개 장소는 쉐라톤 그랜드 워커힐 호텔에서하는 딸기 뷔페.

뷔페 시작 시간인 2시에 맞춰 아침 일찍부터 길을 나서며 Google + 로 서로간의 소식을 확인한다.
거리가 멀어 일찍 출발하다보니 1시간이나 일찍 도착, 하지만 이내 Google + 로 서로간의 위치를 확인해 뒤늦게 오신 다른 인원들과 합류하고...
그리고 합류하지 못한 분들은 각자 시간에 맞춰 호텔에 도착.

처음 뵙는 분들도 계시고, 한번씩 만났던 분들도 계시고...
하지만 모두 Google + 에서 친하게 지내던 분들이라 금세 화기애애해진다.

Google + 번개 기념
먼저 차, 커피, 쥬스 중에서 음료를 고르고 시작한다.
쥬스는 리필이 안되고, 긴 시간동안 딸기와 커피만 먹기는 좀 그래서 일까?
음료는 자연스레 차로 통일.
음료도 골랐겠다 이제 본격적으로 뷔페를 즐기는 시간.





이런 저런 대화를 나누며 각종 딸기로 만든 디저트들을 먹는 시간.
딸기로 만든 디저트들이다 보니 너무 단것이 많아서일까?
가장 인기 있었던 것은 생딸기와 딸기샌드위치.

딸기샌드위치를 모두 쓸어오는 민폐를 끼치는 등 즐겁게 몇시간을 먹고나니 모두 배가 슬슬 불러오시는 듯, 자연스레 디저트보다는 차를 마시며 담소를 즐기기 시작.


마침 한분이 준비해온 선물을 나눠주신다.
감사합니다. S.H님 ^^


즐거운 시간을 보내고 어느덧 5시.
뷔폐시간도 끝나가니 계산을 하고 밖으로 나와 소화도 시킬겸 바람도 쐴겸 도보로 역까지 이동.
저녁 노을을 즐기며 광나루역에 도착하고, 다음 장소는 건대로 결정. 2팀으로 나눠 택시를 타고 다시 건대로 이동.


저녁은 현경 건대점에서 짬뽕의 매운 맛으로 단것에 지친 속을 달래고...


다음으로 이동한 곳은 Google + 의 한분으로 인해 Google + 와 인연이 많은  카페베네.
마침 새로 오신 한분과도 인사를 나누고, 즐거운 담소시간.
주로 이야기는 모임이 모임이다보니 Google + 에 대한 이야기들...
즐겁게 시간을 보내다보니 어느덧 11시가 넘어가고, 늦은 시간 각자 헤어져 집으로 귀가.

하지만 시골에 집이 있는 나는 차가 끈기고,
마침 카페베네에 계시던 다른 구플러 분들이 불러주신 덕분에 그분들과 합류해 함께 행아웃을 하며 밤을 보냈다... 그리고 아침 첫 기차를 타고 집으로....


밤을 지센 여파일까... 졸다 깨서 목적지를 2개역을 남기고 내리기도 하고...
간신히 양평에 도착.


마침 양평은 5일장 준비로 분주하네요.
시장을 지나 버스를 기다려 타고 다시 집으로....
정확히 하루만에 복귀.

즐거운 만남, 즐거운 이야기, 즐거운 기억이 함께했던 시간...
함께했던 모두 감사드립니다.^^

2012년 3월 16일 금요일

[Google API] Google+ ID Card





구글 API를 건드려보는 것 중의 하나로 제가 자주 하는 SNS인 Google+의 API를 이용한 무엇인가를 만들어 볼 수 있지 않을까하고 생각을 하던 중 Google+의 프로필정보를 가지고 ID카드를 만들어 주는 사이트를 보고 간단하게 따라서 구현을 해봤습니다.

해당 사이트는 언어설정이 'en_US'로 되어있어 한글이 안나오는 점도 한몫 했구요.
그리고 이왕 만드는 김에 디자인도 Google+의 디자인을 따라서 바꿔봤습니다.

테스트하는 방법은 간단하게 위에 Text box에 자신의 Googl+의 ID Number를 입력해주시면 됩니다.
개인의 프로필에 들어가 주시면 나오는 숫자를 입력해 주시면 되는데요.

예를 들면 제 프로필 주소인 https://plus.google.com/u/0/103718751107954683981/posts 에서 '/0/'와 '/posts'사이에 진하게 표시된 부분의 숫자를 입력해 주시면 됩니다.

입력하시면 자신의 개인정보 공개정도에 따라 public 공개인 정보들을 읽어와서 이미지의 정보와 사진이 변화하게 됩니다.

안타까운 것은 위의 Canvas를 이미지로 전환이 안되는 군요.
Dom Exception 18 에러가 뜨는데 알아보니 '동일 원본 정책'위반으로 canvas는 현재 문서와 다른 도메인의 리소스가 들어가면 이에대한 데이터 수정등을 차단하는 것이라고 합니다.
이 에러에 대해 자세한 정보를 보고 싶으신 분은 http://zziuni.pe.kr/zziuni/580 주소의 블로그를 확인하면 좋을 듯 합니다.

구현은 callback 함수를 통해 json객체를 받아 구현했는데 Google+ API는 Google API Key를 등록해야 하는 군요.
API Key등록은 https://code.google.com/apis/console/ 의 API Access에서 가능하고, 해당 API를 사용할 주소를 입력해야 사용하실 수 있습니다.
Test용으로는 Server API Key에 '192.168.12.0/23'로 등록을 해 주시면 가능하네요.


이때 키 등록을 했다고 바로 사용할 수 있는게 아니라 Services탭에 가셔서 사용하고자 하는 서비스를 on으로 켜주셔야 사용하실 수 있습니다.


Google +의 API는 https://developers.google.com/+/api/ 를 보시면 되구요.
이 중 Profile 정보를 가져오는 것은

https://www.googleapis.com/plus/v1/people/' + id + '?key=' + apikey + '&callback=' + callback

와 같은 방법으로 얻고자하는 user의 id와 개인 apikey, 그리고 callback 함수를 입력해 사용하면 됩니다.

[Project Euler] 31. 영국 화폐 액면가를 조합하는 방법의 수

31. 영국 화폐 액면가를 조합하는 방법의 수

영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다.

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)
이 동전들을 가지고 2파운드를 만드는 방법은 다양할 것입니다. 예를 하나 들면 이렇습니다.

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
2파운드를 만드는 서로 다른 방법은 모두 몇가지나 있습니까?
Click
http://blog.mycila.com/2009/06/project-euler-problem-31.html 블로그에서 본 방법이 단일 경우에 대해서는 최선의 방법일 듯하네요. 아래 공식을 이용한 방법인데.... 200 = 200*a + 100*b + 50*c + 20*d + 10*e + 5*f + 2*g + 1*h
<script language="Javascript" type="text/javascript">
function p31(){
  var count = 2; // for a = 1, a = 0 and b = 2`
  for (var b = 0; b <= 1; b++)
   for (var c = 0; 100 * b + 50 * c <= 200; c++)
    for (var d = 0; 100 * b + 50 * c + 20 * d <= 200; d++)
      for (var e = 0; 100 * b + 50 * c + 20 * d + 10 * e <= 200; e++)
        for (var f = 0; 100 * b + 50 * c + 20 * d + 10 * e + 5 * f <= 200; f++)
          for (var g = 0; 100 * b + 50 * c + 20 * d + 10 * e + 5 * f + 2 * g <= 200; g++)
            count++;
  return count;
}
</script>
하지만 개인적으로 단일 방법보다는 범용적인 방법을 더 좋아하므로 동적 계획법(Dynamic Programming)쪽에 더 점수를 주어봅니다.
동적계획(動的計劃, dynamic programming)은 어떤 알고리즘이 부분 문제 반복과 최적 기본 구조라는 특징을 가지고 있을 때, 이 알고리즘의 실행시간을 줄이는 방법이다. 수학자인 리처드 벨만이 1953년에 '동적계획'이라는 용어를 만들었다.
제가 구현한 것은 동전의 종류, 배열, 원하는 n값에 모두 적용 되도록 구현해 봤습니다.
0원을 구하는 경우는 아무것도 선택하지 않는 1가지 방법 뿐.
1개의 동전으로 n원을 구할 수 있는 경우의 수는 1 or 0이다.
이때 동전 k가 하나 추가 되면, k가 없을 때의 경우의 수에 k를 하나 이상 선택한 경우의 수를 더해 주면 된다.
즉 새로운 newcnt[n] = oldcnt[n] + newcnt[n-k]가 된다.

이때 n-k가 n보다 클 경우. 역시 마찬가지로 k를 선택하지 않은 경우와 k를 하나 이상 선택한 경우를 더해야 한다.
이렇게 n-ak를 해 내려가면 n%k값에 도달하게 되고 이 수는 k값보다 작으므로 k를 선택하지 않은 oldcnt[n%k]와 동일한 값이라는 것을 알 수있다.
그렇다면 이걸 다시 역으로 타고 올라가면서 구하면 newcnt[n]값을 구할 수 있다.

같은 방법으로 동전을 추가해 나가면서 구하면 최종 값을 구할 수 있다.

위 방법을 효율적으로 하기위해 0~n까지 배열을 선언하여 1개의 동전 구할 수 있는 경우의 수로 초기화 한 후, 새로 동전을 추가 할때마다 새로운 동전의 가치 k부터 cnt[i] = cnt[i] + cnt[i-k]를 해나가면 원하는 수를 구할 수 있음.
<script language="Javascript" type="text/javascript">
function countCombineMoney(money,n){
    var cnt = new Array(); //i 값을 만들 수 있는 경우의 수.

    cnt[0] = 1; //0원을 만들 수 있는 경우의 수는 아무것도 선택하지 않은 1가지 경우뿐.
    for(var i=1; i<=n; i++) //동전 1개로 구할 수 있는 경우의 수는 1 or 0(불가)
        if(i%money[0] == 0)
            cnt[i] = 1;
        else
            cnt[i] = 0;
    
    var max = 0;
    for(var i=1; i<=money.length; i++)
        for(var j=money[i]; j<= n; j++)
            cnt[j] += cnt[j-money[i]];    //newcnt[n] = oldcnt[n] + newcnt[n-k]

    return cnt[n];
}
</script>

2012년 3월 14일 수요일

[Project Euler] 30. 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은?

30. 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은?

각 자리의 숫자를 4제곱해서 더했을 때 자기 자신이 되는 수는 놀랍게도 단 세 개밖에 없습니다.


1634 = 1⁴ + 6⁴ + 3⁴ + 4⁴
8208 = 8⁴ + 2⁴ + 0⁴ + 8⁴
9474 = 9⁴ + 4⁴ + 7⁴ + 4⁴

(1 = 14의 경우는 엄밀히 말해 합이 아니므로 제외합니다)

위의 세 숫자를 모두 더하면 1634 + 8208 + 9474 = 19316 입니다.

그렇다면, 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은 얼마입니까?

Click
깊이 탐색으로 탐색해 내려가면서 현재 수가 각자리수를 5제곱해서 나온 값보다 작으면 새로운 수를 더해 줄 수 있다고 판단 *10을 한 후 1에 자리에 새로운 수를 더해주고...
현재수가 각자리수를 더한 수보다 크다면 더이상 수를 더해주면 안돼니 깊이 탐색을 끝내는... 분기 한정 가지치기 깊이탐색법입니다.
분기 한정법(分岐限定法, Branch and bound)은 다양한 최적화 문제를 풀기 위한 범용 알고리즘이다. 주로 이산 최적화나 조합 최적화 문제를 풀 때 쓴다. 분기 한정법은 모든 후보해를 체계적으로 늘어놓으면서 최적화할 수치의 상한과 하한을 추정, 가망 없다는 판정이 나는 해를 제거해 나간다. 제거하는 해에서 파생되는 해는 살펴보지 않기 때문에 불필요한 시간 소모를 줄이게 된다.
이 방법은 A. H. 랜드와 A. G. 도이그가 1960년에 선형 계획법을 풀기 위해서 제안하였다.
<script language="Javascript" type="text/javascript">
/* 분기한정 가지치기 깊이 탐색. */
function branchNbound(nums,n,sum){
    if(n > sum) //분기 한정. (n이 각 자리수의 5제곱의 합보다 크면 탐색실패.)
        return 0;
    else if(n == sum && n!=1) //찾은 결과 return.
        return sum;
    
    //0~9까지의 경우에 대해 가지를 탐색.
    var nsum = 0;
    for(var i=0; i<10; i++){
        var tn = n*10 + i;
        var tsum = sum + nums[i];
        nsum += branchNbound(nums, tn, tsum);
    }
    return nsum;
}
function p030(n){
    //input으로 들어 온 n값에 대한 각 n제곱값들을 저장.
    var nums = new Array();
    for(var i=0; i<10; i++)
        nums[i] = Math.pow(i, n);
    
    //가지 탐색 시작.
    var sum = 0;
    for(var i=0; i<10; i++)
        sum += branchNbound(nums, i, nums[i]);
    
    return sum;
}
</script>

[Project Euler] 29. 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b로 만들 수 있는 a^b의 개수

29. 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b로 만들 수 있는 a^b의 개수
2 ≤ a ≤ 5 이고 2 ≤ b ≤ 5인 두 정수 a, b로 만들 수 있는 ab의 모든 조합을 구하면 다음과 같습니다.


22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=3125

여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 숫자가 됩니다.


4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

그러면, 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b를 가지고 만들 수 있는 ab는 중복을 제외하면 모두 몇 개입니까?
Click
brute-force로 하면 비효율적이긴 하지만 금방 구현할 수 있었을 텐데 좋은 방법 찾아본다고 고생을 했네요. 아무튼.... 결국 찾았습니다. 고생의 원인은 역시 사소한 실수....
2<=a<=n, 2<=b<=n 으로 만들 수 있는 숫자는 총 n-1개.

이 때 a^(b)가 이전에 구한 어떤 수 c^(d)과 중복이 된다면.
그 말은 a와 c 모두 어떠한 수 i의 제곱수라는 것이다.

이때 a = i^(t), c = i^(j) 라고 한다면. a^(b)와 c^(d)는 (i^(t))^(b) , (i^(j))^(d)가 되고.
이때 t*b, j*d가 같을때 중복이 됩니다.
즉. t,j의 공배수일때 중복이 된다는 것을 알 수 있습니다.

그리고 위에 두가지 내용을 가지고 구현할 것을 종합해 보면....

1. 100까지의 배열을 만들어 배수값들을 저장해 둔다.
2. 현재 값이 제곱으로 만들어 지는 수가 아닐 경우 sum에 n-1값을 더해준다.
3. 현재 값이 어떠한 수 k에 t제곱일 경우.    
    2부터 t까지 작은 수의 경우만 중복의 수를 판단하여 n-중복수를 sum에 더해준다.

3가지 단계에 의해 구현.
그리고 아래가 위에 알고리즘을 정리한 코드.
<script language="Javascript" type="text/javascript">
function euclid(a,b){
 if (b == 0) return a;
 return euclid(b, a % b);
}
/* 최대 공약수 */
function gcd(a,b){
 return euclid(Math.max(a,b),Math.min(a,b));
}
function p029(n){
   var sum = 0;
   var square = new Array();       //어떠한 수의 제곱값으로 나타낼 수 있는지를 저장하는 배열.
   for(var i=2; i<=n; i++){
      if(isNaN(square[i])){       //어떠한 수의 제곱값인지 판단.
         sum += n-1;
         var temp = i*i;
         for(var j=2; temp<=100; j++){   //현재 수의 제곱 값들을 배열에 저장.
            square[temp] = j;
            temp *= i;
         }
      }
      else{                     //어떠한 수의 제곱으로 나타내어지는 수의 경우.
         sum += n;
         var arr = new Array();      //중복을 판단하기 위한 배열.
         for(var j=1; j< square[i]; j++){
            var p = square[i] / gcd(square[i],j); //p 현재값을 만드는 지수 중 j지수와 공약수를 제외한 수.
            var q = j / gcd(square[i],j);   //q j지수 중 현재값을 만드는 지수와의 공약수를 제외한 수.
            var r = q;
            for(var k=p; k<=n; k+=p){               //k를 p씩 증가. 즉 두 지수 t,j의 공배수를 찾음.
               if(arr[r] != true){
                  sum--;
                  arr[r] = true;
               }
               r += q;
            }
         }
      }
   }
   return sum;
}
</script>

2012년 3월 12일 월요일

[Project Euler] 28. 1001×1001 나선모양 행렬에서 대각선 원소의 합은?

28. 1001×1001 나선모양 행렬에서 대각선 원소의 합은?
숫자 1부터 시작해서 우측으로부터 시계방향으로 감아 5×5 행렬을 만들면 아래와 같이 됩니다.

21 22 23 24 25
20 07 08 09 10
19 06 01 02 11
18 05 04 03 12
17 16 15 14 13

여기서 대각선상의 숫자를 모두 더한 값은 101 입니다.

같은 방식으로 1001×1001 행렬을 만들었을 때, 대각선상의 숫자를 더하면 얼마가 됩니까?

Click

일단 푸념하고 시작합니다.
아.... 난 수학을 하는 것인가 프로그래밍을 하는 것인가.......
푸념 끝. 그럼...

nxn 행렬에 대해 대각선 값이
1부터 시작, 2,2,2,2, 그리고 4,4,4,4, ..... (n-1),(n-1),(n-1),(n,1) 씩 더해주며 증가.
우측 상단으로 가는 대각선은 1²,3²,5²......n²으로 증가.
이런 패턴들을 정리하면... k껍데기에 있는 대각선 들의 값은

 k²+ (k²- (k-1)) + (k²- 2(k-1)) + (k² - 3(k-1)) = 4k² - 6k + 6 (k=1 제외)

으로 나타낼 수 있다.
이제 이 껍데기들을 k=3부터 k=n까지 k=k+2씩 더해준 후 마지막에 1만 더해주면 결과가 나온다.
그런데 여기서 한번 더 보면.
k값을 (i=1부터 i=(n-1)/2까지 i++, k = 2*i+1)로 바꿀 수 가 있다. 이를 다시 위에 식에 적용하면.

 4(2*i+1)²- 6(2*i) + 6 = 16*i²+ 4i + 1

이 되고. 이 수들을 더한 값을 시그마(∑)로 나타내면.. ((n-1)/2 = t로 놨을때..)

 (i=1 부터 i = ((n-1)/2) = t 까지) ∑(16*i²+ 4i + 1) = 16∑i²+ 4∑i + 4∑1
                                            = 16*(t*(t+1)*(2t+1)/6) + 4*(t*(t+1)/2)) + 4*t
                                            = (16t³)/3 + 8t²+ (8t)/3 + 2t²+ 2t + 4t
                                            = (16t³)/3 + 10t²+ (26t)/3
                                            = (16t³ + 30t²+ 26t)/3

이제 다시 t를 (n-1)/2로 하면... 뭔가가 나오겠지만 여기서는 귀찮으니 그냥 구현.
마지막에 위에서 제외한 예외의 경우 k=1일때 값 1을 더해주는 것도 잊지 않고!!

사실 그냥 손계산은 여기서 계산하는게 더 쉽습니다.
한단계 더 나간다고 뭐 그렇게 어려운 것은 아니지만... 여기서 n값.. 1001에 -1 후 /2를 하면 500이 나오고... 500을 위에 식에 대입하면 끝....
물론 계산기의 힘을 동원하는게 여러모로 편하지만요....

물론 컴퓨터가 계산하는데는 한단계 더 나간것까지 풀어주는게 더 좋겠지만 그래봐야 아주아주아주아~ 주 극미한 차이이니 pass.
사실 이정도만 해도 코딩 두줄로 끝나니.....
<script language="Javascript" type="text/javascript">
function p028(n){
    var t = (n-1)/2;
    alert((16*t*t*t + 30*t*t + 26*t)/3 + 1);
}
</script>

[Blogspot] 구글 지도를 이용한 블로그 지도 만들기

이전 포스트에 Google Map API를 다뤄 본 것에 이어서, 구글맵과 블로거의 feed를 이용해 제 블로그 상단 페이지에서 있는 Blog Map를 만들어 봤습니다.

Blog Map에 들어가시면 아래와 같이 구글 지도가 보이실 텐데요.



기본 위치는 서울. 그리고 지도 위에는 블로그 post에 설정한 위치가 마커에 표시되구요.
마커를 선택하면 해당 포스트 제목과 Thumbnail, 그리고 약간의 포스트 내용이 써진 정보창이 보이실 것입니다.
역시나 정보창의 제목을 클릭하면 해당 포스트로 이동이 가능하구요.
그외의 우측에는 검색창과 포스트가 표시되구요.

검색을 하면, 해당 포스트 제목이과 포스트의 주소, 그리고 Google GeoAPI를 이용한 주소 검색 결과가 나오고, 해당 포스트 또는 주소를 클릭하면 지도가 해당 위치를 중심으로 이동을 하게 됩니다.

설명은 이만 마치고... 블로그에 이를 추가하시기 위해서는 간단한 설정이 필요한데요.

우선 이 방식은 블로그에서 위치를 지정한 포스트들만 특정 label를 붙여서 이를 이용하는 방식이라 블로그의 posting를 할때부터 몇가지 설정을 해 줘야 합니다.
물론 이미 작성한 포스트에 대해서는 수정을 통해 이 설정을 해주시면 되구요.



위에 스크린샷을 보시면... 구글 블로그에 글을 작성하실때 우측에 보이시는 설정 창입니다.
저 중에 위치를 지도에 노출 시키고 싶으신 포스팅에 특정 태그와 위치 설정을 해 주셔야 합니다.

위에를 보시면 저는 maprss 라는 특정 태그를 지정한 것이 보이구요.
위치는 제주도 한라산으로 설정 된 것이 보이실 겁니다.

이제 코드를 보시면....
<script src="http://maps.google.com/maps/api/js?sensor=true&key=YOUR_API_KEY" type="text/javascript">
</script>
<script type="text/javascript">
        BloggerLocation = function(title,adress,ua,va,link,thumbnail,summary,published){
            this.title = title;
            this.address = adress;
            this.ua = ua;
            this.va = va;
            this.link = link
            this.thumbnail = thumbnail;
            this.summary = summary;
        }
        BloggerLocations = function(feeds){
            this.total = feeds.feed.openSearch$totalResults.$t
            this.posts = new Array();
            for(var i=0; i<this.total; i++){
                var post = feeds.feed.entry[i];
                var location = feeds.feed.entry[i].georss$point.$t.split(' ');
                var link = "";
                for(var j=0; j<post.link.length; j++)
                    if(post.link[j].rel == "alternate"){
                        link = post.link[j].href;
                        break;
                    }
                this.posts[i] = new BloggerLocation(post.title.$t,post.georss$featurename.$t, parseFloat(location[0]),parseFloat(location[1]),link,post.media$thumbnail.url, post.summary.$t,post.published.$t);
            }
        }
        BloggerMap = {
            //초기화.
            initialize : function(feeds) {
                this.blog = new BloggerLocations(feeds);
                this.input = document.getElementById("BloggerMap_input");
                this.address = document.getElementById("BloggerMap_addr");
                this.geocoder = new google.maps.Geocoder();
                
                //지도 생성.
                var latlng = new google.maps.LatLng(37.566419230900905,126.97787415510291);
                var myOptions = {
                    zoom: 6,
                    center: latlng,
                    mapTypeId: google.maps.MapTypeId.ROADMAP
                };
                this.map = new google.maps.Map(document.getElementById("BloggerMap_map"),myOptions);
                
                //마커 생성.
                this.marker = new google.maps.Marker({
                    map : this.map,
                    animation: google.maps.Animation.DROP
                });
                this.markBlog();
                this.setAddressList(this.blog.posts, null);
            },
            markBlog : function(){
                var infowindow = new Array();
                for(var i=0; i<this.blog.total; i++){
                    var marker = new google.maps.Marker({
                        map : this.map,
                        position : new google.maps.LatLng(this.blog.posts[i].ua,this.blog.posts[i].va),
                        title : this.blog.posts[i].title
                    });
                    var contentstr = '<h4><a href="' + this.blog.posts[i].link + '">' +this.blog.posts[i].title + '</a></h4>'+'<div style="height:100px; width:250px;overflow-x:hidden;color:black;"><div style="float:left;"><img src="'+ this.blog.posts[i].thumbnail + '"/></div>'+ '<div style="font-size:small;">' + this.blog.posts[i].summary + '</div></div>';
                    infowindow[i] = new google.maps.InfoWindow({
                        content : contentstr
                    });
                    BloggerMap.clickMarker(marker, infowindow, i);  
                }
            },
            clickMarker : function(marker, infowindow, n){
                google.maps.event.addListener(marker, 'click', function(){
                    for(var i=0; i<infowindow.length; i++)
                        infowindow[i].close();
                    infowindow[n].open(this.map, marker);
                    this.map.setCenter(marker.getPosition());
                });
            },
            searchPost : function (search) {
                var posts = new Array();
                for(var i=0; i<this.blog.total; i++){
                    var title = this.blog.posts[i].title.indexOf(search);
                    var address = this.blog.posts[i].address.indexOf(search);
                    var summary = this.blog.posts[i].summary.indexOf(search);
                    if(title != -1 || address != -1|| summary != -1)
                        posts[posts.length] = this.blog.posts[i];
                }
                return posts;
            },
            //주소 검색.(지오코딩)
            codeAddress : function() {
                var search = this.input.value;
                this.geocoder.geocode( { 'address': search}, function(results, status) {
                    if (status == google.maps.GeocoderStatus.OK) 
                        //검색 된 주소 목록.
                        BloggerMap.setAddressList(BloggerMap.searchPost(search),results);
                    else
                        BloggerMap.setAddressList(BloggerMap.searchPost(search),null);
                });
            },
            setAddressList : function(posts, address){
                BloggerMap.address.innerHTML = "";
                if(posts.length > 0){
                    var blogh = document.createElement('b');
                    var blogul = document.createElement('ul');
                    
                    blogh.innerHTML = 'Blog Posts';
                    blogul.appendChild(blogh);
                    
                    for(var i=0; i<posts.length; i++)
                        blogul.appendChild(this.addAddress(posts[i].title,new google.maps.LatLng(posts[i].ua,posts[i].va)));
                
                    this.address.appendChild(blogul);
                }
                if(address != null){
                    var addressh = document.createElement('b');
                    var addressul = document.createElement('ul');
                    
                    addressh.innerHTML = 'Address';
                    addressul.appendChild(addressh);

                    for(var i=0; i<address.length; i++)
                        addressul.appendChild(this.addAddress(address[i].formatted_address,address[i].geometry.location));
                    
                    this.address.appendChild(addressul);
                }
            },
            addAddress : function(address, location){
                var li = document.createElement('li');
                var a = document.createElement('a');
                
                a.href = "#";
                a.innerHTML = address;
                this.clickAddress(a, location);
                
                li.appendChild(a);
                return li;
            },               
            //주소 클릭 이벤트.
            clickAddress : function(a, addr){
                a.onmousedown = function(){
                    //지도 이동.
                    BloggerMap.map.setCenter(addr);
                }
            }
        }
        function BloggerMapinit(feeds){
            BloggerMap.initialize(feeds);
        }
    
</script>
    
<br />
<div>
<div id="BloggerMap_map" style="float: left; height: 400px; width: 400px;">
</div>
<div>
<div>
<input id="BloggerMap_input" onkeydown="javascript:if(event.keyCode == 13) BloggerMap.codeAddress();" type="textbox" value="" />
                <input onclick="javascript:BloggerMap.codeAddress()" type="button" value="Enter" />
                <input onclick="javascript:BloggerMap.setAddressList(BloggerMap.blog.posts,null)" type="button" value="Post List" />
            </div>
<div id="BloggerMap_addr" style="height : 350px; padding-left: 1px;overflow-x:hidden; overflow-y: auto;">
</div>
</div>
<script src="http://creatorhong.blogspot.com/feeds/posts/summary/-/maprss?max-results=300&amp;alt=json-in-script&amp;callback=BloggerMapinit">
</script>
</div>
html, javascript를 모르시는 분들은 복잡하다고 생각하실수도 있지만....
그런 분들도 가장 아래쪽에

<script src="http://creatorhong.blogspot.com/feeds/posts/summary/-/maprss?max-results=300&amp;alt=json-in-script&amp;callback=BloggerMapinit">
</script>

부분만 봐주시면 됩니다.
색이 다른 3부분이 보이시나요? 각각 아래와 같습니다.

블로그 주소 : creatorhong.blogspot.com
지도에 표시할 포스트 Label : maprss
지도에 표시할 최대 마커 수 : 300

블로그 주소를 개인 블로그 주소로 바꿔 주시고, Label은 위에 설명드린데로 특정 라벨을 설정해 주시구요. 최대 마커수는 최근 포스트부터 원하시는 만큼 표시가 됩니다.

저는 전부 보여주기위해 아직 몇년을 가도 채우지 못할 것 같은 숫자인 300을 써 줬습니다.
blogspot이 rss를 최대 얼마나 보여주는지는 확인해 보지 않아 최대값이 얼마일지는 확인을 못했네요.

아.. 그리고, 검색을 할때도 이 최대 마커수 이내의 포스트들만 검색이 가능하니 이를 염두에 두시고 설정을 해 주시면 되겠습니다.

그럼. 위에 코드를 수정 하신 후,
저처럼 블로그에 페이지를 만드셔서 위에 코드를 추가하시면 완성입니다.

2017년 5월 16일

이전에는 구글맵을 쓰는데 API키를 발급 안받아도 썼던거 같은데 오늘 확인하니 API키가 없을 경우 에러가 나네요. (참고 : 구글맵 API 가이드)

구글콘솔에서 API키를 발급 받으신 후 위 소스 상단 구글맵 Javascript 라이브러리를 로드 하는 부분에 API키를 입력해 주시면 됩니다.

<script src="http://maps.google.com/maps/api/js?sensor=true&key=YOUR_API_KEY" type="text/javascript">

2012년 3월 11일 일요일

[Google API] 구글 맵 API(v3)

구글Map API v3의 간단한 예제입니다.
설명이 한글로 잘 되어있네요. 예제도 다양하고, 무엇보다 따로 인증 같은 것을 받을 필요가 없군요. 지오코딩도 콜백함수를 함수내에서 자체적으로 처리하도록 되어있는것 같습니다.
좌표계도 다음맵과 동일한 좌표계를 사용하는군요.

예제코드는 아래와 같습니다.
한가지 주의해야 할 것은 이 API는 HTML5로 작성해야 한다는 군요.

api인증키나 다른 조치 없이 바로 사용이 가능 합니다.
(2017년 5월 16일 추가). API키가 필요하네요. 제일 아래부분에 추가한 내용 참고하시기 바랍니다.

<!-- Google Map API -->
<script type="text/javascript" src="http://maps.google.com/maps/api/js?sensor=true&key=YOUR_API_KEY"></script>

<!-- Code -->
<script type="text/javascript">
    /** Google Map 객체. **/
    GoogleMap = {
        /* 초기화. */
        initialize : function() {
            this.input = document.getElementById("GoogleMap_input");
            this.address = document.getElementById("GoogleMap_addr");
            this.geocoder = new google.maps.Geocoder();
            this.infowindow = new google.maps.InfoWindow();
               
            //지도 생성.(기본 위치 서울.)
            var latlng = new google.maps.LatLng(37.56641923090,126.9778741551);
            var myOptions = {
                zoom: 8,
                center: latlng,
                mapTypeId: google.maps.MapTypeId.ROADMAP
            };
            this.map = new google.maps.Map(
                    document.getElementById("GoogleMap_map"),myOptions);
                
            //마커 생성.
            this.marker = new google.maps.Marker({
                map : this.map,
                animation: google.maps.Animation.DROP
            });
        },
        /* 주소 검색.(지오코딩) */
        codeAddress : function() {
            var address = this.input.value;
            //콜백 함수 호출.
            this.geocoder.geocode( { 'address': address}, 
                           function(results, status) {
                if (status == google.maps.GeocoderStatus.OK) {
                    //검색 된 주소 목록.
                    GoogleMap.address.innerHTML = "";
                    var ul = document.createElement('ul');
                    for(var i=0; i<results.length; i++){
                        var li = document.createElement('li');
                        var a = document.createElement('a');
                         
                        a.href = "#";
                        a.innerHTML = results[i].formatted_address;
                        GoogleMap.clickAddress(a, results[i].geometry.location,
                                results[i].formatted_address);
                        
                        li.appendChild(a);
                        ul.appendChild(li);
                    }
                    GoogleMap.address.appendChild(ul);
                }
            });
        },
        //주소 클릭 이벤트.
        clickAddress : function(a, addr,content){
            a.onmousedown = function(){
                //지도와 마커이동.
                GoogleMap.map.setCenter(addr);
                GoogleMap.marker.setPosition(addr);
                GoogleMap.marker.setAnimation(google.maps.Animation.DROP);
                GoogleMap.infowindow.setContent(content);
                GoogleMap.infowindow.open(GoogleMap.map,GoogleMap.marker);
            }
        }
    }
    window.onload = function(){
        GoogleMap.initialize();
    }
</script>
HTML 태그.
<div>
    <div id="GoogleMap_map" style="width:500px; height:500px; float:left;">
    </div>
    <div style="height:500px; padding-left: 10px;">
        <div>
            <input id="GoogleMap_input" type="textbox" value="" onkeydown="javascript:if(event.keyCode == 13) GoogleMap.codeAddress();" >
            <input type="button" value="Enter" onclick="javascript:GoogleMap.codeAddress()">
        </div>
        <div id="GoogleMap_addr"></div>
    </div>
</div>
제가 블로그에 쓰기위에 좀 더 수정한 [Blog] 구글 지도를 이용한 블로그 지도 만들기도 같이 참고해서 보시면 좋을 듯 합니다.

2017년 5월 16일

이전에는 구글맵을 쓰는데 API키를 발급 안받아도 썼던거 같은데 오늘 확인하니 API키가 없을 경우 에러가 나네요. (참고 : 구글맵 API 가이드)

구글콘솔에서 API키를 발급 받으신 후 위 소스 상단 구글맵 Javascript 라이브러리를 로드 하는 부분에 API키를 입력해 주시면 됩니다.
<script src="http://maps.google.com/maps/api/js?sensor=true&key=YOUR_API_KEY" type="text/javascript"></script>

[Project Euler] 27. 연속되는 n에 대해 가장 많은 소수를 만들어내는 2차식 구하기

27. 연속되는 n에 대해 가장 많은 소수를 만들어내는 2차식 구하기
오일러는 다음과 같은 멋진 2차식을 제시했습니다.

n² + n + 41
이 식의 n에다 0부터 39 사이의 숫자를 넣으면, 그 결과는 모두 소수가 됩니다.
하지만 n = 40일 때의 값 40² + 40 + 41 은 40×(40 + 1) + 41 이므로 41로 나누어지고, n = 41일 때 역시 412 + 41 + 41 이므로 소수가 아닙니다.

컴퓨터의 발전에 힘입어 n² − 79n + 1601 이라는 엄청난 2차식이 발견되었는데, 이것은 n이 0에서 79 사이일 때 모두 80개의 소수를 만들어냅니다. 이 식의 계수의 곱은 -79 × 1601 = -126479가 됩니다.

아래와 같은 모양의 2차식이 있다고 가정했을 때,

n² + an + b   (단 | a | < 1000, | b | < 1000)
0부터 시작하는 연속된 n에 대해 가장 많은 소수를 만들어내는 2차식을 찾아서, 그 계수 a와 b의 곱을 구하세요.
Click
고민을 좀 많이 했습니다. 다른 분들 푸신것도 좀 보고...
http://blog.mycila.com/2009/05/project-euler-problem-27.html 에서는 어떻게 푸는 방법을 잘 정리해 놓은 것 같은데 영어와 공식의 압박에 제대로 이해를 못했네요. 아무튼 이용 할 수 있는 편법은 모두 이용해 봤습니다.
공식(n² + an + b)에 의해.
n = 0 -> b -> b는 소수.
n = 1 -> a + b + 1 -> a+b=1 or a+b=짝수(a,b 모두 홀수 or 모두 짝수)
n = 2 -> 2(a+2) + b -> b는 홀수 or (a=-2) 

(n=1)일때와 (n=2)일때를 종합하면.. a,b 모두 홀수 or a=-2,b=3(n=3일때

a <= -b & n = 1 -> 1보다 작은 값. -> a는 -b보다 큰 값.
n = b -> b(b + a + 1) 즉 최대 n<b.

 이전에 구한 max 보다 클려면 적어도 n = max+1일 때 값이 소수여야함.
그리고 매번 소수인지 판단하는 것은 너무 시간이 걸릴것이므로....
최대값 (실제론 여기까지 오지는 않을것 같지만) max*(2*max+1)까지의 소수여부를 미리 구했습니다.
소수 판단하는 것은 이전에 사용했던 에라토스테네스의 체를 이용했습니다.
<script language="Javascript" type="text/javascript">
function eratos(max){
 /* 2부터 n까지 n-1개를 저장할 수 있는 배열 할당
  * 배열 참조 번호와 소수와 일치하도록 배열의 크기는
  * n+1 길이만큼 할당(인덱스 번호 0과 1은 사용하지 않음)       */
 var PrimeArray = new Array();

 /* 배열초기화
  * 처음엔 모두 소수로 보고 true값을 줌  */
 PrimeArray[0] = PrimeArray[1] = false;
 for(var i=2; i<max; i++) PrimeArray[i]=true;

 /* 에라토스테네스의 체에 맞게 소수를 구함
  * 만일, PrimeArray[i]가 true이면 i 이후의 i 배수는
  * 약수로 i를 가지고 있는 것이 되므로 i 이후의 i 배수에 대해
  * false값을 준다.
  * PrimeArray[i]가 false이면 i는 이미 소수가 아니므로 i의 배수 역시
  * 소수가 아니게 된다. 그러므로 검사할 필요 없다. */
 for(var i=2; i*i<=max; i++)
  if(PrimeArray[i])
   for(var j=2*i; j<=max; j+=i)PrimeArray[j]=false;
 
 return PrimeArray;
}
</script>
그리고 아래가 이번에 구현한 코드입니다.
<script language="Javascript" type="text/javascript">
/* 2차식의 값. */
function func27(a,b,n){
    return r = n*n + a*n + b;
}
/* 연속되는 n에 대해 가장 많은 소수를 만들어내는 2차식의 a와 b의 곱. */
function p027(l){
    var prime = eratos(l*(2*l+1));  //에라토스테네스의 체로 소수배열 구함.
    
    var maxn = 0;
    var maxa = 0;
    var maxb = 0;
    for(var b=3; b<l; b+=2){        //b는 홀수.
        if(!prime[b])                //b는 소수.
            continue;
        for(var a=-b+2; a<l; a+=2){     //a는 -b보다 큰 홀수
            if(prime[func27(a,b,maxn+1)]){  //n = maxn+1 일때 값이 소수이면.
                var n=1;
                for(;n<=maxn; n++){         //0<n<maxn 일때 값이 소수인지 확인.
                    if(!prime[func27(a,b,n)])
                        break;
                }
                if(n>maxn){        
                    for(n=maxn+1; n<b; n++){         //새로운 maxn을 구함.
                        if(!prime[func27(a,b,n+1)])
                            break;
                    }
                    maxn = n;
                    maxa = a;
                    maxb = b;
                }
            }
        }            
    }
    return maxa*maxb;
}
</script>