[이것이 코딩테스트다] 10. 기타 알고리즘

이것이 취업을 위한 코딩테스트다.

 

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다.

(원본 소스코드 : https://github.com/ndb796/python-for-coding-test/)

 

 

1. 소수 판별하기

1) 소수를 판별하는데 제곱근까지만 확인하면 된다.

- 소수(Prime Number) : 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 떨어지지 않는 자연수

- a라는 자연수를 소수인 지 확인하기 위해서는 2~(a-1) 의 수로 나누어 지는 지 확인해야한다.

- 하지만 a의 제곱근까지만 확인해도 충분하다. (아래의 소스코드 참고)

public class Main {

	// 소수 판별 
	// 2 이상의 자연수만 판별 가능 
    public static boolean isPrimeNumber(int x) {
        // 2 ~ x의 제곱근까지만 확인
    	// Math.sqrt : 제곱근 
        for (int i = 2; i <= Math.sqrt(x); i++) {
            // x가 해당 수로 나누어떨어진다면
            if (x % i == 0) {
                return false; // 소수가 아님
            }
        }
        
        // 위의 반복 중에서 나누어 떨어지는 경우가 없으면 소수임
        return true; 
    }

    public static void main(String[] args) {
    	// 6은 소수가 아님 
        System.out.println(isPrimeNumber(6));
        
        // 11은 소수임 
        System.out.println(isPrimeNumber(11));
    }

}

 

 

2) 에라토스테네스의 체

- 여러 개의 수가 소수인지 아닌지를 판별할 때 사용한다. (N보다 작거나 같은 모든 소수를 찾을 때 사용)

- 동작 과정

1. 2부터 N까지의 모든 자연수를 나열한다.
2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다.
3. 남은 수 중에서 i의 배수를 모두 제거한다. (i는 제거하지 않음)
4. 더 이상 반복 할 수 없을 때까지 2번과 3번의 과정을 반복한다.

import java.util.Arrays;

public class Main {

	public static int n = 1000; // 2 ~ 1,000 사이의 모든 수 소수 판별 
	
    public static boolean[] arr = new boolean[n + 1]; 

    public static void main(String[] args) {
    	// 모든 수가 소수라고 가정한다. 
        Arrays.fill(arr, true); 
        
        // 0과 1은 소수가 아님 
        arr[0] = false;
        arr[1] = false;
        
        // 에라토스테네스의 체 알고리즘 수행
        // 2부터 n의 제곱근까지의 모든 수를 확인
        for (int i = 2; i <= Math.sqrt(n); i++) {
            // i가 소수인 경우(남은 수인 경우)
            if (arr[i] == true) {
                // i를 제외한 i의 모든 배수는 소수가 아님!
                int j = 2;
                while (i * j <= n) {
                    arr[i * j] = false;
                    j += 1;
                }
            }
        }
        
        // 기록된 모든 소수 출력
        for (int i = 2; i <= n; i++) {
            if (arr[i] == true)
            	System.out.print(i + " ");
        }
    }

}

 

 

3) 투 포인터 : 리스트에 순차적으로 접근해야할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘

- 특정한 합을 가지는 부분 연속 수열 찾기 (M : 찾을 부분 합)

1. 시작점과 끝점이 첫 번째 인덱스(0)를 바라보도록 설정
2. 현재 부분합이 M과 같다면 카운트
3. 현재 부분합이 M보다 작다면 end 1 증가
4. 현재 부분합이 M보다 크거나 같다면 start 1 증가
5. 모든 경우를 확인할 때까지 2~4 반복

public class Main {

	public static void main(String[] args){
		// TODO Auto-generated method stub
		
		// 데이터의 갯수
		int N = 5;
		
		// 찾을 부분합
		int M = 7;
		
		// 데이터
		int[] data = {1,2,3,4,5};
		
		// 시작점과 끝점은 0으로 시작
		int start=0, end = 0;
		
		// 찾을 부분합과 일치하는 부분수열의 갯수
		int count = 0;
		
		// 시작점이 끝까지 갈 때까지 반복
		while(start<N) {
			
			// 시작점부터 끝점 사이의 부분 수열의 합 구하기
			int tempSum = 0;
			for(int i=start; i<end; i++) {
				tempSum += data[start];
			}
			
			// 부분 수열의 합이 찾을 부분합과 같다면 카운트
			if(tempSum == M) {
				count++;
			}
			
			// 부분 수열의 합이 M보다 작다면 end 증가
			if(tempSum < M) {
				end++;
			}
			
			// 부분 수열의 합이 M보다 크거나 같다면 start 증가
			else {
				start++;
			}
		}
		
		System.out.println("결과 : " + count);
	}

}

 

4) 구간 합 계산

1. 배열의 각 원소에 대한 접두사 합을 계산하여 배열 p에 저장
2. 배열의 L인덱스 ~ R인덱스 사이의 합계  = p[R] - p[L-1]

import java.util.*;

public class Main {
    public static int n = 5; // 데이터의 개수 N과 데이터 입력받기
    public static int arr[] = {10, 20, 30, 40, 50};
    public static int[] p = new int[6];

    public static void main(String[] args) {
        // 접두사 합(Prefix Sum) 배열 계산
        int sumValue = 0;

        for (int i = 0; i < n; i++) {
            sumValue += arr[i];
            p[i + 1] = sumValue;
        }

        // 구간 합 계산(두 번째 수부터 네 번째 수까지)
        int left = 2;
        int right = 4;
        System.out.println(p[right] - p[left - 1]);
    }
}