알고리즘 특강

• 코딩 문제를 해결할 때 컴퓨터의 연산을 5초 이내로 하도록 풀어야한다.

• 어림잡아 일반적으로 js 연산 속도를 초당 2000만번 정도로 생각하고 문제로 주는 입력값의 크기 즉 배열의 길이와 복잡도를 고려하여 5초 안에 연산을 마치도록 알고리즘을 사용하여 작성한다.

문제 해결 과정

1. 지문읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제 해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩

복잡도

• 복잡도는 알고리즘의 성능을 나타내는 척도이다.

• 시간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 수행 시간 분석

• 공간 복잡도: 특정한 크기의 입력에 대해 알고리즘의 메모리 사용량 분석

• 일반적으로 복잡도가 낮을수록 좋다.

BigO

• 가장 빠르게 증가하는 항만을 고려하는 표기법

• 반복문을 중첩하면 반복문 중첩 갯수만큼 n^n 이 된다.

• 완벽하게 반복문 중첩이 n^2 로 되는 것은 아니다.

• 문제의 입력값의 양을 복잡도와 고려하여 문제를 해결해야 한다.

BOJ 에서 코테 문제 풀기

js 기본 입력 방식

• 입력 값은 파일의 내용을 읽어와서 입력 하도록 한다.

//readline 모듈보다는 fs를 이용해 파일 전체를 읽어 들여 처리하기
let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
// let input = fs.readFileSync('input.txt').toString().split('\n');

• 문제 풀때는 input.txt 를 만들어 풀고

• 제출시에는 /dev/stdin 으로 위치를 바꿔 제출!

• 출력은 console.log() 사용