오늘 공부한 알고리즘 문제 5개

문제1

100,000 보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마인가요?

정답 : 2333316668

    public static void main(String args[]) {
        long sum = 0;
        for(int i = 1; i < 100000; i++) {
            if (i % 3 == 0 || i % 5 == 0) {
                sum += i;
            }
        }
        System.out.println("결과 : " + sum);
    }

---

문제2

피보나치 수열에서 5천만 이하이고, 짝수인 항의 합은 얼마인가요?

피보나치(Fibonacci)수열의 각 항은 바로 앞의 항 두 개를 더한 것입니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다. 1, 2, 3, 5, 8, 13, 21, 34, 55, ...(1과 2로 시작하는 경우로 풀이한다.)

5천만 이하의 짝수 값을 갖는 모든 피보나치 항을 더하면 얼마가 됩니까?

정답 : 19544084

    public static void main(String args[]) {
        //문제 : 피보나치 수열에서 5천만 이하이고 짝수인 항의 합은 얼마인가요?
        //EX : 1, 2, 3, 5, 8, 13, 21, ...
        int n1 = 1;
        int n2 = 2;
        int sum = 2;
        
        while (true) {
            int newNum = n1 + n2;
            
            if(newNum > 50000000) {
                break;
            }
            if (newNum % 2 == 0) {
                sum += newNum;
            }
            
            n1 = n2;
            n2 = newNum;
        }
        System.out.println("결과 : " + sum);
    }

---

문제3

1600851475143의 소인수 중에서 가장 큰 수를 구하세요. 어떤 수를 소수의 곱으로만 나타내는 것을 소인수 분해라 하고, 이 소수들은 그 수의 소인수라고 합니다. 예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.

정답 : 16807369

어려웠던 점

• '소인수 분해'의 개념에서 자신이 없어서 로직을 생각하는 데 어려웠음.
• 소인수분해란. 1 보다 큰 양의 정수를 소수들의 곱으로 나타내는 것을 말한다.
  이 때 곱으로 나타내어지는 소수들을 '소인수'라고 한다. 해당 수를 나누어 떨어뜨리는 수.
• 소수를 소인수분해할 경우에는 해당 수 자체가 유일한 소인수가 된다.

로직 생각할 점

1. 문제의 숫자가 소수인 경우

• 가장 큰 소인수는 해당 수 자체가 될 수 있다.

2. 소수가 아닐 경우

• 2부터 해당 수까지 나누어 떨어지는 수 중에 가장 큰 수를 찾으면 된다.

결론

2부터 해당 수까지 나누어 떨어지는 수를 찾고, 거기서 가장 큰 수가 정답이다.
(그런데 엄청 큰 소수가 문제의 숫자로 나올 경우, 시간 초과가 나올 수 있다. 10억 이상?)

    public static void main(String args[]) {
        //문제 : 1600851475143의 소인수 중에서 가장 큰 수는?
        long num = 1600851475143L;

        int i = 2;
        while(i <= num) {
            if (num % i == 0) {
                num /= i;
                System.out.println(num);// 533617158381, 177872386127, 9361704533, 16807369, 1
            }
            else {
                i++;
            }
        }

        System.out.println("결과 : " + i);
    }

---

문제4

네 자리 수 2개를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까? 앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

정답 : 99000099

package com.ll;

public class Main2 {
    public static void main(String args[]) {
        //문제 : 네 자리 수 2개를 곱해 만들 수 있는 가장 큰 '대칭수'는 얼마인가?
        int maxPal = 0;
        for (int i = 1000; i < 10000; i++) {
            for (int j = 1000; j < 10000; j++) {
                if (isPalindrome(i * j)) {
                    maxPal = i * j;
                }
            }
        }

        System.out.println("문제4 결과 : " + maxPal);
    }

    static boolean isPalindrome(int num) {
        String sNum = String.valueOf(num);

        int i = 0;
        int j = sNum.length() - 1;
        while (i <= j) {
            if (sNum.charAt(i++) != sNum.charAt(j--)) {
                return false; // 대칭수가 아니다.
            }
        }

        return true; // 대칭수가 맞다.
    }
}

---

문제5

1 ~ 23 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

정답 : 5354228880

package com.ll;

public class Main2 {
    public static void main(String args[]) {
        //문제 : 1 ~ 23 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마인가요?
        long num = 23 * 22 * 21;
        while (true) {
            for (int i = 1; i <= 23; i++) {
                if (num % i != 0) {
                    break;
                }
                else if (i == 23) {
                    System.out.println("문제5 결과 : " + num);
                    return;
                }
            }
            num += 23 * 22 * 21;
        }
    }
}

위 문제 풀이 포인트

• 수를 계속 증가시키면서, 해당 수가 1~23 에 대해서 모두 나누어 떨어지면 정답이 나오는 방법.
• 그런데 정답이 50억 보다 큰 수가 되어서, 1씩 증가시키면서 찾으면 엄청 시간이 걸리게 됨.
• 그래서 수학적인 개념을 조금 생각하여, 더 빨리 정답이 구해지도록 작성하였다.

위 풀이 과정에서 생각할 점

뭔가 당장의 문제를 풀 수만 있게 빠르게 작성한 코드이다. 완벽한 답이 아니라서 아쉽지만, 이렇게 소스를 작성하는 법도 필요하지 않을까..? 아직은 잘 모르겠다.