[ALGORITHM] 프로그래머스 완전탐색 2번 소수찾기
소수 찾기 알고리즘
input : n (자연수)
1번 방법
2~n-1 까지 나머지가 0인게 존재하면 소수
2번 방법
2~ n/2 까지 나머지가 0인게 존재하면 소수
3번 방법
약수의 중간 값은 무조건 n의 제곱근 이하이다. 1~n의 제곱근까지 나머지가 0인게 존재하면 소수이다.
에라토스테네스의 체
boolean[] getPrimes(int n){
boolean[] primes = new boolean[n + 1];
primes[1] = true;
for(int i = 2 ; i <= n ; ++i){
if(primes[i]) continue; // 소수가 아닌(true) 수는 넘어가기
for(int j = i + i ; j <= n ; j += i){ // i를 제외한 i의 배수 모두 체크하기
primes[j] = true;
}
}
}
2부터 시작하여 소수의 배수들을 모두 걸러낸다.
이렇게 하다보면 => n까지의 모든 소수가 판별되게됨.
O(nloglogn)의 시간복잡도를 가진다.
가능한 모든 숫자 만들기
처음엔 for문으로만 해결하려했음. (DP 말고)
손계산을 우선 해보니
DP가 아닌 for문으로만 구현하기에 무리가있음.(for문을 문자 갯수만큼 만들 수 없으므로)
따라서 재귀로 접근하여 풀었음.
for (let check = 0; check < numbers.length; check++) {
for (let check1 = 0; check1 < numbers.length; check1++) {
let indexArray = [];
let string = "";
func(check, check1, string, indexArray);
}
}
function func(time, index, string, indexArray) {
indexArray.push(index);
if (time === 0) {
string += stringArray[index];
array.push(string);
} else {
string += stringArray[index];
for (let check = 0; check < numbers.length; check++) {
if (!indexArray.includes(check)) {
func(time - 1, check, string, [...indexArray]);
}
}
}
}
time
: 몇자리의 숫자인지index
: time번째에 넣을 문자의 index번호string
: 해당 반복에 만들어진 문자열indexArray
: 중복 방 들어가지 않게
참조값이 아닌 값자체를 넘겨주도록 해야함
- 올바른 출력
func(time - 1, check, string, [...indexArray]);
- 올바르지 않은 출력
func(time - 1, check, string,indexArray);
다음과 같이 indexArray
를 전달해주게 되면 값이 아닌 변수의 참조를 넘겨버린 셈이라서 그 시점의 indexArray에 접근한다.
string
변수는 왜 현재 시점의 string이 아닌 호출 시점의 string
에 접근할 수 있는 걸까?
배운점
- 호출 시점과 참조 시점 => 변수 위치를 바꾸어 보면서 이해해보자
- 소수 판별 알고리즘은 알고 있는게 좋을듯 하다.
Reference
Author And Source
이 문제에 관하여([ALGORITHM] 프로그래머스 완전탐색 2번 소수찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@rat8397/TIL-NINJA-완전탐색-2번-소수찾기
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여([ALGORITHM] 프로그래머스 완전탐색 2번 소수찾기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@rat8397/TIL-NINJA-완전탐색-2번-소수찾기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)