'Programing/Algorithm'에 해당되는 글 13건

  1. 2015.02.10 프로젝트 오일러 3번
  2. 2015.02.10 프로젝트 오일러 2번
  3. 2015.02.10 Kadane's Algorithm

문제: 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.

예를들면 13195의 소인수는 5, 7, 13, 29 입니다. 600851475143의 소인수 중에서 가장 큰 수를 구하세요.


#include <stdio.h>


int main()

{

 int i;

 unsigned long long int n = 600851475143;

 for (i = 2; i<=n; i++)

 {

  if (n%i == 0){

   printf("%d ", i);

   n = n/i;

   i = 2;

  }

 }

 return 0;

 

}


//문제의 답이 제대로 나오지 않았는데, INT형의 범위를 고려하지 않은것이 문제였다. unsigned long long으로 선언하지 않으면 제대로 된 답이 나오지 않는다.

'Programing > Algorithm' 카테고리의 다른 글

프로젝트 오일러 6번  (0) 2015.02.10
프로젝트 오일러 5번  (0) 2015.02.10
프로젝트 오일러 4번  (0) 2015.02.10
프로젝트 오일러 2번  (0) 2015.02.10
Kadane's Algorithm  (0) 2015.02.10
Posted by kimmayer

문제: 피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

짝수이면서 4백만 이하의 모든 항을 더하면 얼마가 됩니까?


#include <stdio.h>


int main()

{

 int first = 1;

 int second = 2;

 int third = 0;

 unsigned int total = 2;

 int flag = 0;


 while (third < 4000000){

  third = first + second;

  if (third % 2 == 0) total += third;

  first = second;

  second = third;

 }


 printf("%d\n", total);

}

'Programing > Algorithm' 카테고리의 다른 글

프로젝트 오일러 6번  (0) 2015.02.10
프로젝트 오일러 5번  (0) 2015.02.10
프로젝트 오일러 4번  (0) 2015.02.10
프로젝트 오일러 3번  (0) 2015.02.10
Kadane's Algorithm  (0) 2015.02.10
Posted by kimmayer

n^3 알고리즘으로서 주어지는 행렬의 sub array들로 만들어지는 직사각형들 중 최대 합을 가지고 있는 직사각형을 구하는 알고리즘,

 

 

void main(){

 char c;

 string s;

 int n;

 int row, col;

 ifstream fin;

 fin.open("testcase100.txt");

 getline(fin, s);

 istringstream input(s);

 input >> row;

 col = row;

 n = row;

 int **pt = new int *[row];

 for(int i = 0; i < row; i++)

  pt[i] = new int[col];

 

 int *c_pt = new int [row];

 /*for(int i = 0; i < row; i++)

  c_pt[i] = new int[col];*/

 

 int temp = 0;

 

 for(int i=0; i < row; i++)

  for(int j = 0; j < col; j++)

  {

   fin >> temp;

   pt[i][j] = temp;

  }

  

     

  int sum = 0;

  int sum_2 = 0;

  int max_sum = 0; 

  

  

 

 int t = 0;

   int S = 1<<31, d = 0, k, l, x1 = 0,x2 = 0,y1 = 0,y2 = 0,j;

 

 

 for( int z = 0; z < n; z++)

    {

  for(int i = 0; i < n; i++) c_pt[i] = 0;

 

        for(int x = z; x < n; x++)

        {

            t = 0;

   d = 1<<31;

            j = 0;

            k = 0; l = 0;

   for(int i = 0; i < n; i++)

            {

    c_pt[i] = c_pt[i] + pt[x][i];

    t = t + c_pt[i];

    if( t > d)

                {

     d = t;

                    k = i;

                    l = j;

                }

                if( t < 0 )

                {

                    t = 0;

                    j = i + 1;

                }

            }

   if( d > S)

            {

    S = d;

                x1 = x;

                y1 = k;

                x2 = z;

                y2 = l;

            }

        }

    }

 

    cout << x1 << " " << y1 << " " << x2 << " "  << y2 << endl;

    cout << S;

 

    

}

'Programing > Algorithm' 카테고리의 다른 글

프로젝트 오일러 6번  (0) 2015.02.10
프로젝트 오일러 5번  (0) 2015.02.10
프로젝트 오일러 4번  (0) 2015.02.10
프로젝트 오일러 3번  (0) 2015.02.10
프로젝트 오일러 2번  (0) 2015.02.10
Posted by kimmayer
이전버튼 1 2 이전버튼

블로그 이미지
IT 기술들 정리, 독후감을 주로 남깁니다!
kimmayer

공지사항

Yesterday
Today
Total

달력

 « |  » 2024.3
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

최근에 올라온 글

최근에 달린 댓글

최근에 받은 트랙백

글 보관함