이론/알고리즘

[정렬] Insertion Sort - JS, Python

삽입정렬 알고리즘 삽입 정렬은 왼쪽에서 오른쪽으로 가면서 요소들을 왼쪽 요소들과 비교하여 알맞은 자리에 삽입하는 형식의 정렬 방법 주의 첫번째 값은 고정되어있음 1. 첫번째 값을 고정시킨 채 오른쪽 값과 첫번째 값을 비교한다 2. 왼쪽 값이 오른쪽 값보다 크면 오른쪽 값을 왼쪽으로 삽입한다 (반복) 3. 만약 왼쪽값이 오른쪽 값보다 작은 경우 삽입을 멈춘 뒤 값을 고정시킨다 삽입정렬은 항상 왼쪽 비교 대상 데이터들이 정렬되어 있다는 가정하에 진행된다 Big O 삽입 정렬 시간 복잡도는 O(N^2)이며, 선택정렬과 마찬가지로 반복문이 두 번 중첩되어 사용됨 삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태면 매우 빠르게 동작 WORST O(N^2) - 값을 전부 비교하며 교환해야 하는 경우 BE..

[정렬] Selection Sort - JS, Python

선택정렬 알고리즘 1. 먼저 주어진 리스트 중에 최소값찾기 2. 그 값(최소값)을 맨 앞에 위치한 값과 교환 3. 맨 앞을 고정하고 다시 순회하며 최소값 찾기 4. 그 값을 고정 값 바로 다음 위치와 교체...반복 선택정렬은 n번째 회전이 끝날 때마다 앞에서 n번째 데이터의 위치가 고정된다 교환 횟수를 최소화하는 반면 각 자료 비교하는 횟수 증가 Big O * 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내줘야 함 * 구현 방식에 따라 사소한 오차는 있을 수 있지만 전체 연산횟수는 아래와 같음 N + (N - 1) + (N - 2) + ... + 2 * 이는 (N^2 + N - 2) / 2 로 표현할 수 있는데 빅오 표기법에 따라서 O(N^2)이라 작성 WORST O(n^2) - 정렬이 하..

[JavaScript] 알고리즘에 쓰이는 문법 (판별)

판별 match() 인자에 포함된 문자를 찾으면 이를 반환(Array로) 일치하는게 없으면 null반환 1. 일반 문자열 if (str.match('red') === 'red') { console.log('Okay'); } 2. 정규표현식 let new_id = 'hello' new_id.match(/^[a-z]$/) //['hello'] var test = 'love you. love me. love everything!' var regExp = /love/gi; test2 = test.match(regExp); ['love', 'love', 'love'] // test2변수에 배열로 모든 love 텍스트가 저장됨 var str = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijkl..

[JavaScript] 알고리즘에 쓰이는 문법 (중복, 포함여부)

중복제거 Set < indexOf < includes순으로 시간 오래걸림 indexOf() 배열에서 지정된 요소 찾을 수 있는 첫번째 인덱스를 반환 존재하지 않으면 -1 if(answer.indexOf(numbers[i]+numbers[j])===-1){ answer.push(numbers[i]+numbers[j]) } Set() 자료형에 관계 없이 원시 값과 객체 참조 모두 유일한 값을 저장할 수 있음 const temp = [] for (let i = 0; i < numbers.length; i++) { for (let j = i + 1; j < numbers.length; j++) { temp.push(numbers[i] + numbers[j]) } } const answer = [...new Se..

[JavaScript] 알고리즘에 쓰이는 문법(누적합, 정렬)

누적합 reduce 누적할때 사용 acc가 합의 결과, 0으로 초기화, cur이 a 순서대로, idx가 index function solution(a, b) { var answer = a.reduce((acc, cur, idx) => acc += cur*b[idx], 0) return answer } 정렬 sort() 정렬하기 : array, object일때 사용가능 기본개념 sort(a, b)에서 a는 다음 인자, b는 현재 idx인자를 뜻함 sort([compareFunction])에서 [compareFunction] 이 어떤 값을 반환하는지가 중요 0보다 크다 0이다 0보다 작다 ⇒ 이 경우에만 앞 뒤 순서가 바뀜 answer.sort((next, prev) ⇒ (next > prev) - (nex..

[JavaScript] 알고리즘에 쓰이는 문법 (배열초기화)

new Array 초기화 할 값의 길이를 정할 수 있음 prices = [1,2,3,4,5] answer = new Array(prices.length) >>[ ] Array.from 초기화할 범위와 값을 정할 수 있다 const arr = Array.from({length: 5}, (v, i) => i); // i(index) 1씩 증가 console.log(arr); // => Array(5) [0, 1, 2, 3, 4] console.log(arr[0]); // => 0 console.log(arr.length); // => 5 /* 콜백함수의 첫번째 매개변수, v 생략시 undefined 반환 */ const arr = Array.from({length: 5}, (i) => i); console...