[TIL-003] 알고리즘 - 에라토스테네스의 체 연습, 기술면접 스터디 준비

Today목표 : 4/12일 Challenger's Challenge 5개 문제  풀기 ✅

---

알게된 점,

1. 완주하지 못한 선수 - Map객체와 해시 테이블 🟡

일반 객체와 Map객체의 차이점

일반 객체는 모든 key를 순환하면서 해당하는 키값을 찾지만, Map은 해당 키값을 검색하여 찾는다. 따라서 시간 복잡도를 많이 줄일 수 있는 해시 테이블 자료구조에 대해 공부하고 Map객체를 활용하여 풀어보도록 하자. 

프로그래머스

 

 

2. 에라토스테네스의 체 - 소수 찾기

요구 사항 : 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수 만들기

문제 사항 : n번째 까지 숫자 중 소수의 갯수를 구하라. 시간복잡도에 걸리는 상황이 발생했다.

어제 배운 에라토스테네스의 체를 사용할 수 있는 좋은 기회가 왔다!

이 공식을 사용해서 문제를 풀어보았다.

 

다음은 먼저 실패한 케이스다.

1. n번째 까지의 배열을 생성하여 소수 구하기 : 실패

1) n번째 까지의 배열 생성하기

먼저 for문을 순회하여 소수를 구하기 위해서는 숫자 n까지의 배열을 생성해야 하는데, for문을 안쓰고 생성할 수 있는 방법을 찾아보았다. Array.from()를 사용하면 쉽게 배열을 원하는 길이만큼, 값을 가공하여 생성할 수 있었다.

Array.from(A, B) : A에는 배열로 반환하고자 하는 이터러블 객체, B에는 배열의 모든 요소에 대해 호출할 맵핑 함수를 선언한다.

1) 첫번째 인자에 {length: 9}를 넣어주면, 길이가 9인 배열이 생성된다.

[undefined,undefined,undefined,undefined,undefined,undefined,undefined,undefined,undefined]

2) 두 번째 인자에 (v, i)=>i+1을 하면 index+1의 값을 담은 배열이 생성된다.

const arr = Array.from({length:9}, (v,i)=>i+1)); 

//[1, 2, 3, 4, 5, 6, 7, 8, 9]

이 외에도 여러가지 방법이 있으니 다음 게시글을 참조하여 공부하면 좋을 것 같다.

1~N까지의 숫자 배열 만들기(with js)

하지만 이 문제에서는 n까지의 숫차적인 숫자들 중 소수인 갯수를 찾는 것이기 때문에, 굳이 배열을 생성하지 않고도 for문으로 i를 증감시켜 갯수를 구했다. 

 

2) for문으로 소수 찾기

우선 0,1은 소수가 아니기 때문에 for문에서 2부터~ n까지의 숫자를 순환하도록 하였다. 각 숫자가 소수인지 확인해 보기 위해 1과 자신을 제외한 2부터 ~ n-1까지 순회하며 나누어 떨어지는 숫자가 있는지 확인하고, 없으면 소수로 count되도록 코드를 작성했다.

   let count = 0;
    for(let i = 2; i <= n; i++){
        let length = 0;
        for(let j = 2; j < i; j++){
            if(i % j === 0){
                length++
            }
        }
        if(length === 0){
            count++
        }
    }
    return count

❗문제는 이 과정에서 테스트 케이스는 통과되지만, 시간복잡도에서 너무 오래걸려 실패처리가 되었다!

따라서 어제 배운 에라토스테네스의 체 공식을 이용하여 풀어보도록 하자.

 

 

2. 에라토스테네스의 체 공식을 사용하여 소수 찾기 : 성공 ✅

1. 배열을 생성할 때는, n의 갯수만큼 생성하여 true 또는 false의 값들로만 채워준다.

// 배열은 0부터 시작하므로 n+1, 0과 1은 소수가 아니므로 2개는 false로 만들어 놓고, 
// 나머지를 갯수만큼 true로 채워준다.
    let arr = Array(n+1).fill(true).fill(false, 0, 2);

우선 갯수를 n+1로 하는 이유는 0이 포함되어있기 때문이다. 또 0,1은 소수가 아니므로 제외하기 위해 초기설정으로 false로 설정으로 우선 false로 먼저 생성해 놓는다.

[false, false, true, true, true, true, true, true, true, true, true]

2. 소수가 아닌 것들은 false로 변환하여 배열에서 true인 값만 찾아 갯수를 구해준다.

function solution(n) {
    // 배열은 0부터 시작하므로 n+1, 0과 1은 소수가 아니므로 2개는 false로 만들어 놓고, 나머지를 갯수만큼 true로 채워준다.
    let arr = Array(n+1).fill(true).fill(false, 0, 2); 
    // 이후 소수가 아닌 것들은 false로 변환하여
    for(let i=2; i*i<=n; i++){
        if(arr[i]){
            for(let j=i*i; j<=n; j+=i){
                arr[j] = false;
            }
        }
    }
    // filter로 true인 갯수만 뽑는다.
    console.log(arr.filter(e => e).length)
}

채점 결과 시간 복잡도를 모두 통과하는 것을 볼 수 있다.

 

 

3. 기술면접 스터디 1회차

내가 선택한 이번 주 발표 주제는 '자바스크립트의 비동기 처리 방식에는 어떤 것들이 있고, 각각의 특징은 무엇인가요?' 이다.

거의 강의만 듣고 이해가 어려워 잘 모르는 내용이기 때문에 스스로 확실하게 알 수 있도록 공부하고자 선택했다. 일단 내가 이 주제에 있어서 무엇을 모르는지 정리해 보았다. 

1. 동기와 비동기에 대한 이해가 필요하다. 비동기 처리가 왜 필요한 것인지, 비동기 처리의 단점과 이를 보완하여 동기적으로 순서를 제어하도록 나온 문법들을 공부하자. ✅

2. 동기적 콜백과 비동기적 콜백, 둘의 차이점에 대한 이해가 필요하다. ✅

3. 개발의 범위, 복잡도가 증가할 수록 콜백 함수를 이용한 비동기 처리가 증가하게 되고, 이는 콜백 지옥을 부르게 된다. 그로 인한 콜백지옥의 단점들은 무엇인지, 이를 개선하기 위해 Promise를 왜 사용해야 하는지 공부하자.

4. Promise의 개념과 사용 방법에 대해 공부하자. 생성부와 실행부를 나눠서 예제로 공부하자. Promise 체이닝 다음에 코드가 온다면, Promise는 비동기적으로 실행되고, Promise 체이닝 다음 코드는 바로 실행되는지 확인해 보자.

5. async-await 문법에 대해 공부하고, await을 사용하지 않았을 때 어떤 결과가 나오는지 예상해 보자.

 

오늘은 1,2번에 대해 공부했으니 내일은 3~5번까지 학습한 후, 내용을 정리해 기술면접 깃헙에 올리고 발표준비를 마쳐야겠다❕