Javascript 알고리즘: 재귀, 집합, 검색과 정렬
글 작성자: SoniaComp
공부한 기록을 공유하기 위한 글입니다. 수정할 내용이 있다면 알려주세요!
Table of the Contents
1. 재귀: 분할정복, 종료조건
2. 집합: O(1)
집합속성, 집합연산과 유틸리티 함수
3. 검색과 정렬
3.1~3.2 선형검색, 이진검색
3.3~3.9 일곱가지 정렬 알고리즘
3.10 자바스크립트 내장 정렬함수 sort( )
1. 재귀
주의할 점: 무한 재귀 호출로 인해 콜 스택 메모리를 초과한 StackOverflow
알고리즘: ‘분할 정복’에 의해 점점 작아지면서 ‘종료 조건'에 도달
시간복잡도: 종료조건과 점화식의 시간복잡도 체크
공간복잡도: 콜 스택 메모리
2. 집합: Set 객체
집합: 정렬되지 않은, 중복되지 않은 항목 들의 그룹이다.
접근, 삽입, 삭제의 시간 복잡도: O(1)
(집합의 구현이 해시 테이블의 구현을 기초로 하기 때문에 가능)
(배열의 O(n) 시간 복잡도와 비교할 때, 빠름!)
2.1 집합속성
size
2.2 집합 연산
삽입: add( ) 중복되는 항목은 허용되지 않음. O(1)
삭제: delete( value ) true, false return. O(1)
포함: has( value ) true, false return. O(1)
2.3 기타 유틸리티 함수
// 1. 교집합: 공통 항목들로 구성
function intersectSects (setA, setB) {
var intersection = new Set( );
for(var elem of sets) {
if(setA.has(elem) {
intersection.add(elem);
}
}
return intersection;
}// 2. 상위집합 여부 확인: 다른 집합의 모든 항목들을 포함하는 경우
function isSuperset(setA, subset) {
for(var elem of subset) {
if(!setA.has(elem)) {
return false;
}
}
return true;
}// 3. 합집합: 양쪽 집합의 항목들을 합침
function unionSet(setA, setB) {
var union = new Set(setA);
for(var elem of setB) {
union.add(elem);
}
return union;
}// 4. 차집합: A에는 있지만 B에는 없는 항목들
function differenceSet(setA, setB) {
var difference = new Set(setA);
for(var elem of setB) {
difference.delete(elem);
}
return difference;
}
3. 검색과 정렬
🐥 병아리 개발자 SoniaComp의 붙임말
사용자가 원하는 데이터를 빠르고 신속하게 주는 것은 중요하다. 나는 어젯밤 마켓컬리에서 아몬드 우유🍶를 검색했고, 오늘 아침 네이버 쇼핑에서도 새롭게 업데이트 된 옷👗들을 보았다. 이제 직접 그 알고리즘을 구현해보자! 👊
검색: 자료를 얻기 위해 자료 구조의 항목들을 반복적으로 접근하는 것
선형 검색: 정렬된 자료, 정렬되지 않은 자료 O(n)
이진 검색: 정렬된 자료
정렬: 자료구조의 항목들을 순서대로 위치시키는 것.
좋은 정렬은 검색을 효율적으로 하게 해준다.
3.1 선형 검색
배열의 각 항목을 한 인덱스 씩 순차적으로 접근하면서 동작
3.2 이진 검색
중간 값을 확인하며 검색
3.3 거품정렬
전체 배열을 반복하며 순회하며 앞 뒤 값을 비교, 더 큰 항목과 교환
(거품을 통해 가장 큰 값을 뒤로 보내기)
3.4 선택 정렬
전체 배열을 순회하며, 가장 작은 값을 가장 맨 앞과 교환
(최소값을 선택해서 가장 앞으로 보냄)
3.5 삽입 정렬
‘정렬되지 않은 항목’을 ‘정렬된 부분’에 삽입
3.6 빠른 정렬 O(log)
빠른 정렬 5분 동영상 설명 :
기준점을 정한 후, 기준점을 기준으로 smaller, bigger 정렬(분할정복)
스택 호출로 인해 비교적 큰 공간복잡도.
function quickSort(items) {
return quickSortHelper(items, 0, itmes.length-1;
}function quickSortHelper(items, left, right) {
var index;
if(items.length>1){ // left, right가 다를 때
index = partition(items, left, right);
if(left<index-1) {
quickSortHelper(items, left, index -1);
}
if(index<right) {
quickSortHelper(items, index, right);
// 최종 반환 할 때는 쪼개진 파티션들이 정렬 된 채로 반환된다.
}
}
return items;
}function partition(array, left, right) {
// 1. 가장 첫번째로 중간 값 구하기
var pivot = array[Math.floor((right+left)/2)];
while(left<=right) {
while(pivot>array[left]){ // 작은 건 왼쪽으로,
left++;
}
while(pivot<array[right]){ // 큰건 오른쪽으로
right--;
}
if(left<=right){ // left가 right보다 작은 경우
var temp = array[left];
array[left] = array[right];
left ++;
right --; // 둘의 값을 교환
}
}
return left;
}
3.7 빠른 선택
빠른 정렬과 비슷.
기준점을 기준으로 한쪽만을 재귀적으로 정렬. (이진 검색과 비슷)
3.8 병합 정렬 O(log)
병합정렬 5분 동영상 설명
하위 배열로 계속 나눈 후(분할 정복),
두 개 남아서 하나씩 비교할 때(종료 기준), 정렬하여 넣으며 병합 정렬
function merge(leftA, rightA){
var results = [ ] , leftIndex = 0, rightIndex = 0; while(leftIndex<leftA.length && rightIndex<rightA.length) {
if(leftA[leftIndex]<rightA[rightIndex]){
results.push(leftA[leftIndex++]);
} else{
results.push(rightA[rightIndex++]);
}
}
var leftRemains = leftA.slice(leftIndex),
rightRemains=rightA.slice(rightIndex)
return results.concat(leftRemains).concat(rightRemains);
}function mergeSort(array){
if(array.length<2){
return array;
}
var midpoint = Math.floor((array.length)/2),
leftArray = array.slice(0, midpoint),
rightArray = array.slice(midpoint)
return merge(mergeSort(leftArray), mergeSort(rightArray));
}
3.9 계수 정렬 O(k+n)
각 항목의 등장 횟수를 센 후, 새로운 배열을 사용한다.
3.10 자바스크립트 내장 정렬
sort( )
sort( 비교함수 )
var arr = [3,2,1,4,5];
function comparatorNum(a,b) { return a-b; }
arr.sort(); // arr: [1,2,3,4,5]
arr.sort(comparatorNum); // arr: [5,4,3,2,1]
