분류 전체보기

[정렬] Quick Sort - JS, Python

퀵 정렬 알고리즘 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터 위치 바꾸는 방법 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 됨 가장 기본적인 퀵정렬은 첫번째 데이터를 기준 데이터(pivot)으로 설정 Divide and Conquer전략 사용 1. pivot 데이터 설정 (맨 앞) 2. pivot의 다음 값을 left로, 배열 맨 끝을 right로 설정 3. left값이 pivot보다 크고 right값이 pivot보다 작을 때까지 동작 (left는 idx+1, right는 idx-1) 4. right의 idx가 left의 idx보다 클 경우 right값과 left값을 교환해줌 5. right의 idx가 lef..

[정렬] 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..