기본적인 알고리즘 문제 풀기 - 2


문제 4. 


앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?



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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method4();
    }
}
 
class MyClass1{
    // 문제4.     
    // 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
    // 두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.
    // 세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?
     public void method4(){
         int intValue1;
         String stringValue1;
         ArrayList<String> arraylist = new ArrayList<String>();
        for(int i=1; i<1000; i++){
            for(int j=1; j<1000; j++){
//                System.out.println("i값: "+i+"x"+j+"="+i*j);
                intValue1 = i*j;
                stringValue1 =Integer.toString(intValue1);
                
                if(stringValue1.length() % 2 == 0){
                    if(stringValue1.length() == 2){
                        if(stringValue1.charAt(0== stringValue1.charAt(1)){
                            System.out.println("2자리 대칭수: "+stringValue1);
                        }
                    }
                    if(stringValue1.length() == 4){ // 10 01
                        if(stringValue1.substring(0,2).equals(stringValue1.substring(3,4)+stringValue1.substring(2,3))){
                            System.out.println("4자리 대칭수: "+stringValue1);
                        }
                    }
                    if(stringValue1.length() == 6){
                        if(stringValue1.substring(0,3).equals(stringValue1.substring(5,6)+stringValue1.substring(4,5)+stringValue1.substring(3,4))){
                            System.out.println("6자리 대칭수: "+stringValue1);
                            arraylist.add(stringValue1);
                        }
                    }
                }
            }
        }        
        System.out.println("3자리 대칭수 중 가장 큰값은: "+Collections.max(arraylist));
    }
}
cs


출력결과




문제 5.


1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 


접근방법 5-1. if문 중첩방법



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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method5();
    }
}
 
 
class MyClass1{
        
     // 문제5 접근방법1.
     // 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
     // 그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?     
     public void method5(){
         int n = 10000;
         for(int i=2; i<=10;){
             if(n % i == 0){// 2
                 i++;
                 if(n % i == 0){ // 3     
                     i++;
                     if(n % i == 0){ // 4          
                         i++;
                          if(n % i == 0){ // 5          
                              i++;
                               if(n % i == 0){ // 6          
                                   i++;
                                    if(n % i == 0){ // 7          
                                        i++;
                                        if(n % i == 0){ // 8        
                                            i++;
                                            if(n % i == 0){ // 9
                                                i++;
                                                if(n % i == 0){ // 10
                                                    System.out.println("1부터 10까지 나눠지는 수: "+n);
                                                    i++;
                                                }
                                            }
                                        }
                                    }
                                }
                           }
                      }
                 }
             }
             if(n>1){
                 n = n-1;                 
             }
             i = 2;
         }
     }
}
cs


출력결과




접근방법 5-2. 메소드 호출방법


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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method5A(999999999,2);
    }
}
 
 
class MyClass1{
    
     // 문제5 접근방법2.
     // 1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
     // 그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?     
     // n= 10000, i= 2
     public void method5A(int n, int i){
         while(n>1){
             if(n%i==0){ // 1000 % 2 == 0
                 i++// 3
                 if(n > 1){
                     method5B(n, i);
                 }
                 if(i==20){
                     System.out.println("1부터 20까지 나눠지는 수: "+n);
                 }
             }else{
                 if(n>1){
                     n = n-1;
                 }
                 i = 2;  
             }             
         }
     }     
     
     public void method5B(int n, int i){     
         if (n % i == 0 ){
            i++;
        }
     }
}
 
cs


출력결과


문제 6


1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).

1^2+2^2+3^2+4^2+5^2+6^2+7^2+8^2+9^2+10^2

1+4+9+16+25+36+49+64+81+100 = 385

1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).

(1 + 2 + ... + 10)^2 = 552 = 3025

따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.

그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?



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
32
33
34
35
36
37
38
39
40
41
42
43
package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method6();
    }
}
 
 
class MyClass1{
 
    // 1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).
    // 1^2+2^2+3^2+4^2+5^2+6^2+7^2+8^2+9^2+10^2
    // 1+4+9+16+25+36+49+64+81+100 = 385
    // 1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).
    // (1 + 2 + ... + 10)^2 = 552 = 3025
    // 따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.
    // 그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?     
     
     public void method6(){
         int squareSum = 0;
         int sumSquare = 0;
         int subtractSquare = 0;
         for(int i=1; i<=100; i++){
             squareSum += i * i; // 1 * 1 // 2* (2*2) 3*3 4*4
         }
         System.out.println("제곱의 합: "+squareSum);
         for(int i=1; i<=100; i++){
             sumSquare += i;
         }
         sumSquare *= sumSquare;
         System.out.println("합의 제곱: "+sumSquare);
         subtractSquare= sumSquare - squareSum;
         System.out.println("합의제곱-제곱의합: "+subtractSquare);
     }     
     
}
cs


출력결과




기본적인 알고리즘 문제 풀기


문제 1. 


10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.

1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?


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
32
33
34
35
36
37
38
39
package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method1();
    }
}
 
 
class MyClass1{
    
    // 문제1. 
    // 10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.
    // 1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?
    public void method1(){
        int threeMulti = 0;
        int fiveMulti = 0;
        int sum = 0;
        
        for(int i=0; i<1000; i++){
            if( i%3 == 0 ){
                threeMulti += i;
            }
            if( i%5 == 0){
                fiveMulti += i;
            }
        }
        System.out.println("3의 배수: "+threeMulti);
        System.out.println("5의 배수: "+fiveMulti);
        sum = threeMulti+fiveMulti;
        System.out.println("3의배수와 5의 배수를 모두 합한 값: "+sum); ;
    }
}
cs


출력결과




문제 2.


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

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

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



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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method2();
    }
}
 
 
class MyClass1{
        
    // 문제2.     
    // 피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.
    // 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
    // 짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까? 
    public void method2(){
        
        int previousData = 1;
        int currentData = 2;
        int nextData = previousData + currentData; // 3
        int sum = 0;
        
        while(previousData < 4000000){            
            previousData = currentData; // 2 
            if(previousData < 4000000 ){
                currentData = nextData;  // 3
                nextData = previousData + currentData; // 5 
                System.out.println("previousData: "+previousData);
                System.out.println("currentData: "+currentData);
                System.out.println("nextData: "+nextData);                
                if(previousData % 2 == 0){
                    sum = sum+ previousData;
                    System.out.println("pre짝수값: "+previousData);
                }
            }
        }
        System.out.println("짝수값: "+sum);
    }
}    
cs


출력 결과




문제 3.


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

예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. // 1, 2, 3, 5, 7, 11

600851475143의 소인수 중에서 가장 큰 수를 구하세요.



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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
package test1;
 
import java.util.ArrayList;
import java.util.Collections;
 
public class MyTest1 {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyClass1 myClass1 = new MyClass1();
        myClass1.method3();
    }
}
 
 
class MyClass1{
        
    // 문제3.     
    // 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
    // 예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. // 1, 2, 3, 5, 7, 11
    // 600851475143의 소인수 중에서 가장 큰 수를 구하세요.    
    public void method3(){
        long n = 13195;
        
        // 정적 배열 사용
        long[] myNum1 = new long[10];
        long j = 0;
        long max = 0;
        
        // 동적배열에 사용하는 ArrayList
        ArrayList<Long> array = new ArrayList<Long>();
        
        for(long i=2; i<=n; i++){ // 2639
            if(n % i == 0){
                n = n / i;
                myNum1[(int) j++= i;
                array.add(i);
            }
        }
        long maxValue = Collections.max(array);
        System.out.println("동적배열 최대값: "+maxValue);
        
        // 정적 배열 비교
        for(int i=0;i<j;i++){
            max = myNum1[0]; 
            if(max < myNum1[i]){
                max = myNum1[i];
            }
        }
        System.out.println("정적배열 최대값: "+max);
    }
}
 
cs


출력 결과






+ Recent posts