[Data Structure] 기초 상식 / 문자열 / 기초 수학

1. 자료구조 / 알고리즘이란 ? 

자료구조(Data Structure)란?

• 데이터를 효율적으로 사용할 수 있도록 정리하는 방법
• 종류
  • 선형 구조 (Array, Dynamic Array, Linked list, Queue, stack, Hash Table)
  • 비선형 구조 (Tree, Graph)

선형 구조 / 비선형 구조

알고리즘이란?

• 문제를 해결하기 위해 정해진 일련의 절차나 방법
• 알고리즘을 설계하다 : 문제 풀이 절차를 설계한다는 의미
• 알고리즘을 구현하다 : 프로그래밍 언어를 이용하여 문제 풀이 절차를 실제로 동작하는 코드로 작성한다는 의미

즉, 알고리즘 문제풀이는 해당 문제를 풀기 위해 적절한 자료구조를 선택하고 그 자료구조를 선택하고 그 자료구조를 이용해 적합한 알고리즘을 구현하는 것이다.

 

 

2. 시간 복잡도 / 공간 복잡도 / 빅오 표기법이란?

시간 복잡도와 공간 복잡도는 trade-off 관계이다. 이유는 실행시간을 줄이기 위해서는 메모리를 더 사용해야 하고, 메모리 사용량을 줄이기 위해서는 시간을 더 사용해야하기 때문이다. 코딩 테스트 및 알고리즘에서는 메모리를 사용해서 실행 시간을 줄이는게 중요하기 때문에 시간복잡도 계산 방법, 이에 맞는 자료구조/알고리즘 선택 방법을 잘 선택해야한다.

시간 복잡도

• 알고리즘의 시간 효율성을 의미
• 시간 복잡도가 가장 낮은 알고리즘을 선택하여 사용한다.
• 빅오 표기법을 통하여 시간 복잡도를 구할 수 있다.

공간 복잡도

• 알고리즘의 공간(메모리) 효율성을 의미

빅오 표기법(big-O notation)

• 알고리즘 효율성을 표기해주는 표기법이다. 즉, 빅오 표기법은 보통 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 주로 사용된다.
• 특징
  • 상수항을 무시한다.
  • 영향력 없는 항을 무시한다.

그림에 나와 있는 시간 복잡도의 성능을 비교하면 오른쪽에서 왼쪽으로 갈 수록 효율성이 떨어진다.

• 예제
  • O(1) : 상수 (스택에서 Push, Pop)
  • O(log n) : 이진 검색 (이진트리)
  • O(n) : 선형 (for문)
  • O(n log n) : 이진 검색 (퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap sort))
  • O(n^2) : Square (이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort) )
  • O(2**n) : 피보나치 수열

3. 문자열 관련 javascript 함수 정리

1. 문자열 인덱싱 / 슬라이싱

//문자열 인덱싱
let str = ‘Hello World’;

console.log( str[0] ); // ‘H’
console.log( str[6] ); // ‘W’
console.log( str[10] ); // ‘d'

//문자열 슬라이싱
let str = ‘Javascript’;

str.slice(0, 4); // ‘Java’
str.slice(4); // ‘script’
str.substring(0,4); // ‘Java’
str.substring(4); // ‘script’
console.log(str.slice(-5, -1)); // ‘crip’
console.log(str.slice(3, 1)); // ‘ ’
console.log(str.substring(3, 1)); // ‘av’

slice() 와 substring() 차이

- slice()와 substring()은 비슷한 기능이지만 시작 인덱스가 종료 인덱스보다 클 경우 처리 방식이 다름

- substring()은 시작 값이 종료 값보다 클 겯ㅇ우 두 인덱스를 바꿔 처리한다. - slice()는 공백을 출력한다.

2. 특정 문자가 있는지 확인

const str = 'HTML,CSS,JavaScript';

if ( str.includes('HTML') ) {
	console.log('exist Hello');
} else {
	console.log('not exist Hello');
}

3. 문자열이 같은지 비교

const str1 = 'apple';
const str2 = 'apple';
const str3 = 'banana';

console.log(str1 === str2); // true
console.log(str1 == str2); // true
console.log(str2 === str3); // false
console.log(str2 == str3); // false

4. 문자열 길이 반환

const str = ‘자바스크립트’;
console.log(str.length); // 6

5. 특정 문자의 인덱스 값 찾기

//indexOf() 함수
const str = 'HTML,CSS,Javascript';
console.log(str.indexOf(','); // 4

// indexOf('찾을 문자열', '시작 위치')
console.log(str.indexOf(',', 5)); // 8

// lastIndexOf 함수로 뒤에서부터 문자열 찾기
console.log(str.lastIndexOf(',')); // 8

//search() 함수
const str = 'HTML,CSS,JavaScript'
console.log(str.search('JavaScript')); // 9
console.log(str.search('Kotlin')); // -1

6. 문자열을 구분자 기준으로 나누고 합치기

//split('구분자 문자열')
const str = 'HTML,CSS,JavaScript';
const words1 = str.split(','); // ['HTML', 'CSS', 'Javascript']

//split('구분자 문자열', '최대 배열 크기')
const words2 = str.split(',', 2); // ['HTML', 'CSS']

7. 문자열 대소문자 변환

const str = 'HTML,CSS,Javascript';

console.log(str.toUpperCase()); //HTML,CSS,JAVASCRIPT
console.log(str.toLowerCase()); //html,css,javascript

8. 기존 값을 다른 값으로 치환

const str = "hello, sooyeon";

str = str.replace('sooyeon', 'javascript');
console.log(str); // hello, javascript

const str2 = 'hello, javascript javascript javascript';
str2 = str2.replace('javascript', 'sooyeon');
console.log(str2); // hello, sooyeon javascript javascript

9. 양쪽 끝에서 특정 문자 (혹은 공백 제거)

// 양쪽 끝에서 공백 제거
const str1 = ' 안녕하세요 ';
const trimmedStr1 = str.trim();
console.log(trimmedStr1); // '안녕하세요'

// 줄바꿈 문자가 삽입되어 있는 경우 but,문자열과 문자열 사이의 공백은 제거되지 않음
const str2 = '여러분 안녕하세요\n';
const trimmedStr2 = str2.trim();
console.log(trimmedStr2); // '여러분 안녕하세요'

10. 아스키코드로 변환 혹은 대소 비교

//문자.charCodeAr();
'h'.charCodeAt(); // 104
1.charCodeAt(); // 에러 발생!!!
'hello'.charCodeAt(); // 104 => 맨 앞에 있는 문자만 변환

//String.fromCharCode(number);
String.fromCharCode(104); // "h"
String.fromCharCode(72); // "H"
String.fromCharCode(49); // "1"
String.fromCharCode(32); // " "
String.fromCharCode(0x68); // "h"
String.fromCharCode(0x48); // "H"
String.fromCharCode(0x31); // "1"
String.fromCharCode(0x20); // " "