2장 배열 주요개념 및 복습 노트

이번 2장 배열에서는 기본적으로 배열과 for 문을 어떻게 설계하고 컴퓨팅적 사고를 하는지에 대해 물어보는 문제가 많았다. 그래서 딱히 중요한 문법이나 알고리즘이 많이 나오지 않았기 때문에 가장 중요했다고 생각되는 내용만 몇개 추려서 포스팅 할 예정이다. 

 

2-5. 소수의 개수

input 값으로 숫자를 하나 부여받고 0부터 해당 값까지 소수의 개수를 구하는 문제

풀이는 두가지로 나뉜다. 

1. 소수를 수학적으로 접근하는 방법

2. 알고리즘을 사용하는 방법

하지만 여기서 첫번째 방법으로 문제를 풀게되면 TimeLimitBreak 에 걸리기 때문에 옳지 못한
풀이이다. 하지만 정리해보자면

1. 소수를 수학적으로 접근하는 방법
나눠지는수 / 나누는수 이렇게 연산을 하는데 2중 for문을 돌면서 모든 값을 다 비교해서 나머지가 0인
상황에서 나눠지는수 == 나누는수가 되면 값을 하나 카운트 하는 방식

이 방식의 문제는 문제의 조건인 1부터 10만까지 수를 계산하려면 10만^2 번만큼 for 문이 돌기때문에
TimeLimitBreak에 걸린다. 

2. 알고리즘을 사용하는 방법
소수를 구하는 알고리즘인 에라토스테네스의 체 라는 것을 이용하여 풀면 시간 복잡도도 O(N^1/2) = N의 제곱근
으로 굉장히 빨리 구할 수 있다. 

1. 먼저 배열을 설정하고 각각의 값을 0으로 초기화한다. 

2. 나눠지는 수는 input 값으로 고정한 뒤에 나누는 수를 하나씩 올린다. 

3. 만약 나누는 수를 올리다가 나눠지는 수와의 나머지가 0인 경우 나누는 수의 배수를 전부 1로 바꾼다.
이때 for 문이 핵심인데
for (int i = 0; i < n; i = i++) {
	if (arr[i] == 0) {
    	answer++;
    }
	for (int j = i; j <= n; j = j + i) {
    	arr[j] = 1;
    }
}

이렇게 구하면 된다.

 

2-6. 뒤집은 소수

ex) 1200, 145 -> 21, 541 이렇게 뒤집은 다음 소수인지 확인하는 문제

소수를 수학적으로 접근해서 구하는 로직이 boolean 을 사용하면 된다. 

1. 뒤집은 소수의 배열인 arr[i] 가 있다고 하자

2. isPrime(int num) 을 만들어 리턴값을 boolean 으로 받는다. 

3.
for (int i = 0; i < n; i++) {
	if (isPrime(arr[i])) {
    	answer += arr[i] + " ";
    }
}

private boolean isPrime(int num) {
	if (num == 1) {
    	return false;
    }
    
    for (int i = 2; i < num; i++) {
    	if (num % i == 0) {
        	return false;
        }
    }
    
    return true;
}