Codestates pre course

자료구조와 알고리즘

Programming language : A programming language is a formal language comprising a set of instructions that produce various kinds of output. Programming languages are used in computer programming to implement algorithms.
wikipedia

자료구조와 알고리즘에 대한 기본적인 이해가 있다면 프로그램 또는 기능 구현을 보다 쉽고 효율적으로 할 수 있다.

자료구조와 알고리즘 공부를 코딩테스트 문제를 푼다고 생각하면 안된다. 따라서 자료구조와 알고리즘을 공부하고 전반적인 이해가 완료되면 그 때 문제를 풀어보기로 하자.

내일 Pre Hiring Assessments가 예정이 되어있는데 자기 진단을 한다고 생각하고 최대한 레퍼런스 도움 없이 진행을 해보고 테스트 종료 후에 스스로 피드백을 해봐야겠다. 테스트 패스보다는 양질의 피드백을 얻을 수 있는 기회가 됐으면 좋겠다.

테스트가 끝나면 예전부터 읽어 보고 싶었던 책을 읽어보려고 한다. 항상 의문을 갖는 내 코드가 좋은 코드일까..? 그 부분에 대해서 깨달음을 조금은 주지 않을까? 라고 생각한다.

소수 테스트

const isPrime = number => {
  if(number <= 1) return false;
  for(let i = 2; i < n; i++) {
    if(n % i === 0) return false; 
  }
  return true
}

위 코드의 시간 복잡도는 O(n)이다. 소수의 특징을 살펴보면 n이 소수인지 확인하려면 n의 제곱근까지만 확인하면 된다. 또한 모든 소수는 6k±1 형태이다. 그렇다면 이러한 특징을 이용해서 코드를 변경해볼 수 있다.

const isPrime = n => {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 === 0 || n % 3 === 0) return false;
  for (let i = 5; i * i <= n; i += 6) {
    if (n % i === 0 || n % (i + 2) === 0) return false;
  }
  return true;
};

위 코드의 시간 복잡도는 O(sqrt(n)) 이다. 변경된 코드로 시간 복잡도를 상당히 줄일 수 있었다.
여기서 그러면 n까지의 모든 소수를 반환하고 싶다면 아래와 같이 추가를 해주면 된다.

const makePrimes = n => {
  let result = [];
  for (let i = 0; i <= n; i++) {
    isPrime(i) && result.push(i);
  }
  return result;
};

console.log(makePrimes(23)); // [2, 3, 5, 7, 11, 13, 17, 19, 23]