시간복잡도와 빅오 표기법(Big-O)
시간 복잡도
특정한 크기의 입력에 대하여 알고리즘의 수행시간 분석 → 알고리즘의 성능을 나타내는 척도
❗️ 동일한 기능을 수행하는 알고리즘이 있다면, 시간 복잡도가 낮을수록 우수하다.
ex) T(n) = 5n^2+3n+30
- 입력값의 크기가 동일하더라도, 입력값의 형태에 따라 시간복잡도는 다양하게 나옴
- Worst case: 가장 높은 시간 복잡도
→ Average case는 구하기 어려워서 값이 비슷한 Worst case로 시간복잡도 구함 - Average case: 평균값의 시간 복잡도
- Best case: 가장 낮은 시간 복잡도
빅오 표기법(Big-O)
입력값 n에 대한 실행시간 함수가 존재한다면, 시간복잡도의 최고 차항의 계수만을 표기하여 빅오를 표기할 수 있다.
ex) C=O(1)
an+b=O(n)
an^2+bn+c=O(n^2)
문제 풀이에 자주 사용되는 JS 문법
표준 출력은 console.log() 이용
// 단순히 문자열을 출력
console.log('Hello World');
result=35;
// 템플릿 리터럴을 사용해 문자열 내부에 변수를 포함 (백틱 문자 사용)
console.log(`정달은 ${result}입니다.`);기본적인 사칙 연산 기능 제공
a=7;
b=3;
console.log(a+b); // 10
console.log(a-b); // 4
console.log(a*b); // 21
console.log(parseInt(a/b)); // 몫만 남기기 // 2
console.log(a%b); // 1출력 시간을 단축하기 위한 방법
- 하나의 문자열에 결과를 저장해서 한꺼번에 출력하는 것이 더 빠르게 수행됨
let answer='';
/*
여러 출력 결과를 한 줄에 하나씩 출력할 때 매 번 console.log()를 실행하지 않고,
**하나의 문자열에 결과를 저장해서 한꺼번에 출력하는 것이 더 빠르게 수행됨**
*/
for (let i=1; i <= 100; i++){
answer+=i+'\n'; // 문자열로 변환하여 기록
}
console.log(answer);fs 모듈: 입력 데이터가 텍스트 파일 형태로 주어지는 경우 사용하는 파일 시스템 모듈
ex) /dev/stdin 파일에 적힌 텍스트를 읽어오는경우, 다음과 같이 작성
// 기능: 전체 텍스트를 읽어 온 뒤, 줄바꿈 기호를 기준으로 구분하여 리스트로 변환
// readline 모듈보다는 fs를 이용하여 파일 전체를 읽어 들여 처리
let fs=require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');
console.log(input);
// [ '5', '40 20 39 29 40' ]// txt
5
40 20 39 29 40readline 모듈: 한 줄씩 입력을 받아서, 처리하여 정답을 출력할 때 사용
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() {
// 콘솔 입력 창에서 Ctrl+C 혹은 Ctrl+D를 입력하면 호출(입력의 종료)
console.log(input);
process.exit();
});조건문: 조건에 따라서 프로그램의 흐름을 결정할 때 사용할 수 있는 문법
- condition: 참 혹은 거짓을 반환하는 조건식
- statement1: condition1이 참일 대 실행되는 구문
- statement2: condition1이 거짓이고, condition2가 참일 때 실행되는 구문
- statement3: condition1과 condition2가 거짓이고, condition3가 참일 때 실행되는 구문
- statementN: 앞의 모든 조건문이 거짓일 떄 실행되는 구문
if (condition1)
statement1
else if (condition2)
statement2
else if (condition3)
statement3
...
else
statementN반복문: 조건에 따라서 특정한 코드를 반복하고자 할 때 사용할 수 있는 코드
for 반복문
- 초기문이 존재한다면 초기문이 먼저 실행
- 조건문이 참이라면 블록 내부 코드가 실행되고, 거짓이면 반복문이 종료됨
- 블록 내부 코드가 실행된 뒤에 증감문이 실행됨
for (초기문; 조건문; 증감문){
// statements
}ex) 1부터 100까지의 합 계산
let sum=0
for (let i=1; i<=100; i++){
sum+=i;
}
console.log(sum);while 반복문
- while문은 조건문이 참일 때 실행되는 반복문
- 블록 내부의 코드가 실행되기 전에 참 혹은 거짓을 판단
while (조건문){
// 실해되는 코드 부분
}Number와 String의 형태 변환
: 수(Number) 데이터와 문자열(string) 데이터 간의 상호 변환이 필요
/*
Int -> String
*/
let a = "777";
let b = Number(a);
console.log(b); // 777/*
Stirng -> Int
*/
let a = 777;
let b = String(a);
console.log(b); // "777"Array.prototype.reduce()
: 배열의 모든 원소에 대해 특정한 연산을 순차적으로 적용할 때 reduce()를 사용
- reduce() 메서드: 배열의 각 요소에 대해 reducer 함수를 실행한 뒤에 하나의 결과를 반환
- reducer의 형태:
(accumulator, currentValue) ⇒ (반환값)- 배열의 각 원소를 하나씩 확인하며, 각 원소는 currentValue에 해당
- 반환값은 그 이후의 원소에 대하여 accumulator에 저장됨
ex)
let data=[5,2,9,8,4]
// minValue 구하기 예제
let minValue = data.reduce((a,b)=>Math.min(a,b));
console.log(minValue); // 2
// 원소의 합계 구하기 예제
let sum = data.reduce((a,b) => a+b);
console.log(sum); // 28배열 초기화 방법
- 직접 값을 설정하여 초기화
let arr = [8, 1, 4, 5, 7]- 길이가 5이고, 모든 원소의 값이 0인 배열 초기화
let arr = new Array(5).fill(0);집합 자료형
: 특정한 원소의 등장 여부를 파악할 때 집합 자료형을 효과적으로 사용 가능
❗️중복된 원소는 포함 안함
add(): 원소 삽입size: 원소 크기has(): 원소 포함 여부delete(): 원소 제거for (let i of 집합) console.log(i): 원소 하나씩 출력
let mySet = new Set(); // 집합 객체 생성
// 여러 개의 원소 삽입
mySet.add(3);
mySet.add(5);
console.log(`원소의 개수: ${mySet.size}`);
console.log(`원소 7을 포함하고 있는가? ${mySet.has(7)}`);
// 원소 5 제거
mySet.delete(5);
// 원소 하나씩 출력
for (let item of mySet) console.log(item);소수점 아래 특정 자리에서 반올림
- 특정 실수에 대해서
toFixed()를 이용해 원하는 소수점 까지 출력 가능
let x = 123.456;
console.log(x.toFixed(2)); // 소수점 아래 둘째 자리까지 출력Escape Sequence
- 예약 문자 혹은 특수 문자를 출력하기 위해 이스케이스 시퀀스 사용 가능
시퀀스 문자 \t 탭 \ 역 슬래시 \” 큰 따옴표 \’ 작은 따옴표
ex) console.log(”그는 \”비범함\”을 보였다.”);
