coding test

정해진 시간 내에 적절한 알고리즘을 활용한 문제를 해결할 수 있는 능력을 평가하는 것

알고리즘의 성능을 평가하는 척도

• 공간을 많이 사용하는 대신 시간을 단축하는 방법이 흔히 사용된다.

• 일반적으로 연산 횟수가 10억을 넘어가면 1초 이상의 시간 지연 발생한다고 본다.

• 현실 세계에서 동작 시간이 1초 이내인 알고리즘을 설계할 필요가 있다.

시간 복잡도(Time Complexity)

특정 입력값에 따라 알고리즘의 수행 시간을 평가

수행 시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행 시간을 평가한다.

기본 연산이란?

• 데이터 입출력

• 제어 연산

• 산술연산

시간 복잡도는 알고리즘이 복잡해질수록 평균적인 경우를 구하기 어렵기 때문에 최악의 경우로 성능을 파악한다.

공간 복잡도(Spade Complexity)

특정 입력값에 따라 알고리즘이 메모리를 얼마나 차지하는지를 평가

입력 공간 + 알고리즘 자체가 필요로 하는 공간을 의미한다.

공간 복잡도 규칙

• string을 제외한 원시값은 O(1)

• string, 참조값(array, object)는 O(n)

  • 문자열 길이가 50이라면 길이가 1인 문자열 보다 50배 많은 공간을 차지한다

Big O 표기법

여러 코드를 비교하기 위해 알고리즘의 성능을 평가하여 수치로 나타낸 방법

입력값이 커질수록 알고리즘의 수행시간(시간 복잡도)이 어떻게 변하는지 설명한다.

bigO

Big O 공식

• 가장 빠르게 증가하는 항(차수가 가장 큰 항)만을 고려

• 차수가 가장 큰 항에서 계수를 제외하여 표기

• 결과적으로 표현식은 단순하게 나타내진다.

Big O 필요성

• 같은 문제를 해결하는 알고리즘을 비교하기 위해 필요하다.

• 여러 접근법의 장단점을 애기할 때 필요

• 내가 작성한 코드를 더 잘 이해하고, 더 좋은 코드를 작성할 때 도움이 된다.

Node.js로 코딩테스트 풀기

백준은 js의 문제가 node.js의 입출력 형태로 문제가 제공되니 참고하자.

fs 모듈

입력 데이터가 text 파일로 주어지는 경우, 파일 시스템 모듈을 활용

전체 텍스트를 읽어온뒤 개행으로 분리하여 최종적으로 배열형태로 입력값을 받아온다.

let fs = require('fs');
let input = fs.readFileSync('파일경로').toString().split('\n');

console.log(input);

readline 모듈

한 줄 씩 입력을 받아서, 처리하는 경우 readline 모듈 활용

const rl = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

let input = [];
rl.on('line', function(line) {
  // 콘솔 입력 창에서 Enter 입력할 때마다 호출
  input.push(line); 
}).on('close', function() {
  // 콘솔 입력이 종료되면 호출
   console.log(input);
   porcess.exit();
});