[JAVASCRIPT][PCCP 대비] 프로그래머스 레벨1, 2 빠르게 풀고 메모하기

코테는 안한지 오래됐지만... PCCP 무료 응시권을 헛되게 날린 수 없어서... 최대한 해 보는 벼락치기 ⚡️

프로그래머스 레벨1, 2 문제들 최대한 다시 풀어보자 !!

 

 

---

 

🧩 약수와 소수

약수 = 어떤 수를 나누었을 때 나머지가 0인 수를 그 수의 '약수'라고 함

소수 = 약수로 1과 자기 자신만을 갖는 어떤 수 (= 1과 자기자신으로만 나누어지는 수)

ex) 5는 1, 5로 나누어진다. 5의 약수는 1과 5이다. 5는 소수다.

4는 1, 2, 4로 나누어진다. 4의 약수는 1, 2, 4이다. 4는 소수가 아니다.

 

약수를 구할 때에는 for문으로 1부터 해당 값까지 전부 탐색해도 가능은 하지만 보통 시간초과함

때문에 1부터 해당 값의 제곱근까지만 탐색하는 방법을 사용 (#136798)

- Math.sqrt(숫자) : 숫자의 제곱근(^1/2)

- Number.isInteger(숫자) : 숫자가 정수라면 true, 아니면 false 반환

function divisor(num) { // 약수의 갯수
    if(num === 1) return 1;
    let count = 2; // 양 끝 값, 1과 num 확보
    const sqrtNum = Math.sqrt(num);
    for(let i=2; i<sqrtNum; i++){
        if(num % i === 0) count+=2;
    }
    if(Number.isInteger(sqrtNum)) count++;
    return count;
}

 

약수의 개수가 홀수 = 제곱근이 정수 (#77884)

if(Number.isInteger(Math.sqrt(i)) return "odd";

 

소수인지 여부를 확인하기 위해 약수를 구하는 함수 로직을 일부 사용 (#12977)

function isPrime(num) { // 소수인지 판별
    const sqrtNum = Math.sqrt(num);
    if(Number.isInteger(sqrtNum)) return false;
    for(let i=2; i<sqrtNum; i++){
        if(num % i === 0) return false;
    }
    return true;
}

 

 

여기에서 더 불필요한 반복을 줄이기 위해서는 Set 활용한 에네토스테네스의 체 알고리즘 이용 (#12921)

2 ~ 어떤수 에 해당하는 리스트를 먼저 만든 뒤 (2, 3, 4, 5, ...)

2를 제외한 2의 배수들을 리스트에서 제거 (2, 3, 5, 7, 9, ...)

3을 제외한 3의 배수들을 리스트에서 제거 (2, 3, 5, 7, 11, ...)
와 같은 형식으로 순환하여 소수의 갯수를 구한다.

function seekPrimes(n) { // 에라토스테네스의 체 알고리즘 적용한 1~n 사이 소수 찾기
    const set = new Set([2]); // set에 2 추가
    for(let i=3; i<=n; i+=2){ // set에 2를 제외한 2의 배수들 제거 (= 3 이상의 홀수들 추가)
        set.add(i);
    }
    for(let j=3; j<Math.sqrt(n); j++){ // n의 제곱근까지 차례로 순환
        if(set.has(j)){
             for(let k=j*2; k<=n; k+=j){    
                set.delete(k); // set에 j를 제외한 j의 배수들 제거
             }
        }
    }
    return set.size; // 순환 종료 후 set의 크기가 소수의 갯수
}

 

 

🧩 최대공약수와 최소공배수

최대공약수와 최소공배수 (#12940)

function gcd(n, m) { // 최대공약수
    return m ? gcd(m, n % m) : n;
}

function lcm(n, m) { // 최소공배수
    return n * m / gcd(n, m);
}

 

 

🧩 피보나치의 수

피보나치의 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 (#12945)

let fibo = [0, 1]; // 메모이제이션을 위해 전역으로 선언
function F(n) { // F(n) 값을 구하는 함수
    if(fibo.length > n) return fibo[n];
    for(let i=fibo.length; i<=n; i++) {
        fibo[i] = fibo[i-1] + fibo[i-2]; // index를 이용해 직접 배열 업데이트 (push와 동일 결과)
    }
    return fibo[n];
}

console.log(F(5)) // ? 5

 

이 때 재귀 호출을 사용하지 않는 이유는 JavaScript의 경우 재귀 호출을 할 수 있는 횟수가 지정되어 있고, 해당 횟수를 넘어 호출하면 런타임 에러를 내도록 설계되어 있기 때문. 재귀 호출 대신에 for문을 활용하는 DP(dynamic programming, 동적 계획법)를 사용해야 함

 

 

F(n)을 특정 수로 나눈 나머지 값을 요구하는 경우, F(n)에만 % 계산하면 JavaScript가 표현할 수 있는 자료형의 범위를 넘어가기 때문에 오버플로우가 발생. 모든 피보나치 값 연산 과정에 % 해주어야 함

fibo[i] = (fibo[i-2] + fibo[i-1]) % 1234567; // 모든 연산에 % 1234567

 

 

 

 

🧩 문자 정렬

sort() 메서드를 이용하여 문자 정렬 시 아스키코드의 순방향으로 정렬됨 (#12917)

A(65) - Z(90) - a(97) - z(122) 순 정렬

const s = ["A", "b", "c", "D", "E", "f"];
[...s].sort(); // [ 'A', 'D', 'E', 'b', 'c', 'f' ]

 

비교를 명시적으로 작성하려면 다음과 같은 삼항 연산자를 활용 (#12915)

정렬 로직을 좀 더 명확히 표현하고자 할 때, 혹은 특정 조건에 따른 복잡한 정렬 기준을 적용하고자 할 때 유용

const s = ["A", "b", "c", "D", "E", "f"];
[...s].sort((a, b) => a > b ? 1 : -1); // [ 'A', 'D', 'E', 'b', 'c', 'f' ]

 

 

🧩 문자 변환

문자를 아스키코드로 변환하거나, 역으로 아스키코드를 문자로 변환할 수 있음 (#12926)

- 문자.charCodeAt() : 문자를 아스키코드로 변환

- String.fromCharCode(숫자) : 아스키코드를 문자로 변환

const ascii = "A".charCodeAt(); // 65
const str = String.fromCharCode(65); // A

 

 

🧩 n진법

parseInt() 메서드와 toString() 메서드는 서로 반대 작업을 수행 (#68935)

- parseInt(문자열, n) : n진법으로 표현된 문자열을 10진법으로 표현된 숫자로 변환 (n -> 10)

- 숫자.toString(n) : 10진법으로 표현된 숫자를 n진법으로 표현된 문자열로 변환 (10 -> n)

const c16to10 = parseInt('ff', 16); // 255
const c10to2 = (10).toString(2); // 1010

 

여기에서 만일 n자리수로 표현하고자 할 때 padStart() 메서드를 사용할 수 있음 (#17681)

- 문자열.padStart(크기, 문자) : 앞에서부터 문자를 채워 문자열 크기를 요구대로 맞춤

- 문자열.padEnd(크기, 문자) : 뒤에서부터 문자를 채워 문자열 크기를 요구대로 맞춤

const c10to2 = (10).toString(2); // 1010
const toByte = c10to2.padStart(8, '0'); // 00001010

 

 

🧩 2차원 배열

0으로 채워진 2차원 배열 만들기 (#92334)

const arr = Array.from(Array(5), () => Array(3).fill(0));
// [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]

 

 

🧩 Set

중복없는 값을 모으기 위해서 사용하는 자료구조 Set

let newSet = new Set([1, 1, 1, 2, 2]); // Set(2) {1, 2}

 

Array.from() 메서드 또는 전개 연산자를 사용하면 Set을 Array로 변환할 수 있음 (#68644)

console.log([...newSet]); // ? [1, 2]
console.log(Array.from(newSet)); // ? [1, 2]

 

size 를 통해 Set의 크기 측정 (#1845)

console.log(newSet.size); // 2