Script / CSS

G1sUtil.js

G1sBlogger.js

G1sNavigationList.js

G1sCode

Posts List


2012년 4월 25일 수요일

[Project Euler] 51. 일부 숫자를 치환했을 때 8개의 서로 다른 소수가 생기는 가장 작은 소수

51. 일부 숫자를 치환했을 때 8개의 서로 다른 소수가 생기는 가장 작은 소수
두 자리 숫자 *3의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉 가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯 개는 소수입니다.

56**3 의 3번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에서는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.

56003, 56113, 56333, 56443, 56663, 56773, 56993
위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요.
치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0은 올 수 없습니다.
Click
http://nianelo4.blog.me/ 블로그의 동일 문제 풀이에 대해 참고.
1. 마지막 자리에 짝수나 5가 올 경우 2의 배수 혹은 5의 배수이므로 마지막 자리에 올 수 있는 수는 1,3,7,9가 전부.
2. 반복되는 수의 갯수는 3의 배수개일 때만 가능하다.
3의 배수 판단법으로 각 자리의 수를 모두 더했을 때 3의 배수가 되는 수를 찾는 방법을 이용.
반복 되는 수가 3의 배수가 아닐때 각 자릿수를 더한 값은 3번의 한번 3의 배수가 된다.
즉 반복되는 수가 3의 배수이고, 그 외의 자릿수들의 합이 3의 배수가 아닐때 만 8개 이상의 값이 나올 수 있다.
알고리즘은 해당 블로그와 다르네요.

일단 각 자릿수마다 사용하는 패턴이 다르므로 자릿수 증가시마다 패턴을 새로 구합니다.
각 패턴과 i값에 대해 고정 값 n을 만듭니다.
고정값 n에 패턴 * k 를 더해가며 만들어지는 수에 대해 소수인지를 판단하고 최종적으로 소수의 수를 구합니다.
가장 작은 값을 구하는 것이므로 min값이 나온 자릿수보다 자릿수 증가가 일어나기 전까지 연산을 해봅니다.
<script language="Javascript" type="text/javascript">
/* 소수 판단. */
function isPrime(n){
 if(n < 2) return false;
 else if(n < 4) return true;
 else if(n%2 == 0 || n%3 == 0) return false;

 for(var i=5; i*i<=n; i+=6)
     if(n%i == 0 || n%(i+2) == 0)
         return false;
 
 return true;
}
//t와 f의 수의 따라 가능한 패턴을 얻는다.
function get051Patterns(t,f,patterns,tn,fn){
    if(t==tn && f==fn)
        return [patterns];
    
    var r = [];
    if(fn < f)
        r = get051Patterns(t, f, patterns*10, tn, fn+1);
    if(tn < t){
        var temp = get051Patterns(t, f, patterns*10+1, tn+1, fn);
        for(var i in temp)
            r[r.length] = temp[i];
    }
    return r;
}
function p051(){
    var pn = 3, goal = 8;   //기본 변수 설정.
    var digit = 0, ten = 1, patterns, min = Number.MAX_VALUE, minDig = 100;
    for(var i=1; ; i+=(i%10==3)?4:2){
        //자릿수 증가시 새로운 패턴을 얻음.
        if(i >= ten){
            if(minDig == digit)
                break;
            patterns = get051Patterns(pn, digit++, 0, 0, 0);
            ten *= 10;
        }
        
        for(var j in patterns){
            //패턴과 i값을 이용해 고정 값 n을 얻음.
            var cnt = 0;
            var pattern = patterns[j] * 10;
            var n = i;
            for(var k=1; k < pattern; k*=10)
                if(~~(pattern/k)%10 == 1)
                    n = (parseInt(n/k))*k*10 + n%k;
            
            //고정값에 패턴값을 더해가며 소수를 찾음.
            var t = Number.MAX_VALUE;
            for(var k=(pattern < ten * Math.pow(10, pn-1))?0:1; goal<11-k+cnt; k++){
                if(isPrime(n + pattern*k)){
                    if(n+pattern*k < t){
                        t = n+pattern*k;
                        if(t > min)
                            break;
                    }
                    cnt ++;
                }
            }
            
            //소수의 수를 파악하여 결과값을 구함.
            if(cnt >= goal){
                if(min>t){
                    min = t;
                    minDig = digit;
                }
            }
        }
    }
    
    alert(min);
}
</script>
탐색 시간 0.02초 정도.

2012년 4월 21일 토요일

[Project Euler] 50. 1백만 이하의 소수 중 가장 길게 연속되는 소수의 합으로 표현되는 수는?

50. 1백만 이하의 소수 중 가장 길게 연속되는 소수의 합으로 표현되는 수는?
41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.

41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.

1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.

1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?
Click
prime[n] = n 번째 소수.
sum[n][m] = n번째 소수부터 m번째 소수까지를 모두 더한 수
                    (prime[n] + prime[n+1] + ....... + prime[m-1] + prime[m])

라고 할때.

sum[n][m] = 0번째 소수부터 m번째 소수를 더한 수 - 0번째 소수부터 n번째 소수를 더한 수
                     (sum[0][m] - sum[0][n])

가 된다.
에라스토테네스의 체로 소수를 모두 구한 후,
소수들을 체크해나가며 소수들을 더해가 0번째 소수(2)부터 n번째 소수까지의 합 sum[n]의 배열을 채우고, 동시에 sum[n]이 소수인지를 체크해 소수가 되는 sum[n]을 찾아 '첫번째 소수부터 시작하는 가장 길게 연속되는 소수의 합' 을 구한다.

이후 i는 1부터 증가시켜가고, j는 sum.length 부터 감소시켜가며 sum[j] - sum[i]가 소수가 되는 수를 찾아 'i번째 소수부터 시작하는 가장 길게 연속되는 소수의 합'을 구한다.

이때 max count보다 작은 값을 갖는 범위는 탐색할 필요가 없으므로
i값은 sum.length - i 가 max conut 보다 클때만 탐색하고,
j값은 j - i 가 max count 보다 클때만 탐색하면 된다.
<script language="Javascript" type="text/javascript">
/* 에라스토테네스의 체 */
function eratos(max){
    var PrimeArray = new Array();

    PrimeArray[0] = PrimeArray[1] = false;
    for(var i=2; i< max; i++) PrimeArray[i]=true;

    for(var i=4; i<=max; i+=2)PrimeArray[i]=false;
    for(var i=6; i<=max; i+=3)PrimeArray[i]=false;
    for(var i=5; i*i<=max; i+=6){
 if(PrimeArray[i]) for(var j=2*i; j<=max; j+=i)PrimeArray[j]=false;
 if(PrimeArray[i+2]) for(var j=2*(i+2); j+2<=max; j+=i+2)PrimeArray[j]=false;
    }

    return PrimeArray;
}
function p050(limit){
    //소수 판별 배열.
    var check = eratos(limit);
    
    //첫번째 소수부터 시작하는 가장 길게 연속되는 소수의 합.
    var sum = []; sum[0] = 2; sum[1] = 2 + 3;
    var max = 2, r = 5;
    for(var i=5; sum[sum.length-1]<=limit; i+=(i%6==1)?4:2){
        if(check[i]){
            sum[sum.length] = sum[sum.length-1] + i; //0 ~ n번째 소수까지의 합.
            if(check[sum[sum.length-1]]){
                max = sum.length;
                r = sum[sum.length-1];
            }
        }
    }
    
    //i번째 소수부터 시작하는 가장 길게 연속되는 소수의 합.
    for(var i=1; sum.length-i>max; i++){
        for(var j=sum.length; j-i>=max; j--){
            var temp = sum[j] - sum[i]; //j ~ i번째 소수까지의 합.
            if(check[temp]){
                max = j-i+1;
                r = temp;
            }
        }
    }

    alert(r);
}
</script>
탐색시간 0.85(s)

2012년 4월 18일 수요일

[Project Euler] 49. 세 항이 소수이면서 다른 수의 순열이 되는 4자리 숫자의 등차수열 찾기

49. 세 항이 소수이면서 다른 수의 순열이 되는 4자리 숫자의 등차수열 찾기
1487, 4817, 8147은 3330씩 늘어나는 등차수열입니다. 이 수열에는 특이한 점이 두 가지 있습니다.

  • 세 수는 모두 소수입니다.
  • 세 수는 각각 다른 수의 자릿수를 바꿔서 만들 수 있는 순열(permutation)입니다.

1자리, 2자리, 3자리의 소수 중에서는 위와 같은 성질을 갖는 수열이 존재하지 않습니다. 하지만 4자리라면 위엣것 말고도 또 다른 수열이 존재합니다.

그 수열의 세 항을 이었을 때 만들어지는 12자리 숫자는 무엇입니까?
Click

에라스토테네스의 체를 이용 소수리스트를 구해 놓은 후, 1001부터 9999까지의 소수 i에 대해 i보다 큰 j와 i와 j사이의 차이만큼 j에 더한 값 k가 소수인지 확인을 하고, 세 수가 모두 소수이면, 세 수가 순열인지를 확인하였습니다.
<script language="Javascript" type="text/javascript">
/* 순열 판단 */
function isPermutation(num1, num2){
    var d = [0,0,0,0,0,0,0,0,0,0];
    for(var i=num1; i>=1; i/=10)
        d[~~(i%10)] ++;
    for(var j=num2; j>=1; j/=10)
        if((--d[~~(j%10)]) < 0)
            return false;
    
    return true;
}
/* 소수 리스트 */
function eratos(max){
    var PrimeArray = new Array();

    PrimeArray[0] = PrimeArray[1] = false;
    for(var i=2; i< max; i++) PrimeArray[i]=true;

    for(var i=4; i<=max; i+=2)PrimeArray[i]=false;
    for(var i=6; i<=max; i+=3)PrimeArray[i]=false;
    for(var i=5; i*i<=max; i+=6){
 if(PrimeArray[i]) for(var j=2*i; j<=max; j+=i)PrimeArray[j]=false;
        if(PrimeArray[i+2]) for(var j=2*(i+2); j+2<=max; j+=i+2)PrimeArray[j]=false;
    }
 
    return PrimeArray;
}
function p049(){
    var prime = eratos(10000);
    var r= new Array();
    for(var i=1001; i<10000; i+=(i%6==1)?4:2){
        if(prime[i]){
            var lim = i + (100000-i)/2;
            for(var j=i+((i%6==1)?4:2); j< lim;j+=(j%6==1)?4:2){
                var k = j+(j-i);
                if(prime[j] && prime[k])
                    if(isPermutation(i,j) && isPermutation(i,k))// && i != 1487)
                        r[r.length] = i*100000000 + j*10000 + k;
            }
        }
    }
    
    alert(r);
}
</script>

2012년 4월 17일 화요일

[Project Euler] 48. 11 + 22 + 33 + ... + 10001000 의 마지막 10자리

48. 11 + 22 + 33 + ... + 10001000 의 마지막 10자리
11 + 22 + 33 + ... + 1010 = 10405071317 입니다.

11 + 22 + 33 + ... + 10001000 의 마지막 10자리 숫자는 무엇입니까?
Click
오버플로우 처리만 한다면 간단한 문제.
마지막 10자리만 필요하다는 조건에서 오버플로우를 해결하는 방법이 보이네요. 

11자리 이상의 수는 아무런 영향을 미치지 않으니 계산을 할때 뒤의 10자리만 가지고 계산을 하면 됩니다. 식으로 표현하면 아래 처럼 된다는 군요.
(x + y) % m = ((x % m) + (y % m)) % m (x * y) % m = ((x % m) * (y % m)) % m
<script language="Javascript" type="text/javascript">
function p048(length){
    length ++;
    var mod = 10000000000;
    
    for(var i=1, sum = 0; i < length; i++){
        for(var j=1, pow = i; j < i; j++)
            pow = (pow*i)%mod;
        
        sum += pow;
    }

    alert(sum%mod);
}
</script>

[Project Euler] 47. 서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우는?

47. 서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우는?

서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다.

14 = 2 × 7
15 = 3 × 5

서로 다른 세 개의 소인수를 갖는 수들이 처음으로 세 번 연속되는 경우는 다음과 같습니다.

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?
Click  첫번째 방법. 단순한 brute-force 로... 2.5초 정도 걸리네요.
<script language="Javascript" type="text/javascript">
function func047(n){
    var t = n;
    var cnt = 0;
    if(t%2==0){
        cnt ++;
        do t/=2; while(t%2==0);
    }
    if(t%3==0){
        cnt ++;
        do t/=3; while(t%3==0);
    }
    for(var i=5; i<=t; i+=6){
        if(t%i==0){
            cnt ++;
            do t/=i; while(t%i==0);
        }
        if(t%(i+2)==0){
            cnt ++;
            do t/=i+2; while(t%(i+2)==0);
        }
    }
    return cnt;
}
function p047(){
    var cnt = 4;
    for(var i=1; cnt>0; i++){
        if(func047(i) == 4)
            cnt--;
        else
            cnt = 4;
    }
    alert(i-4);
}
</script>
두번째 방법. 위의 방법에 단순하게 이전 기록을 저장하면서 이전 기록을 참조. 0.05초? 그 이하도 나오는 듯하네요.
<script language="Javascript" type="text/javascript">
function func047(n,nums){
    if(n<2) return 0;
    if(n%2==0){
        nums[n] = (n==2)?1:(nums[n/2] + ((n%4==0)?0:1));
        return nums[n];
    }
    if(n%3==0){
        nums[n] = (n==3)?1:(nums[n/3] + ((n%9==0)?0:1));
        return nums[n];
    }
    for(var i=5; i*i<=n; i+=6){
        if(n%i==0){
            nums[n] = nums[n/i] + ((n%(i*i)==0)?0:1);
            return  nums[n];
        }
        if(n%(i+2)==0){
            nums[n] = nums[n/(i+2)] + ((n%((i+2)*(i+2))==0)?0:1);
            return nums[n];
        }
    }
    nums[n] = 1;
    return 1;
}
function p047(){
    var nums = [0,0];
    var cnt = 4;
    for(var i=1; cnt>0; i++){
        if(func047(i,nums) == 4)
            cnt--;
        else
            cnt = 4;
    }
    alert(i-4);
}
</script>
46번부터 시간을 체크하기 시작했는데 javascript는 시도할때마다 시간 오차가 좀 있네요.

2012년 4월 15일 일요일

[Project Euler] 46. (소수 + 2×제곱수)로 나타내지 못하는 가장 작은 홀수인 합성수는?

46. (소수 + 2×제곱수)로 나타내지 못하는 가장 작은 홀수인 합성수는?

크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다.

9 = 7 + 2×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

이 추측은 잘못되었음이 밝혀졌습니다.

위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?
Click  

소수 판정은 에라토스테네스의 체로 어느정도 적정선을 구해놓고 하는게 좋겠지만 답을 구하기전에는 적정선을 모르니 일반 소수 판정을 약간 변형, 앞에서 구한 소수들을 이용했습니다.
<script language="Javascript" type="text/javascript">
/* 소수판정. 기존에 구한 소수 배열을 이용. */
function isPrime(n, prime){
    if(n==3) return true;
    for(var i=0; prime[i]*prime[i] < n; i++)
        if(n%prime[i] == 0)
            return false;
    return true;
}
/* 골드바흐의 홀수 합성수 추측 확인. 기존에 구한 소수 배열을 사용. */
function isGoldbach(n, prime){
    for(var i=0; i < prime.length; i++){
        var temp = Math.sqrt((n-prime[i])/2);
        if(temp == ~~temp)
            return true;
    }
    return false;
}
function p046(){
    prime = new Array();
    for(var i=3; ; i+=2){
        if(isPrime(i, prime))
            prime[prime.length] = i;
        else if(!isGoldbach(i, prime))
            break;
    }
    alert(i);
}
</script>
찾아보니 위의 경우와는 약간 다르지만 짝수와 관련 된 골드바흐의 추측이 있군요. 이 것은 아직 미해결 문제로 남아있다네요.
골드바흐의 추측(Goldbach's conjecture)은 오래 전부터 알려진 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것이다.
이때 하나의 소수를 두 번 사용하는 것은 허용한다.
예를 들어, 20까지의 짝수는

4 = 2+2 6 = 3+3
8 = 3+5
10 = 3+7 = 5+5
12 = 5+7
14 = 3+11 = 7+7
16 = 3+13 = 5+11
18 = 5+13 = 7+11
20 = 3+17 = 7+13

위와 같이, 두 개의 소수의 합으로 표현할 수 있다. 그러나 모든 짝수에서 가능한지는 아직까지 해결하지 못하고 있다.

2012년 4월 14일 토요일

[Project Euler] 45. 오각수와 육각수도 되는, 40755 다음으로 큰 삼각수는?

45. 오각수와 육각수도 되는, 40755 다음으로 큰 삼각수는?

삼각수, 오각수, 육각수는 아래 식으로 구할 수 있습니다.

삼각수 Tn = n (n + 1) / 2 1, 3, 6, 10, 15, ...
오각수 Pn = n (3n − 1) / 2 1, 5, 12, 22, 35, ...
육각수 Hn = n (2n − 1) 1, 6, 15, 28, 45, ...

여기서 T285 = P165 = H143 = 40755 가 됩니다.

오각수와 육각수도 되는, 그 다음으로 큰 삼각수를 구하세요.
Click

44번을 풀었다면 쉽게 구할 수 있는 문제인 듯 하네요.

H(n) = n (n - 1) = 2n (n - 1)/2 = (2n - 1)((2n - 1) + 1)/2 = T(2n - 1)

위 식에 의해 H(n) = T(2n-1) 이므로 P = H 가 같은 경우만 찾으면 됩니다.

P(p) = H(h)
p(3p-1)/2 = h(2h-1)
p(3p-1) = 2h(2h-1)
3p²- p = 4h²- 2h
36p²- 12p = 48h²- 24h
36p²- 12p + 1 = 48h²- 24h + 1
(6p-1)²= 48h²- 24h + 1
6p - 1 = √(48h²- 24h + 1)
6p = √(48h²- 24h + 1) + 1
p = (√(48h²- 24h + 1) + 1)/6

위의 p값이 정수값이 되는 h를 구하면 됩니다.
<script language="Javascript" type="text/javascript">
function p045(){
    for(var h=144; ; h++){
        var p = (Math.sqrt(48*h*h - 24*h + 1) + 1)/6;
        if(p == parseInt(p)) break;
    }
    alert(h*(2*h-1));
}
</script>

2012년 4월 13일 금요일

[Project Euler] 44. 합과 차도 모두 오각수인 두 오각수 차의 최소값은?

44. 합과 차도 모두 오각수인 두 오각수 차의 최소값은?

오각수는 Pn = n (3n − 1)/2 라는 공식으로 구할 수 있고, 처음 10개의 오각수는 다음과 같습니다.

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

위에서 P4 + P7 = 22 + 70 = 92 = P8이 됨을 볼 수 있습니다. 하지만 두 값의 차인 70 − 22 = 48 은 오각수가 아닙니다.

합과 차도 모두 오각수인 두 오각수 Pj, Pk 에 대해서, 그 차이 D = | Pk − Pj | 는 가장 작을 때 얼마입니까?
Click

일단 문제를 해결 하기 위해 오각수를 판단하는 함수가 일단 필요하겠네요.
x = n(3n-1)/2
2x = 3n²- n
24x = 36n²- 12n
24x + 1 = 36n²- 12n +1
24x + 1 = (6n - 1)²
√(24x + 1) = 6n - 1
√(24x + 1) + 1 = 6n
(√(24x + 1) + 1) / 6 = n
즉 위의 값 n이 정수값을 가지면 해당 수 x는 오각수가 됩니다.
<script language="Javascript" type="text/javascript">
/** 오각수 판단. **/
function isPentagonal(num){
    var n = (Math.sqrt(24*num + 1)+1)/6;
    if(parseInt(n) == n)
        return true;
    else
        return false;
}
</script>
이제 남은 것은 범위를 정하는 것인데요. k>j 이고, j는 최대 k-1 이니 d값은 최소 P(k) - P(k-1) 값이고, 이 값은.. 3k - 2 가 됩니다.
p(n) - p(n-1) = (n(3n-1) - (n-1)(3(n-1)-1))/2
p(n) - p(n-1) = (3n²- n - (3n²- 7n + 4))/2
p(n) - p(n-1) = 3n - 2
즉 3k-2가 min 보다 크다면 더 이상의 k값의 증가 탐색을 할 필요가 없겠죠.
그리고 j값은 k-1부터 시작해 d값이 min보다 크면 탐색 종료, P(j)가 3*k-2보다 작으면 d값은 오각수가 아니게 되므로 마찬가지로 탐색을 종료합니다.
<script language="Javascript" type="text/javascript">
/** 오각수. **/
function pentagonal(n){
    return (3*n*n - n)/2;
}
function p044(){
    var min = 1000000000;
    
    for(var k=2; 3*k-2<min; k++){
        var pk = pentagonal(k), d = 0, s;
        for(var j=k-1; j>0; j--){
            var pj = pentagonal(j);
            d = pk - pj;
            if(d>min)
                break;
            else if(pj<3*k-2)
                break;
            else if(isPentagonal(d) && isPentagonal(pk+pj))
                min = d;
        }
    }
    alert(min);
}
</script>
돌려보면 체감상으로도 바로 값이 안나오는 것이 느껴질 정도로 연산이 꽤 오래 걸리는 편입니다.

해당 조건을 만족하는 최초의 d 값이 가장 작은 값이라는 것은 예상이 가능하고 해당 d를 구하는 것은 빠른 편인데,
해당 d값이 과연 가장 작은 값인지에 대해, 그 이상의 값을 탐색하는게 오래걸리는 편이네요.

예상대로 첫번째 d가 가장 작은 수가 맞고.. 범위를 임의로 자르거나 첫번째로 구하는 d까지만 탐색한다면 더 빠른 시간이 걸리겠지만 해당 방법은 답은 맞을지라도 문제를 제대로 푼 것은 아니겠지요.

어떻게든 범위를 줄이는 것이 관건인데 더이상의 좋은 방법은 떠오르지 않는 군요.

2012년 4월 12일 목요일

[Project Euler] 43. 부분열에 관련된 특이한 성질을 가진 모든 팬디지털 숫자의 합

43. 부분열에 관련된 특이한 성질을 가진 모든 팬디지털 숫자의 합

숫자 1406357289은 0 ~ 9 팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다.

d1을 첫째 자리수, d2를 둘째 자리수...라고 했을 때, 다음과 같은 사실을 발견할 수 있습니다.

d2 d3 d4 = 406 → 2로 나누어 떨어짐
d3 d4 d5 = 063 → 3으로 나누어 떨어짐
d4 d5 d6 = 635 → 5로 나누어 떨어짐
d5 d6 d7 = 357 → 7로 나누어 떨어짐
d6 d7 d8 = 572 → 11로 나누어 떨어짐
d7 d8 d9 = 728 → 13으로 나누어 떨어짐
d8 d9 d10 = 289 → 17로 나누어 떨어짐

위와 같은 성질을 갖는 0 ~ 9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?
Click  

그야말로 값들을 하나하나 넣을때마다 조건을 따져가며 10개의 자릿수를 채워 팬디지털을 만들는 과정을 거치는게 가장 빠를 것입니다.  그전에 수의 성질을 몇가지 이용하면 위의 조건 중 몇가지를 수정할 수 있습니다.
d2 d3 d4 = 406 → 2로 나누어 떨어짐 → d4 = 짝수
d3 d4 d5 = 063 → 3으로 나누어 떨어짐 → d3 + d4 + d5 = 3으로 나누어 떨어짐.
d4 d5 d6 = 635 → 5로 나누어 떨어짐 → d6 = 0 or 5
d5 d6 d7 = 357 → 7로 나누어 떨어짐
d6 d7 d8 = 572 → 11로 나누어 떨어짐
d7 d8 d9 = 728 → 13으로 나누어 떨어짐
d8 d9 d10 = 289 → 17로 나누어 떨어짐
이제 d1부터 하나씩 구해가면서 위에 조건과 만족하는 결과를 배치해 가며 구합니다.
d1,d2는 그 어떤 성질에도 영향을 주지 않으니 0~9의 수에서 서로 겹치지 않게 배치.
d3는 2번째 성질에 영향을 주지만 시작점이니 역시 0~9의 수에서 d1,d2와 겹치지 않게 배치.
d4는 짝수 중에서 앞의 값들과 겹치지 않게 배치.
d5는 (3-(d3+d4))%3 값을 시작으로 3씩 더해가면서 앞에서 구한 값들과 겹치지 않게 배치.
d6는 0,5 중에서 앞의 값과 겹치지 않게 배치.
d7은 (7-((d5*100+d6*10)%7))%7과 7을 더해서 9가 넘지 않는 수를 앞에서 구한 값들과 겹치지 않게 배치.
d8은 (11-((d6*100+d7*10)%11))%11 이 앞에 구한 값과 겹치지 않고 9이하라면 배치.
d9는 (13-((d7*100+d8*10)%13))%13 이 앞에 구한 값과 겹치지 않고 9이하라면 배치.
d10은 (17-((d8*100+d9*10)%17))%17 이 앞에 구한 값과 겹치지 않고 9이하라면 배치.
<script language="Javascript" type="text/javascript">
function p043(){
  var r = 0, check = [true,true,true,true,true,true,true,true,true,true];
  for(var d1=0; d1<10; d1++){
    check[d1] = false;
    for(var d2=0; d2<10; d2++) if(check[d2]){
      check[d2] = false;
      for(var d3=0; d3<10; d3++) if(check[d3]){
        check[d3] = false;
        for(var d4=0; d4<10; d4+=2) if(check[d4]){
          check[d4] = false;
          for(var d5=(3-((d3+d4)%3))%3; d5<10; d5+=3) if(check[d5]){
            check[d5] = false;
            for(var d6=0; d6<10; d6+=5) if(check[d6]){
              check[d6] = false;
              for(var d7=(7-((d5*100+d6*10)%7))%7; d7<10; d7+=7) if(check[d7]){
                check[d7] = false
                var d8=(11-((d6*100+d7*10)%11))%11;
                if(d8<10 && check[d8]){
                  check[d8] = false;
                  var d9 = (13-((d7*100+d8*10)%13))%13;
                  if(d9<10 && check[d9]){
                    check[d9] = false;
                    var d10 = (17-((d8*100+d9*10)%17))%17;
                    if(d10<10 && check[d10])
                      r += d1*1000000000+d2*100000000+d3*10000000+d4*1000000+
                           d5*100000+d6*10000+d7*1000+d8*100+d9*10+d10;
                    check[d9] = true;
                  }
                  check[d8] = true;
                }
                check[d7] = true;
              }
              check[d6] = true;
            }
            check[d5] = true;
          }
          check[d4] = true;
        }
        check[d3] = true;
      }
      check[d2] = true;
    }
    check[d1] = true;
  }
  alert(r);
}
</script>

2012년 4월 11일 수요일

[Project Euler] 42. 주어진 텍스트 파일에 들어있는 '삼각단어'의 개수는?

42. 주어진 텍스트 파일에 들어있는 '삼각단어'의 개수는?

n번째 삼각수는 tn = ½ n (n + 1) 이라는 식으로 구할 수 있는데, 처음 10개는 아래와 같습니다.

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

어떤 영어 단어에 대해서, 각 철자의 알파벳 순서(A=1, B=2, ..., Z=26)를 모두 더한 값을 '단어값'이라 부르기로 합니다.
예를 들어 'SKY'의 단어값은 19 + 11 + 25 = 55가 되는데, 이것은 우연히도 t10과 같습니다.
이렇게 어떤 단어의 단어값이 삼각수일 경우에는 이 단어를 '삼각단어'라 부르기로 합니다.

약 16KB의 텍스트 파일 words.txt에는 2000개 정도의 영어 단어가 수록되어 있습니다.
이 중에서 삼각단어는 모두 몇 개입니까?
Click
삼각함수 Tn = n*(n+1)/2
               2*Tn = n*(n+1) 

여기서 2*Tn 의 제곱근의 값을 내림 한 값이 n이 될거라는 것을 추측할 수 있다.
즉. ceil(sqrt(2Tn)) = k 이라고 할때 k*(k+1)/2 = Tn 일 경우 해당 수는 삼각함수입니다.   
그리고 나머지는 22번 문제를 수정하여 완성.
<script language="Javascript" type="text/javascript">
/* 삼각함수 판단 */
function isTriangular(Tn){
    var sqrtTn = parseInt(Math.sqrt(2*Tn));
    return (Tn == sqrtTn*(sqrtTn+1)/2);
}
/* 텍스트의 점수를 더한 값이 삼각함수인지 체크하여 count. */
function p042(values){
    var names = values.split(',');
    var cnt = 0;
    for(var i=0; i< names.length; i++){
        var sum = 0;
        for(var j=1; j< names[i].length-1; j++)
            sum += names[i].charCodeAt(j)-64;
        if(isTriangular(sum))
            cnt ++;
    }
    alert(cnt);
}
</script>
아래는 파일 접근을 위한 함수.. 아래 함수에서 파일을 읽어서 p042함수를 실행 시킵니다.
<script language="Javascript" type="text/javascript">
/* 파일을 읽어서 함수 실행. */
function getData(url){
    // 기본적인 변수 선언 
    var xmlhttp = null; 
    if (window.XMLHttpRequest)  { xmlhttp=new XMLHttpRequest(); } // code for IE7+, Firefox, Chrome, Opera, Safari
    else    { xmlhttp=new ActiveXObject("Microsoft.XMLHTTP");   } // code for IE6, IE5

    // URL 주소의 값을 가져온다 
    xmlhttp.open("GET", url, true); 
    xmlhttp.setRequestHeader("Cache-Control", "no-cache");
    xmlhttp.setRequestHeader("Pragma", "no-cache");

    // 값을 가져 왔을경우 호출할 메소드를 선언 
    xmlhttp.onreadystatechange = function() { 
        // readyState 가 4 고 status 가 200 일 경우 올바르게 가져옴 
        if(xmlhttp.readyState==4){
            if (xmlhttp.status == 200){
                //F
                if (xmlhttp.responseText != null)
                    // 지정된 함수 실행.
                    p042(xmlhttp.responseText); 
                else
                    alert("Failed to receive RSS file from the server - file not found.");
            }
            else
                alert(responseText = "Error code " + xmlhttp.status + " received: " + xmlhttp.statusText); 
        } 
    } 
    
    xmlhttp.send(null); 
}
</script>

2012년 4월 10일 화요일

[Project Euler] 41. n자리 팬디지털 소수 중에서 가장 큰 수

41. n자리 팬디지털 소수 중에서 가장 큰 수
1부터 n까지의 숫자를 하나씩만 써서 만든 n자리 숫자를 팬디지털(pandigital)이라고 부릅니다. 2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다.

 n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까?
Click
가장 큰 수이므로 n=9에서부터 시작하여 큰 수부터 작은수 순으로 팬디지털을 만들어가며 가장 먼저 발견되는 소수를 찾았습니다.

 여기에 모든 각 자릿 수를 더한 값이 3의 배수가 나오면 해당 수는 3의 배수이므로 판단에서 제외 할 수 있습니다. (n=9,8,6,5,3,2 제외)
<script language="Javascript" type="text/javascript">
function isPrime(n){
    if(n <= 1) return false;
    if(n == 2) return true;
    else if(n%2 == 0) return false;
 
    for(var i=3; i*i<=n; i+=2)
        if(n%i == 0) return false;
    return true;
}
function func041(nums, num, digit, n){
    if(digit == n){
        if(isPrime(num))
            return num;
        else 
            return 0;
    }
    for(var i=n; i>0; i--){
        if(nums[i]){
            nums[i] = false;
            var r = func041(nums,num*10+i,digit+1,n);
            if(r != 0)
                return r;
            nums[i] = true;
        }
    }
    return 0;
}
function p041(){
    var max = 0, nums = [false,true,true,true,true,true,true,true,true,true];
    
    for(var n=9; n>0; n--){
        if(parseInt((n+1)*n/2) % 3 == 0)
            continue;
        max = func041(nums, 0, 0, n);
        if(max != 0)
            break;
    }
    alert(max);
}
</script>

2012년 4월 9일 월요일

[Project Euler] 40. 어떤 무리수에서 소수점 n번째 자리 숫자 알아내기

40. 어떤 무리수에서 소수점 n번째 자리 숫자 알아내기
소수점 뒤에 양의 정수를 차례대로 붙여 나가면 아래와 같은 무리수를 만들 수 있습니다.



0.123456789101112131415161718192021...
이 무리수의 소수점 아래 12번째 자리에는 1이 옵니다 (위에서 붉게 표시된 숫자). 소수점 아래 n번째 숫자를 dn이라고 했을 때, 아래 식의 값은 얼마입니까? d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000
Click
먼저 n번째 위치한 수가 포함된 수를 찾고 해당 수에서 몇번째 수를 가르키는 지를 찾으면 dn의 값을 쉽게 구할 수 있습니다.

그러기위해서는 우선 k자릿수의 수가 소수에서 몇개의 자리를 차지하는지부터 접근을 시작해 보는게 빠를 것입니다.
1자리 수는 1~9까지 9개.
2자리 수는 10~99까지 90개.
3자리 수는 100~999까지 900개.
....

각 k 자릿수의 수는 9*10^(k-1)개 그리고 이 각 자릿수가 이루고 있는 문자는

1자릿수가 9*1 개
2자릿수가 90*2 개
3자릿수가 900*3 개
....

각 k 자릿수의 수가 9*10^(k-1) * k 개가 된다.

k를 1부터 증가시켜가며 9*10^(k-1) * k보다 작은지 확인하여
작지 않으면 n에서 9*10^(k-1) * k 를 빼가며

해당 9*10^(k-1) * k보다 작은 수를 찾으면 자릿수 n번째 수가 가리키는 수의 자릿수 k를 찾을 수 있다.

그리고 마지막 남은 temp = n - ∑9*10^(k-1) 의 값(∑의 i범위는 0~(k-1))을 k로 나누면 어떤 값의 일부인지를 알 수 있고, number = (temp-1)/k + 10^(k-1)
다시 temp값을 k로 나눈 나머지 값은 해당 값의 몇번째 값인지를 알 수 있다. digit = k-(temp-1)%k

최종으로 number에서 digit번째의 수를 찾기 위해서는 (number/10^(digit-1))%10을 해주면 된다.
위와 같이 구하면 쉽게 구할 수 있겠네요.
여기에 9*10^(k-1) * k 를 쉽게 구하기 위해 t=9에서 자릿수 증가시마다 10을 곱해주는 방법으로 구현 하였습니다.
<script language="Javascript" type="text/javascript">
function func040(n){
    var temp = n;
    var t = 9;
    var k=1;
    for(; temp>=t*k; k++){
        temp -= t*k;
        t *= 10;
    }
    
    return parseInt((((temp-1)/k+t/9)/Math.pow(10,k-(temp-1)%k-1))%10);
}
function p040(){
    var r = 1;
    for(var d=1; d<=1000000; d*=10)
        r *= func040(d);
    alert(r);
}
</script>

[Blogspot] Picasa Gallery 만들기

사진들을 보관할 수 있는 많은 클라우드 서비스 들이 있는 데요. 그 중 구글에서 제공하고 있는 Picasa의 API를 이용하여 피카사 갤러리를 만들어 보았습니다. 이전에는 웹서핑을 하다 다른분이 만들었던것으로 임시로 사용하고 있었는데요, 당시 방식은 일일이 앨범마다 페이지를 새로 만들어서 해당 앨범으로의 링크를 거는 것이었던 것을 이번에는 여러가지 기능 개선을 시켜보았습니다. 우선, 일일이 원하는 앨범을 입력하는 방식이 아닌.. 피카사 내의 앨범 중 비공개 앨범을 제외한 전체 공개 앨범만 불러와서 썸네일과 함께 Title를 보여주고, 사진 선택시 페이지 전환없이 한페이지에서 해당 앨범내의 사진들의 썸네일을 보여주도록 하였습니다.  예제는 아래를 보시면 되구요.  제 갤러리는 아래 예제에다가 이전에 포스트 했던 Pinterest의 레이아웃을 입히도록 약간의 수정이 더해진 상태입니다.
위에 "전체 앨범 보기" 링크로 어디서든 처음의 초기화면으로 돌아갈 수가 있구요. 전체 앨범 상태에서는 사진을 클릭시 현재 페이지 내에서 해당 앨범의 사진을 볼 수 있고, 앨범 밑에 Title를 클릭시 새로운 창에서 해당 Picasa의 앨범이 열리도록 되어 있습니다.  그리고, 각 앨범에서는 사진이나 Title 선택시 모두 새로운 창에서 해당 Picasa의 앨범이 열리도록 되어 있습니다. 그럼 위 기능을 구현하기 위한 코드를 보시겠습니다.
<script>
var PicasaGallery = {
    /* 초기화. */
    init : function(id, width, height){
        this.id = id;
        this.width = width;
        this.height = height;
        this.gallery = document.getElementById('GalleryAlbum');
        this.script = document.getElementById('GalleryScript');
        this.ping();        
    },
    /* get Picasa Album API */
    ping : function(){
        this.script.innerHTML = "";
        var s = document.createElement('script');
        s.type = 'text/javascript';
        s.charset = 'utf-8';
        s.src = 'https://picasaweb.google.com/data/feed/api/user/'+this.id+'?kind=album&access=public&alt=json-in-script&callback=PicasaGallery.pong';
        this.script.appendChild(s);
    },
    /* 앨범 정보 저장. */
    pong : function(json){
        /* Posts  */
        this.albums = new Array();
        for(var i=0; i< json.feed.entry.length; i++){
            var link;
            var feed;
            for(var j=0; j< json.feed.entry[i].link.length; j++){
                if(json.feed.entry[i].link[j].rel == 'http://schemas.google.com/g/2005#feed')
                    feed = json.feed.entry[i].link[j].href;
                if(json.feed.entry[i].link[j].rel == 'alternate')
                    link = json.feed.entry[i].link[j].href;
            }
            
            this.albums[i] = {
                title : json.feed.entry[i].title.$t,
                id : json.feed.entry[i].id.$t,
                img : json.feed.entry[i].media$group.media$thumbnail[0].url,
                link : link,
                feed : feed
            };      //media$thumbnail[0].url    //media$content[0].url,
        }
        this.pongAlbums();
    },
    /* 앨범 뿌려주기. */
    pongAlbums : function(){
        this.gallery.innerHTML = "";
        
        for(var i=0; i< this.albums.length; i++){
            var div = document.createElement('div');
            var img = document.createElement('img');
            var imga = document.createElement('a');
            var a = document.createElement('a');
            var comment = document.createElement('div');

            var self = this;
            var feed = this.albums[i].feed;
            
            img.src = this.albums[i].img;
            img.style.margin = '10px';
            img.style.width = this.width + 'px';
            img.style.height = this.height + 'px';

            this.pingAlbum(self, imga, feed);
            imga.href = "#PicasaGallery"
            imga.appendChild(img);
            
            a.href = this.albums[i].link;
            a.innerHTML = this.albums[i].title;
            a.target = '_blank';
            
            comment.appendChild(a);
            comment.style.wordBreak = 'break-all';
            
            div.style.float = 'left';
            div.style.margin = '10px';
            div.style.width = this.width + 30 + 'px';
            div.style.height = this.height + 60 + 'px';
            div.appendChild(imga);
            div.appendChild(comment);
            
            this.gallery.appendChild(div);
        }
        this.gallery.style.height = div.offsetHeight + div.offsetHeight + 'px';
    },
    /* get Picasa Photo API */
    pingAlbum : function(self, img, feed){
        img.onclick = function(){
            self.script.innerHTML = "";
            var s = document.createElement('script');
            s.type = 'text/javascript';
            s.charset = 'utf-8';
            s.src = feed + '&kind=photo&callback=PicasaGallery.pongAlbum';
            self.script.appendChild(s);
        }
    },
    /* 사진 뿌려주기. */
    pongAlbum : function(json){
        this.gallery.innerHTML = "";
        var self = this;
        var gallery = document.createElement('div');
        
        for(var i=0; i< json.feed.entry.length; i++){
            var div = document.createElement('div');
            var img = document.createElement('img');
            var imga = document.createElement('a');
            var a = document.createElement('a');
            var comment = document.createElement('div');
            
            img.src = json.feed.entry[i].media$group.media$thumbnail[0].url;
            img.style.margin = '10px';
            img.onclick = function(){}
            img.style.width = this.width + 'px';
            img.style.height = this.height + 'px';
            
            for(var j=0; j< json.feed.entry[i].link.length; j++)
                if(json.feed.entry[i].link[j].rel == 'alternate')
                    a.href = json.feed.entry[i].link[j].href;
            a.innerHTML = json.feed.entry[i].title.$t;
            a.target = '_blank';
            
            comment.appendChild(a);
            comment.style.wordBreak = 'break-all';
            
            imga.href = a.href;
            imga.target = '_blank';
            imga.appendChild(img);
            
            div.style.float = 'left';
            div.style.margin = '10px';
            div.style.width = this.width + 30 + 'px';
            div.style.height = this.height + 60 + 'px';
            div.appendChild(imga);
            div.appendChild(comment);
 
            gallery.appendChild(div)
            this.gallery.appendChild(gallery);
        }
        this.gallery.style.height = div.offsetTop + div.offsetHeight + 'px';
    }
};
window.onload = function(){
    var id = 'creatorhong';
    var width = 200;
    var height = 200;
    PicasaGallery.init(id, width, height);
};
</script>

<div id="PicasaGallery" >
    <div align="center"><a id="G1sGoAlbums" href="#PicasaGallery" onclick="PicasaGallery.pongAlbums()">전체 앨범 보기</a></div>
    <div id="GalleryAlbum"></div>
    <div id="GalleryScript"></div>
</div>
제 전 포스트들를 보시면 아시겠지만 언제나 봐야할 곳은 마지막 window.onload = function(){} 안에 들어 있습니다. 간단하게 하나씩 살펴 보겠습니다. id = 'creatorhong'; - 피카사의 아이디를 입력하면 됩니다.                           숫자로 된 ID나 gmail의 ID를 입력하시면 됩니다. width = 200;    - 이미지의 넓이 height = 200;  - 이미지의 높이

이상만 수정해 주시면 완료. 더 자세한 것은 코드 내부를 수정해 주시거나, css 수정을 통해서 수정해 주시면 됩니다.

2012년 4월 8일 일요일

[Project Euler] 39. 가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는?

39. 가장 많은 직각삼각형이 만들어지는 둘레(≤ 1000)의 길이는?

세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있습니다.

{20, 48, 52}, {24, 45, 51}, {30, 40, 50}
1000 이하의 둘레 p에 대해서, 직각삼각형이 가장 많이 만들어지는 p의 값은 얼마입니까?
Click

9번문제을 좀더 일반화 한 문제네요.
a + b + c = n 에서.
b + c = n - a
b = (n - a) - c
n-a -> t로 놓으면... -> b = t - c
피타고라스 정리에 넣으면..

a ² + b ² = c ² 는
a ² + (t-c) ² = c²
a ² + t ² - 2*t + c ² = c²
a ² + t ² = 2*t*c
( a ² + t ² ) / (2*t) = c

여기서 t = n-a 이므로... 주어진 n에서 a만 알면, c와 b를 구할 수 있다.

여기에 9번에서 미쳐 생각못한 부분인... 조건문의 범위를 a < n까지가 아닌 a < b까지로 그리고 문제에 맞게 약간의 수정을 통해 완료했습니다.
<script language="Javascript" type="text/javascript">
function p039(n){
    var r=0, max = 0;
    for(var i=1; i<=n; i++){
        var a, b=i, c;
        var cnt = 0;
        for(a=1; a < b; a++){
            var t = i-a;
            c = parseInt((a*a + t*t) / (2*t));
            b = i - a - c;
            
            if(a*a + b*b == c*c && b!=0)
                cnt ++;
        }
        if(cnt > max){
            max = cnt;
            r = i;
        }
    }
    
    return r;
}
</script>

[Layout] Pinterest 방식의 레이아웃 정렬

요즘 소셜 큐레이션 서비스인 http://pinterest.com가 큰 인기를 끌고 있는 데요. 무엇보다도 세로 종대로 정렬된 이미지 레이아웃이 눈에 띕니다.


가로로 길이가 긴 이미지보다는 세로로 길이가 긴 이미지(웹툰, 인포그래피 등)가 많은 요즘 상황에 딱 알맞은 레이아웃인 듯 합니다.

보기도 깔끔하고... 해서 이와 같은 레이아웃을 구현해 봤습니다. 아래가 제가 구현한 예시구요.
원래는 브라우져의 크기가 변함에 따라 레이아웃도 자동으로 변화해야 하지만....
블로그 내에서는 해당 방식의 적용이 안되 약간의 수정을 가한상태입니다.

한번 브라우져 창의 크기를 조절해 보시면 창 크기에 비례해서 이미지 배열이 바뀌는 것을 확인 하실 수 있습니다.



댓글 or 주석란 Test
댓글 or 주석란 Test 줄바꿈 줄바꿈 줄바꿈 줄바꿈 줄바꿈 줄바꿈
댓글 or 주석란 Test
댓글 or 주석란 Test - 자동 줄바꿈. 자동 줄바꿈. 자동 줄바꿈. 자동 줄바꿈.
댓글 or 주석란 Test
댓글 or 주석란 Test
댓글 or 주석란 Test
댓글 or 주석란 Test
댓글 or 주석란 Test
댓글 or 주석란 Test
이미지 출처는 http://pinterest.com 입니다.

2012년 4월 7일 토요일

[Project Euler] 38. 어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 숫자

38. 어떤 수에 (1, 2, ... )를 곱해서 이어붙여 얻을 수 있는 가장 큰 1 ~ 9 팬디지털 숫자

숫자 192에 1, 2, 3을 각각 곱합니다.

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576
곱한 결과를 모두 이어보면 192384576 이고, 이것은 1 ~ 9 팬디지털(pandigital)인 숫자입니다. 이런 과정을 편의상 '곱해서 이어붙이기'라고 부르기로 합니다.

같은 식으로 9와 (1, 2, 3, 4, 5)를 곱해서 이어붙이면 918273645 라는 1 ~ 9 팬디지털 숫자를 얻습니다.

어떤 정수와 (1, 2, ... , n)을 곱해서 이어붙였을 때 얻을 수 있는 가장 큰 아홉자리의 1 ~ 9 팬디지털 숫자는 무엇입니까? (단 n > 1)
Click
두가지 방법으로 풀었는데요.

우선 풀이에 들어가기에 앞서 기본적으로 사용한 함수는...

자릿수를 알아내는 함수
<script language="Javascript" type="text/javascript">
function getDigit(n){
    return Math.ceil(Math.log(n)/Math.log(10));
}
</script>
주어진 값을 n까지 곱해서 이어붙이는 함수
<script language="Javascript" type="text/javascript">
function joinMultiply(m, n){
    var r = m;
    for(var i=2; i<=n; i++){
        var temp = m * i;
        var digit = getDigit(temp);
        r = r * Math.pow(10,digit) + temp;
    }
    return r;
}
</script>
각 자릿수를 이루고 있는 수 중 0이나 중복 된 수가 없는지를 판단하는 함수.
<script language="Javascript" type="text/javascript">
function checkNoneOverlapNum(n){
    var temp = n;

    var check = new Array();
    check[0] = false;
    for(var j=1; j<10; j++)
        check[j] = true;
    
    while(temp >= 1){
        var t = temp % 10;
        if(check[t])
            check[t] = false;
        else
            return false;
        temp = parseInt(temp/10);
    }
    return true;
}
</script>
이상 3가지.
각 자릿수를 이루고 있는 수 중 0이나 중복 된 수가 없는지를 판단하는 함수는 팬디지털 판단 외에도 전처리로 사용하기 위해 9자리 모두를 썼는지 확인하는 과정은 제외된 상태이죠.
이 3 함수를 기본으로 하여 이제는 탐색 범위를 줄이는 것이 관건. 

우선 첫번째 방법은 주어진 힌트를 모두 이용하는 방법입니다.

힌트에 주어진 값중에 9, (1~5) 곱 이어붙인 값이 918273645가 현재까지 알고있는 최대값입니다.
그렇다면 최소한 첫자리가 9로 시작하는 자리이고,

90,(1~4) 곱 이어붙이기는 11자릿수, 99,(1~3) 곱 이어붙이기는 8자릿수로 90대 탐색 필요없음.
900, (1~3) 곱 이어붙이기는 11자릿수, 999, (1~2) 곱 이어붙이기는 7자릿수로 900대 탐색 필요없음.
9000, (1~2) 곱 이어붙이기는 9자릿수. 9999, (1~2) 곱 이어붙이기는 9자릿수로 9000대 탐색 필요.

그리고, 최소 9182보다 커야 하므로 9183부터 탐색 시작.
9876보다 큰 수로는 팬디지털이 안되므로 9876까지 탐색.
여기에 더해서 i의 값 각 자릿수에 겹치는 수가 있거나 0이 있다면 팬디지털을 만들 수 없으므로 해당 수는 제외.

위와 같은 식으로 탐색 범위를 줄여서 탐색을 합니다.
<script language="Javascript" type="text/javascript">
function p038(){
    var max = joinMultiply(9,5);
    
    for(var i=parseInt(max/100000); i<9876; i++){
        if(!checkNoneOverlapNum(i))
            continue;
        
        var join = joinMultiply(i,2);
        if(checkNoneOverlapNum(join)){
            if(join > max)
                max = join;
        }
    }
    alert(max);
}
</script>
위 방식으로 간단히 구하기는 했는데.... 솔직히 저 방식은 제가 좋아하는 방식은 아니네요.
힌트로 주어진 값이 9,(1~5)의 경우가 아니었다면 저 방식으로는 못 푸는 경우도 발생하겠죠.
그래서, 이 힌트에는 상관없이 주어진 조건만으로 값을 구해내는 방식이 두번째 방식입니다.

일단 주어진 조건에 만족하는 팬디지털이 있다는 가정아래 max값은 123456789로 초기화 합니다.

탐색은 각 1부터 n이 최소 2가 될 수 있는 조건인 9876까지 탐색하는 방법이 있으나, 탐색 과정을 줄이기 위해 자릿수로 탐색.

즉 한자리인 1~9까지 탐색,
두자리인 11~99까지 탐색.
세자리 101~999까지 탐색.
네자리 1001~9999까지 탐색.

하는 것을 기본 틀로 잡습니다. 
그리고 다시 각 자리수 탐색의 시작지점을 현재 max값의 가장 앞자리로 이루어진 값 +1로 재 조정합니다. 즉.

i = max/100000000*(pow(10,자릿수))+1

이 시작 점이 됩니다. (이를 편하게 계산하기 위해 v값을 자릿수 증가시마다 10씩 곱해주며 판단.)

 다음으로 각 수마다 적정 필요 n값을 구하는데... 
n은 1부터 순서대로 곱했을때 자릿수가 바뀌는 지점을 파악(해당 점은 k로 볼때)
해당 지점까지로 구할 수 있는 자릿수를 뺀 나머지 자릿수로 9를 만들 수 있는 수를 찾으면 된다.
라는 결론아래 아래 식이 나옵니다.

n = k + (9-(k*digit))/(digit+1) 

그리고 해당 n값이 자연수가 아닐 경우, 해당 값은 9자리를 만들지를 못한다는 뜻이고, 이를 한번 걸러냅니다.

마지막으로 첫번째 방식에 사용한 i의 값 각 자릿수에 겹치는 수가 있거나 0이 있다면 팬디지털을 만들 수 없으므로 해당 수는 제외

이 와 같은 방법으로 탐색 범위를 좁힐 수 있습니다.
<script language="Javascript" type="text/javascript">
function p038(){
    var max = 123456789;
    
    var v = 1;
    for(var digit = 1; digit < 10/2; digit++){
        v *= 10;
        for(var i=parseInt(max/100000000*(v/10))+1; i<v; i++){
            var n = parseInt(v/i);
            n += (9-n*digit)/(digit+1);
            
            if(n != parseInt(n))
                continue;
            
            if(!checkNoneOverlapNum(i))
                continue;
            
            var join = joinMultiply(i,n);
            if(checkNoneOverlapNum(join)){
                if(join > max)
                    max = join;
            }
        }
    }
    alert(max);
}
</script>
딱 보기에도 두번째 방식이 첫번째 방식보다 오래걸리는 것은 확실 합니다.
하지만, 1~9까지 탐색을 마치고 나면 max값이 918273645로 변하게 되고, 이것은 후에 탐색범위를 줄이는 큰 역할을 하죠.

그리고 이렇게 좁힌 범위 안에서는 n의 값을 구하는 판별법만으로 2자릿수 대와 3자릿수대를 모두 걸러낼 수 있습니다.

즉, 결국 1~9 탐색 후 92~99까지, 919~999까지는 n판별까지만 탐색하고, 9183부터 다시 탐색에 들어가
1번째 방법에 비해 큰 차이가 나지 않는다고 볼 수 있겠네요.

2012년 4월 4일 수요일

[Project Euler] 37. 왼쪽이나 오른쪽에서 한자리씩 없애가도 여전히 소수인 수의 합은?

37. 왼쪽이나 오른쪽에서 한자리씩 없애가도 여전히 소수인 수의 합은?

소수 3797에는 왼쪽부터 자리수를 하나씩 없애거나 (3797, 797, 97, 7) 오른쪽부터 없애도 (3797, 379, 37, 3) 모두 소수가 되는 성질이 있습니다.

이런 성질을 가진 소수는 단 11개만이 존재합니다. 이것을 모두 찾아서 합을 구하세요.

(참고: 2, 3, 5, 7은 제외합니다)
Click
개인적으로 별로 좋아하는 스타일의 문제는 아니군요. 11개라는 값을 모른다면 무한 탐색을 해야하는 문제고... 무엇보다 무한한 소수중에서 11개라고 딱 정의 내릴 수 있는게 어떻게 가능한지...... 일단 문제를 냈으니 11개는 맞을테지만 그 한계치를 정한 방법이 궁금...

일단 주어진 한계값은 11개밖에 없다는 점 하나군요. 그래서 최대치는 count를 해가며 count값이 11이면 종료하도록 설계.

한계값이 정해져 있다면 에라토스의 체로 모든 소수를 구해 놓은 다음에 그 안에서 판별하는 것도 좋은 방법이겠으나, 한계값이 없으므로 정석대로 brute-force 로 구했습니다.

시작점은 1의 자리가 아니고, 10대의 수 또한 1만 남으면 소수가 아니기 때문에 21부터 시작 짝수는 판단 안해도 되니 2씩 증가.

오른쪽, 왼쪽 부터 지워주는 방법은..

왼쪽부터 지우는 방법은 나누기 10을 해주면 되고..
오른쪽부터 지우는 방법은 생각을 달리해 %10^n씩 해주며 왼쪽부터 쓰는것으로... 역으로 처리하였습니다.
<script language="Javascript" type="text/javascript">
/** 소수 판단. 
 * @param {Object} n : 판별하고자 하는 수.
 * @return {Array} : true, false.
 **/
function isPrime(n){
 if(n <= 1) return false;
 if(n == 2) return true;
 else if(n%2 == 0)
  return false;
 
 for(var i=3; i*i<=n; i+=2){
     if(n%i == 0)
         return false;
 }
 return true;
}
function p037(){
    var cnt = 0;
    var sum = 0;
    for(var i=21; cnt<11; i+=2){
        if(isPrime(i)){
            var temp1 = i%10;
            var temp2 = parseInt(i/10);
            var check = true;
            for(var j=2; temp1 < i; j++){
                if(!isPrime(temp1) || !isPrime(temp2)){
                    check = false;
                    break;
                }
                temp1 = i % Math.pow(10, j);
                temp2 = parseInt(temp2/10);
            }
            if(check){
                sum += i;
                cnt ++
            }
        }
    }
    alert(sum);
}
</script>
그런데 답을 구해놓고 보니 답글란에 첫번째 자리(가장 좌측)에 올 수 있는 수는 {2,3,5,7} 뿐이고... 중간에 들어갈 수 있는 수는 {1,3,7,9} (짝수와 5의 배수를 만들 수 있는 수 제외) 뿐
이라는 댓글을 보고 해당 성질을 이용하면 좀 더 효율적으로 구할 수 있을 것 같아서 위에 두 성질에 1의 자리(가장 오른쪽)에는 {3,7}만 가능 하다는 성질을 더해서 새로 구현해 봤습니다.
첫번째 들어 갈 수 있는 수 {2, 3, 5, 7} => 혼자 남았을때 소수가 되는 수.
가운데 들어 갈 수 있는 수 {1, 3, 7, 9} => 1의 자리에 남았을 때 짝수나 5의 배수를 만들지 않는 수.
마지막에 들어 갈 수 있는 수 {3, 7} => 혼자 남았을 때 소수가 되며, 짝수와 5의 배수를 만들 수 없는 수
<script language="Javascript" type="text/javascript">
/** 소수 판단. 
 * @param {Object} n : 판별하고자 하는 수.
 * @return {Array} : true, false.
 **/
function isPrime(n){
 if(n <= 1) return false;
 if(n == 2) return true;
 else if(n%2 == 0)
  return false;
 
 for(var i=3; i*i<=n; i+=2){
     if(n%i == 0)
         return false;
 }
 return true;
}
function p037(){
    /* 첫, 중간, 마지막자리에 올 수 있는 값. */
    var fn = new Array(2,3,5,7);  //첫번째(가장 왼쪽) 올 수 있는 값.
    var mn = new Array(1,3,7,9);  //중간에 올 수 있는 값.
    var ln = new Array(3,7);      //마지막(가장 오른쪽) 올 수 있는 값.
    
    /* 각 자리수 탐색 위치 초기 설정. */
    var p = new Array();
    p[0] = 0;
    p[1] = 0;
    
    /* 변수 초기화. */
    var cnt = 0;
    var sum = 0;
    
    while(cnt<11){
        /* n값 구하기. */
        var n = fn[p[p.length-1]];
        for(var i=p.length-2; i>0; i--){
            n = n*10 + mn[p[i]]
        }
        n = n*10 + ln[p[0]];
        
        /* n이 소수일경우. */
        if(isPrime(n)){
            var temp1 = n%10;           //우측부터 씀.(좌측부터지우는걸 역으로)
            var temp2 = parseInt(n/10); //우측부터 지움.
            var check = true;
            for(var j=2; temp1 < n; j++){
                if(!isPrime(temp1) || !isPrime(temp2)){
                    check = false;
                    break;
                }
                temp1 = n % Math.pow(10, j);
                temp2 = parseInt(temp2/10);
            }
            if(check){
                sum += n;
                cnt ++
            }
        }
        
        /* 다음 자릿수 탐색 위치를 찾음. */
        p[0] ++;
        if(p[0] >= 2){
            p[0] = 0;
            p[1] ++;
            for(var i=1; i< p.length; i++){
                if(p[i] >= 4){
                    p[i] = 0;
                    if(i==p.length-1)
                        p[i+1] = 0;
                    else
                        p[i+1] ++;
                }
                else
                    break;
            }
        }
    }
    
    //결과값.
    alert(sum);
}
</script>

2012년 4월 3일 화요일

[Project Euler] 36. 10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합

36. 10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합

대칭수(palindrome)인 585는 2진수로 나타내도 10010010012가 되어 여전히 대칭수입니다.

10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합을 구하세요.

(주의: 첫번째 자리가 0이면 대칭수가 아님)
Click
1~1000000까지의 수 중에 사실 대부분의 수는 대칭수가 아닙니다.
즉 이걸 모두 돌며 대칭수인지 아닌지를 판단하는 방법은 좋은 방법이 아니죠....
여기서 생각을 달리해 대칭수를 판단하는 것이 아닌... 대칭수를 만든다면??
1~999까지의 수를 해당 수의 자릿수만큼 뒤에 0을 붙이고 해당 수의 배열을 역으로 만들어 더해준다면?
즉, 1 -> 11, 12 -> 1221, 235->235532 로 만든다면 이것은 모두 대칭수가 됩니다.

1~999까지의 수를 자릿수 -1만큼 0을 붙인 후 가장 마지막 수를 제외한 수를 역으로 만들어 더해준다면??
즉 1 -> 1, 12 -> 121, 235 -> 23532. 이것도 역시 대칭수가 됩니다.
그리고 이 두 경우를 제외한 대칭수는 존재하지 않죠.

즉 1~1000000까지 존재하는 대칭수는 총 1998개가 전부입니다.
그럼 이 1998개의 수에 대해서 2진수가 대칭수인지를 판단하면 결과가 나오죠.

그리고 2진수가 대칭수가 되기위해 필요한 과정에서 10진수가 짝수라면 2진수의 1의자리에 0이 오게되어 대칭수가 아니게 되죠. 그래서 짝수를 걸러내면 조금더 효율적으로 구할 수 있습니다.
<script language="Javascript" type="text/javascript">
/* 수의 배열을 역으로 한 수. */
function reverse(number, base){
    var reverse = 0;
    while (number != 0) {
        reverse = reverse * base + number % base;
        number = parseInt(number/base);
    }
    return reverse;
}
/* 대칭수 판단. */
function isPalindromic(number, base) {
    return number == reverse(number, base);
}
/* 자릿수를 구함. */
function digit(n){
    return parseInt(Math.log(n)/Math.log(10))+1;
}
/* max값 보다 작은 수 중 2,10진수 모두가 대칭수 인 수를 모두 더해준 값. */
function p036(max){
    var sum = 0;
    for(var i=1; ; i++){
        var n = i* Math.pow(10,digit(i)) + reverse(i,10);
        if(n >= max) break;
        if(n % 2 == 0) continue;
        if(isPalindromic(n,2))
            sum += n;
    }
    for(var i=1; ; i++){
        var n = i* Math.pow(10,digit(i)-1) + reverse(parseInt(i/10),10);
        if(n >= max) break;
        if(n % 2 == 0) continue;
        if(isPalindromic(n,2))
            sum += n;
    }
    return sum;
}
</script>