항해 99 - 2023.01.31 TIL

알고리즘 모의고사가 있어서 응시했는데, 생각보다 문제가 원활하게 풀리지는 않은 것 같다.

내가 선택한 문제는 3번 문제로, 실수를 다루는 문제였다.

저번에 풀었던 알고리즘 문제 중 실수를 다루는 문제가 있었기 때문에 자신있게 선택했는데 결과값이 이상하게 나와서 당황했다. 하나씩 값을 찍어보면서 원인을 확인해보니.. break 문을 적절하지 않은 위치에 놓아서 발생한 문제였다. 괄호를 잘 확인하는 습관을 들여야겠다..

 

알고리즘 문제 풀이는 마라톤 단계까지는 완료가 되었고, 오늘부터 챌린지 단계에 돌입했다.

마라톤 단계에서는 어느정도 보다보면 해답이 나왔었는데, 챌린지 단계는 계속 이해되지 않는 개념이 종종 있었던 것 같다..

 

 

 

약수의 개수와 덧셈

주어지는 두개의 정수의 범위로, 약수는 더하고 짝수는 뺄셈하여 합계를 반환하는 문제이다.

class Solution {
    public int solution(int left, int right) {
        int answer = 0;
        for (int i = left; i <= right; i++) {
            int cnt = 1; //1은 모든 수의 약수이므로 미리 포함
            for (int j = 2; j <= i; j++) {
                if(i % j == 0){
                    cnt++;
                }
            }
            if(cnt % 2 == 0){
                answer += i;
                System.out.println(answer + "+" + i + " = "+ answer);
            }else{
                answer -= i;
                System.out.println(answer + "-" + i + " = "+ answer);
            }
        }
        return answer;
    }
}

 

 

 

약수의 합

주어지는 정수의 약수를 모두 더한 값을 반환하는 문제이다

class Solution {
    public int solution(int num) {
        int answer = 0;
        for (int i = 1; i <= num; i++) {
            if(num%i == 0){
                answer += i;
            };
        }
        return answer;
    }
}

 

 

 

예산

주어진 예산 만큼 최대한 많은 부서의 요청을 완수해야하는 문제이다.

import java.util.Arrays;

class Solution {
    public int solution(int[] d, int budget) {
        int answer = 0;
        Arrays.sort(d);
        for (int i = 0; i < d.length; i++) {
            budget -= d[i];
            if(budget < 0){
                break;
            }
            answer++;
        }
        return answer;
    }
}

숫자가 적을 수록 합산 값이 적어지기 때문에, 예산 배열을 정렬해준 뒤에 예산이 0이하로 떨어질때까지 요청한 예산만큼을 빼주었다. 빼는 횟수만큼 answer를 더해주었다.

 

 

 

최대공약수와 최소공배수

주어지는 두 숫자의 최대공약수와 최소공배수를 구하는 문제이다.

class Solution {
    public int[] solution(int n, int m) {
        // 최대공약수 산출 후 최소공배수 계산
        int max = Math.max(n,m);
        int min = Math.min(n,m);
        
        while(min != 0){
            //유클리드 호제법 > 최대공약수 산출
            // a를 b로 나눈 나머지를 r이라 하면, 
            //a, b의 최대공약수는 b와 r의 최대공약수와 같다. (단 a > b)
            int r = max % min;
            max = min;
            min = r;
        }
        int multi = n * m / max;   // 최소 공배수 = 두수의 곱 / 최대공약수
        int answer[] = {max, multi};
        return answer;
    }
}

최대 공약수와 최소 공배수를 구하는 공식을 알면 쉽게 풀 수 있는 문제였다.

시간을 많이 들였음에도 해결 방법이 생각나지 않아 정답을 보고 풀이방법을 외우고자 했다.

 

최대공약수를 구하는 방법으로는 유클리드 호제법이라는 공식이 있어서 참고했다.

r = a % b 면, a , b의 최대 공약수는 b와 r의 최대공약수와 같으므로, a를 b에, b에 r을 대입해서 반복으로 나머지를 계산해주다 보면 최대 공약수를 구할 수 있다.

 

최소공배수는 두수의 곱 / 최대 공약수로 간단히 구할 수 있다.

 

 

 

K번째 수

2차원 배열에 있는 값을 기준으로 i - j 까지 배열을 자르고, k번째에 있는 수를 구하는 문제이다.

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        ArrayList<Integer> intArr = new ArrayList<>();
        for (int i = 0; i < commands.length; i++) {
            int from = commands[i][0];
            int to = commands[i][1];
            int n = commands[i][2];

            System.out.println(from + "," + to + "," + n);
            int[] arr = Arrays.copyOfRange(array, from-1, to);
            Arrays.sort(arr);
            intArr.add(arr[n-1]);
        }
        int[] answer = new int[intArr.size()];

        for (int i = 0; i < intArr.size(); i++) {
            answer[i] = intArr.get(i);
        }
        return answer;
    }
}

배열의 범위를 복사하는 함수가 키워드였던 문제같다.

Arrays.copyOfRange(배열, from, to) 함수로 배열을 원하는 범위만큼 복사할 수 있다. 

from 다음 인덱스의 요소부터 복사되므로 주의해야한다.

 

 

 

나머지가 1이 되는 수 찾기

주어지는 수를 나눴을 때 나머지가 1이 되는 수의 숫자를 반환하는 문제이다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 1; i < n; i++) {
            if(n % i == 1){
                answer = i;
                break;
            }
        }
        return answer;
    }
}

 

 

 

소수 찾기

1부터 입력받은 숫자 n 사이의 소수의 개수를 반환하는 문제이다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] arr = new int[n + 1];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = i + i; j <= n; j += i) {
                arr[j] = 0;
            }
        }

        for (int i = 2; i < arr.length; i++) { // 소수에 0과 1은 포함되지 않기때문에 제외한다.
            if(arr[i]==1){
                answer++;
            }
        }
        return answer;
    }
}

이전에 소수를 계산하는 문제를 풀어봐서 쉽게 풀어질 것 같았는데, 횟수가 많아질 경우 시간이 초과되어 실패했다.

소수 계산 방법이 여러가지가 존재했는데, 두 가지 방법을 눈여겨 보았다. 제곱근을 이용하는 방법과 에라토스테네스의 채 라는 계산방법이다.

 

제곱근 이용

자연수 n이 소수이기 위한 필요 충분 조건은 n이 n의 제곱근보다 작은 어떤 소수로도 나눠지지 않는다. 수를 수로 나누어 떨어진다면 그떄의 몫은 반드시 그 수의 제곱근보다 작기 때문이다.

 

제곱근의 개념을 잘 이해하고 있지 못해서 이 방법은 pass했다. 대충 소수를 구할때는 n번 반복할 필요없이 sqrt(n)번만 반복하는게 더 효율적이라는 것은 알겠다..

 

 

에라토스테네스의 채

'소수는 배수가 아니다.'

원리는 그림을 보면 이해할 수 있다.

에라토스테네스의 체 출처 : 위키피디아

 

1. 2부터 n까지의 모든 수를 나열한다.

2. 2는 소수이므로 소수로 입력한다. 후에 2의 배수들은 소수가 아니게 되므로 n까지의 자기 자신을 제외한 2의 배수를     모두 지운다.

3. 3은 소수이고 2의 배수가 아니므로 지워지지 않았다. 똑같이 n까지의 3의 배수를 모두 지워준다.

4. 5도 소수이고 지워지지 않았다. n까지의 5의 배수를 모두 지워준다.

5. n의 제곱근전의 최대 소수까지 반복해준다.

 

소수인지 아닌지 판별할 배열 arr 을 생성해주었다. (1은 소수, 0은 소수가 아닌 값으로 판정)

그리고 반복문으로 각 숫자의 배수들에 해당하는 index를 0으로 바꿔주었다.(arr 배열의 index와 반복될 숫자의 값을 일치시켜줘야한다.)

 

마지막으로 배열에 있는 1값은 카운트하여 반환했다.

 

 

 

느낀 점

난이도가 올라갈수록 수학적인 사고가 중요해지는 것 같다. 그리고 무작정 풀이에 매달려서 결과를 얻어낸다해도, 문제가 통과되는 것이 아니기 때문에 조금 전략적으로 접근해야할 필요를 느꼈다.

최대 공약수 산출처럼 공식이 필요한 문제는 답안을 보면서 공식을 어떻게 활용하는지 알고, 공식을 암기하는 방법으로 진행해야겠다. 

열심히 풀었는데 효율성에서 실패가 나오면 정말 허탈한 것 같다..

어려운 단계로 넘어갈수록 시간연속성이라는 개념을 공부해야겠다는 생각이 든다..