알고리즘 (소수, 구간 합, 투포인터)

소수?

- 2보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수.

 static boolean isFrimeNumber(int x) {
        for (int i = 2; i <= (int)Math.sqrt(x)+1; i++){ 
        // x를 제곱근으로 묶어 x ^ 2/1로 횟수를 줄였다.
            if (x % i == 0)
                return false;
        }
        return true;
    }

에라토스테네스의 체

여러 개의 수가 소수인지 판별할 때 사용하는 대표 알고리즘.

N보다 작거나 같은 모든 소수를 찾을 때 사용한다.

매우 빠르게 동작하는게 장점이다. O(NloglogN)으로 사실상 선형 시간에 동작한다 한다.

 static boolean[] prime = new boolean[1001];

    public static void main(String[] args) {
    
        Arrays.fill(prime, true);
    }

    static void eratos(int n) {
        for (int i = 2; i < (int) Math.sqrt(n) + 1; i++) {
            if (prime[i] == true) {
                int j = 2;
                while (i * j <= n) {
                    prime[i * j] = false;
                    j += 1;
                }
            }
        }
    }

이 후 true 값만 출력해주면 된다.

 

투 포인터 알고리즘

리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록해 처리하는 알고리즘.

리스트의 부분에서 필요한 것을 찾을 때 주로 사용한다.

static int twoPointer(int n) {
        int start = 0;
        int end = 0;
        int cnt = 0;
        int sum = 0;
        for (int i = start; i < array.length; i++) {
            while (sum < n && end < array.length) {
                sum += array[end];
                end += 1;
            }
            if (sum == n)
                cnt++;
            sum -= array[i];

        }
        return cnt;
    }

위 코드의 경우 배열에 음수가 존재하면 문제를 해결할 수 없다.

다른 느낌으로 정렬되어 있는 두 배열의 합집합을 구할 수도 있다.

    static int[] sumarray(int[] arr1, int[] arr2) {
        int fistart = 0;
        int sestart = 0;
        int[] arr = new int[arr1.length + arr2.length];
        int idx = 0;
        while (fistart < arr1.length || sestart < arr2.length) {
            if (sestart >= arr2.length || 
            (fistart < arr1.length && arr1[fistart] <= arr2[sestart])) {
                arr[idx] = arr1[fistart];
                fistart++;
            }else {
                arr[idx]=arr2[sestart];
                sestart++;
            }
            idx++;
        }

구간 합

연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구할 때 쓴다.

static int arrangeSum(int [] array, int left,int right){
        int sum =0;
        int [] prefixSum = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
            prefixSum[i]=sum;
        }
        return prefixSum[right]-prefixSum[left-1];
    }