[TIL] 211021

Lee Syong·2021년 10월 21일
JavaScriptTIL알고리즘자료 구조
0

TIL

목록 보기
64/204
post-thumbnail

📝 오늘 한 것

  1. 프로그래머스 문제 풀이 - 하샤드 수 / x만큼 간격이 있는 n개의 숫자

  2. 전개 연산자 / function.prototype.apply() / 얕은 복사 VS 깊은 복사 / 전개 구문을 이용한 '다차원 배열' 복사 / Array.prototype.keys() / Object.keys()

  3. 퀵 정렬 VS 삽입 정렬 / 퀵 셀렉트


📖 학습 자료

  1. 책 '누구나 자료 구조와 알고리즘'

📚 배운 것

1. 프로그래머스 문제 풀이

1) Level 1 문제 풀이

(1) 하샤드 수

🔎 내가 작성한 풀이 1

  • 주어진 숫자 x를 배열로 만들어 풀었다
function solution(x) {
  const sum = (x + '').split('').map(s => parseInt(s)).reduce((prev, curr) => prev + curr, 0);

  if (x % sum === 0) {
    return true;
  } else {
    return false;
  }
}

🔎 내가 작성한 풀이 2

  • 가장 먼저 떠오르는 건 위 방법이었지만, 어제 배운 방법으로도 풀어봄

  • 주어진 숫자 x를 10으로 나누었을 때의 몫과 나머지 활용

function solution(x) {
  let quotient = x;
  let sum = 0;

  while (quotient > 0) {
    let remainder = quotient % 10;
    sum += remainder;
    quotient = Math.floor(quotient / 10);
  }

  if (x % sum === 0) {
    return true;
  } else {
    return false;
  }
}

🔎 다른 사람의 풀이

  • 마지막에 if else 문 대신 간결하게 return !(x % sum)이라고 쓸 수 있다.
function solution(x) {
  let quotient = x;
  let sum = 0;

  while (quotient > 0) {
    let remainder = quotient % 10;
    sum += remainder;
    quotient = Math.floor(quotient / 10);
  }

  return !(x % sum);
}

(2) x만큼 간격이 있는 n개의 숫자

🔎 내가 작성한 풀이

function solution(x, n) {
  var answer = [];

  for (let i = 1; i <= n; i++) {
    answer.push(x * i);
  }

  return answer;
}

🔎 다른 사람의 풀이 1

  • 길이가 n인 배열을 미리 만들어 배열의 각 요소를 x로 모두 채운 후에 map()을 이용해 배열의 각 요소를 변환해주었다

  • Array.fill() → 배열의 처음부터 끝까지 하나의 값으로 채운다

function solution(x, n) {
  return Array(n).fill(x).map((v, i) => (i + 1) * v)
}

🔎 다른 사람의 풀이 2

  • 전개 연산자와 Array.prototype.keys() 활용

  • map() 메서드에서 v는 Array 생성자에 의해 만들어진 배열의 인덱스 하나하나를 받는다

function solution(x, n) {
  return [...Array(n).keys()].map(v => (v + 1) * x);
}

🔥 전개 연산자 (spread 연산자, 전개 구문, ... 문법)

MDN 사이트 참고

1. 함수 호출에서의 전개

전개 구문을 이용해, '배열'의 요소 혹은 '문자열'의 각 문자를, 함수의 인수로 사용할 수 있다.
인수 목록의 어디서든 사용될 수 있고, 여러 번 사용될 수도 있다.

① apply() 대신 사용 가능

function func(a, b, c, d, e, f) {
  return a + b + c + d + e + f;
}

// 전개구문을 이용해 함수의 인자로 주어질 '배열'
const args = [1, 2];
const sum1 = func(0, ...args, 3, ...[4, 5]);
console.log(sum1); // 15 (0 + 1 + 2 + 3 + 4 + 5)

// 전개구문을 이용해 함수의 인자로 주어질 '문자열'
const string = 'eat';
const sum2 = func('I', ...string, ...'it');
console.log(sum2); // Ieatit (I + e + a + t + i + t)

💡 function.prototype.apply()

주어진 this 값([TIL] 211014 참고)과 '배열' 또는 '유사 배열 객체'로 제공되는 인자로 함수를 호출한다.

function func(a, b) {
  return a + b;
}

// apply()를 이용해 함수의 인자로 주어질 '배열'
const args = [1, 2];

const sum1 = func.apply(null, args);
console.log(sum1); // 3

const max = Math.max.apply(null, args);
console.log(max); // 2

// apply()를 이용해 함수의 인자로 주어질 '유사 배열'
const obj = { 'length': 2, '0': 'eat', '1': 'bananas' };

const sum2 = func.apply(null, obj);
console.log(sum2); // eatbananas

② new 연산자를 이용해 생성자 함수 호출 시 사용 가능 (이때, apply()는 사용 못함)

const dateFields = [2021, 9, 21];
const date= new Date(...dateFields);
console.log(date.toLocaleString()); // 2021. 10. 21. 오전 12:00:00

2. 배열 리터럴에서의 전개

배열 리터럴의 어디서든 사용될 수 있고, 여러 번 사용될 수도 있다.

① push(), splice(), concat() 대신 사용 가능

const students1 = ['Tom', 'Sam'];
const students2 = ['danny', 'sola'];
const total_students = ['Ellie', ...students1, ...students2, 'Max'];
console.log(total_students); // ['Ellie', 'Tom', 'Sam', 'danny', 'sola', 'Max']

② 배열 복사

1레벨에서만 깊은 복사가 일어난다
2레벨부터는 얕은 복사가 일어난다

const arr1 = [1, 2, 3];
const arr2 = [...arr1];
arr2.push(4);

console.log(arr1); // [1, 2, 3]
console.log(arr2); // [1, 2, 3, 4]

💡 얕은 복사 VS 깊은 복사

※ 들어가기에 앞서, '객체가 같다(===)는 것은 서로 같은 주소를 가짐'을 의미한다!

[ 얕은 복사 ]

  • 객체의 참조 값(주소)을 복사한다
  • 원본과 복사본은 서로 같은 주소를 가진다
  • 하나를 바꾸면 다른 하나도 영향을 받는다
/* 변수에 객체를 직접 할당해 복사 (참조에 의한 할당) */

const arr1 = [1, 2];
const arr2 = arr1;

console.log(arr1 === arr2); // true
// arr1과 arr2는 서로 같은 주소를 가진다. 즉, '얕은' 복사가 되었음을 알 수 있다.

// 확인 예제
arr2[0] = 3;
console.log(arr1[0]); // 3 → arr2을 바꿔도 arr1까지 영향을 받는다

[ 깊은 복사 ]

  • 객체의 값을 복사한다
  • 원본과 복사본은 서로 다른 주소를 가진다
  • 하나를 바꾸면 다른 하나는 영향을 받지 않는다
/* 전개 구문을 이용해 복사 */

const arr1 = [1, 2, 3];
const arr2 = [...arr1];

console.log(arr1 === arr2); // false
// arr1과 arr2는 서로 다른 주소를 가진다. 그렇다면 '깊은' 복사가 된 것일까 ❓

// 확인 예제
arr2.push(4);
console.log(arr1); // [1, 2, 3]
console.log(arr2); // [1, 2, 3, 4] → arr2를 바꾸니까 arr2만 영향을 받는다

// 얼핏 보면, 전개구문을 통해 깊은 복사가 완벽히 가능한 것처럼 보인다.
// 그러나, 이는 1레벨 깊이에서만 효과적으로 동작할 뿐이다 ❗
// 전개구문을 이용해 '다차원 배열'의 깊은 복사는 할 수 없다 ❗

💡 전개 구문을 이용해 '다차원 배열' 복사

결과적으로 1레벨에서만 깊은 복사 가능
2레벨부터는 얕은 복사일 뿐

[ 1레벨에서만 깊은 복사 ]

  • 확인 예제 1
const arr3 = [[1], [2], [3]];
const arr4 = [...arr3];

console.log(arr3 === arr4); // false
// arr3와 arr4는 여전히 다른 주소를 가진다 (즉, 1레벨에서는 깊은 복사가 일어남)

arr4.shift();
console.log(arr3); // [[1], [2], [3]]
console.log(arr4); // [[2], [3]] → arr4를 바꾸면 arr4만 영향을 받는다
  • 확인 예제 2
const arr3 = [[1], [2], [3]];
const arr4 = [...arr3];

console.log(arr3 === arr4); // false
// arr3와 arr4는 여전히 다른 주소를 가진다 (즉, 1레벨에서는 깊은 복사가 일어남)

arr4[0] = 'coke';
console.log(arr3); // [[1], [2], [3]]
console.log(arr4); // ['coke', [2], [3]] → arr4를 바꾸면 arr4만 영향을 받는다

[ 2레벨부터는 얕은 복사 ]

  • 확인 예제 1
const arr3 = [[1], [2], [3]];
const arr4 = [...arr3];

console.log(arr3 === arr4); // false
// arr3와 arr4는 여전히 다른 주소를 가진다 (즉, 1레벨에서는 깊은 복사가 일어남)
// 그러나, 아래 예제를 통해 2레벨부터는 깊은 복사가 되지 않았음을 알 수 있다 ❗

arr4.shift().shift();
console.log(arr3); // [[], [2], [3]] → arr4를 바꿔도 arr3까지 영향을 받는다
console.log(arr4); // [[2], [3]]
  • 확인 예제 2
const arr3 = [[1], [2], [3]];
const arr4 = [...arr3];

console.log(arr3 === arr4); // false
// arr3와 arr4는 여전히 다른 주소를 가진다 (즉, 1레벨에서는 깊은 복사가 일어남)
// 그러나, 아래 예제를 통해 2레벨부터는 깊은 복사가 되지 않았음을 알 수 있다 ❗

arr4[0][0] = 'coke';
console.log(arr3); // [['coke'], [2], [3]] → arr4를 바꿔도 arr3까지 영향을 받는다
console.log(arr4); // [['coke'], [2], [3]]

3. 객체 리터럴에서의 전개

객체 리터럴에 추가하여 얕은 복제와 객체 병합을 간결하게 할 수 있다

const obj1 = { name: 'jimmy', age: 12 };
const obj2 = { name: 'peter', hobby: 'swimming' };

// 얕은 복제
const cloneObj = { ...obj1 };
console.log(cloneObj); // { name: 'jimmy', age: 12 }

// 객체 병합
const mergeObj = { ...obj1, ...obj2 };
console.log(mergeObj); // { name: 'peter', age: 12, hobby: 'swimming' };

🔥 Array.prototype.keys()

배열의 각 인덱스를 값으로 가지는, 새로운 Array Iterator 객체를 반환한다.
따라서, 반환 값에 for of 문을 돌려 그 값을 출력하면, 배열의 각 인덱스가 차례대로 출력된다.

cf. 반복자(iterator)란? 객체 지향적 프로그래밍에서, 배열이나 그와 유사한 자료 구조의, 내부 요소를 순회하는 객체이다.

const arr1 = ['a', 'b', 'c'];
const iterator1 = arr1.keys();
for (let key of iterator1) {
  console.log(key);
}
// 0
// 1
// 2

💡 Object.keys(객체)와 비교할 것 !

주어진 객체의 열거할 수 있는 모든 속성 이름들을 '배열'로 반환한다.

const obj1 = { name: 'syong', age: 1, hobby: 'eating'}
const keys = Object.keys(obj1);
console.log(keys); // ['name', 'age', 'hobby']

const arr1 = ['a', 'b', 'c'];
const iterator2 = Object.keys(arr1);
console.log(iterator2); // ['0', '1', '2']

10장. 속도를 높이는 재귀 알고리즘

2) 퀵 정렬 알고리즘

어제 공부에 이어서

(4) 시나리오

🔎 최선의 시나리오

  • 분할 후 피벗이, 하위 배열의 한가운데 있을 때
    (배열이 이미 정렬되어 있을 때 x)

🔎 최악의 시나리오

  • 피벗이 항상, 하위 배열의 한가운데가 아닌, 한쪽 끝에 있을 때
  • 완전히 오름차순 또는 내림차순일 때를 포함해 몇몇 상황에서 일어난다

[예제]

완전히 오름차순로 정렬되어 있으면서, 피벗이 왼쪽 끝에 있는 경우

( ※ 분할 = 비교 & 교환 )

데이터의 개수가 N개일 때, 각 분할마다, 교환은 1번밖에 일어나지 않지만(왼쪽 포인터가 가리키는 숫자가 피벗이므로 스스로 교환), 비교가 N번씩 일어난다.

예를 들어, 데이터의 개수가 8개일 때, 각 분할마다 교환은 1번밖에 일어나지 않지만(빅 오는 가장 높은 차수만 고려하므로 교환 횟수는 무시한다), 비교는 기저 조건에 도달할 때까지(즉, 하위 배열이 0 또는 1개가 될 때까지) 모든 분할을 거쳐 총 8+7+6+5+4+3+2번(35번) 일어난다. 이를 공식으로 표현하면, N² / 2번이다.

따라서, 최악의 시나리오의 경우, 데이터의 개수가 N개일 때, 퀵 정렬 알고리즘의 효율성은 O(N²)이 된다. (빅 오는 상수를 무시하므로)

피벗이 항상 한쪽 끝에 있으면, 한번 분할할 때마다 비교해야 하는 하위 배열의 원소 수가 많으므로 효율성이 낮아진다. 반면에, 피벗이 중간에 있으면, 한번 분할할 때마다 비교해야 하는 하위 배열의 원소 수가 적으므로 효율성이 높아진다.

(5) 퀵 정렬 VS 삽입 정렬

최선의 시나리오일 때

  • 퀵 정렬의 효율성 : O(N logN)
  • 삽입 정렬의 효율성 : O(N)

평균 시나리오일 때

  • 퀵 정렬의 효율성 : O(N logN)
  • 삽입 정렬의 효율성 : O(N²)

최악의 시나리오일 때

  • 퀵 정렬의 효율성 : O(N²)
  • 삽입 정렬의 효율성 : O(N²)

정리하면, 두 정렬의 효율성은 최악의 시나리오에서는 동일하고, 최선의 시나리오에서는 삽입 정렬이 퀵 정렬보다 빠르다.

그러나, 퀵 정렬이 삽입 정렬보다 우수한 이유는, 대부분의 경우 일어나는 평균 시나리오에서 퀵 정렬이 훨씬 빠르기 때문이다.

3) 퀵 셀렉트

(1) 설명

  • 무작위로 정렬된 배열에서 몇 번째로 작거나 큰 값을 알고 싶다고 하자.

  • 이때 퀵 정렬을 이용해 전체 배열을 정렬한다면 값을 쉽게 찾을 수 있다.

  • 그러나, 퀵 셀렉트를 이용하면, 전체 배열을 정렬할 필요 없이, 퀵 정렬을 이용할 때보다 더 나은 성능을 낼 수 있다.

  • 퀵 셀렉트도 퀵 정렬처럼 분할에 기반하며, 퀵 정렬과 이진 검색을 조합한 알고리즘이라고 할 수 있다.

  • 퀵 셀렉트는 분할이 끝나면, 피벗 값이 배열 내 올바른 위치에 있게 되는 점을 활용한다.

(2) 코드 구현

[예제]

길이가 8인 배열에서 2번째로 작은 값을 찾고자 한다

  • 먼저, 전체 배열을 분할한다.

  • 분할 후 피벗은 올바른 위치에 있게 된다. 임의로 배열의 5번째 셀에 위치해 있다고 치자. 이제 배열 내에서 5번째로 작은 값을 알게 되었다.

  • 2번째로 작은 값을 찾고 있으므로 피벗을 기준으로 왼쪽 하위 배열만 살펴본다. (이후로도 배열을 계속 반으로 나누되, 찾고 있는 값이 있을 반쪽에만 집중한다.)

  • 다음으로, 피벗의 왼쪽 하위 배열을 분할한다.

  • 분할 후 피벗은 올바른 위치에 있게 된다. 임의로 배열의 3번째 셀에 위치해 있다고 치자. 이제 배열 내에서 3번째로 작은 값도 알게 되었다.

  • 2번째로 작은 값을 찾고 있으므로 피벗을 기준으로 왼쪽 하위 배열만 살펴본다.

  • 계속해서, 피벗의 왼쪽 하위 배열을 분할한다.

  • 분할이 끝나면, 가장 작은 값과 2번째로 작은 값이 배열 내에서 올바른 위치에 있게 된다. 이제 배열 내에서 2번째로 작은 값을 가져올 수 있게 되었다.

[코드 구현]

p.212
Ruby로 구현된 코드 → 자바스크립트로 변환
'퀵 셀렉트 메서드'만 새로 추가함

🙋‍♀️ Q1. quickSelect 메서드 안의 if else 문에서 모든 경우에 전부 return을 써줘야만 최종 return 값이 제대로 나온다. 다시 말해, this.quickSelect 앞에 return을 안 써주면 최종 return 값은 계속 undefined라고 뜬다. 근데 여기에 return을 왜 써줘야 하는 건지 이해가 안 간다. 루비로 구현되어 있는 책에도 이 부분에 return은 안 쓰여 있다.
→ 이진 트리 구현해보다가 이해됐다. 함수의 호출 순서를 기억하는 호출 스택을 그림으로 그려서 살펴보면 이해가 된다. return을 써주지 않으면, if 구문들 본문의 마지막에 생략되어 있는 return undefined에 의해 undefined가 반환된다.

class SortableArray {
  constructor(arr) {
    this.arr = arr;
  }

  // 퀵 셀렉트 메서드 추가 ❗
  quickSelect(indexOfValueToFind, left_index, right_index) {
    if (left_index >= right_index) {
      return this.arr[left_index];
    }

    const pivot_position = this.partition(left_index, right_index);

    if (indexOfValueToFind < pivot_position) {
      return this.quickSelect(indexOfValueToFind, left_index, pivot_position - 1);
    } else if (indexOfValueToFind > pivot_position) {
      return this.quickSelect(indexOfValueToFind, pivot_position + 1, right_index);
    } else {
      return this.arr[pivot_position];
    }
  }

  // 퀵 정렬 메서드
  quickSort(left_index, right_index) {
    if (left_index >= right_index) {
      return;
    }

    const pivot_position = this.partition(left_index, right_index);

    this.quickSort(left_index, pivot_position - 1);
    this.quickSort(pivot_position + 1, right_index);
  }

  // 분할 메서드
  partition(left_pointer, right_pointer) {
    const pivot = this.arr[right_pointer];
    const pivot_position = right_pointer;

    right_pointer = right_pointer - 1;

    while (true) {
      while (this.arr[left_pointer] < pivot) {
        left_pointer += 1;
      }
      while (left_pointer < right_pointer && this.arr[right_pointer] > pivot) {
        right_pointer -= 1;
      }

      if (left_pointer >= right_pointer) {
        break;
      } else {
        this.swap(left_pointer, right_pointer);
        left_pointer += 1;
      }
    }

    this.swap(left_pointer, pivot_position);

    return left_pointer;
  }

  // 배열 요소 교환 메서드
  swap(pointer_1, pointer_2) {
    const temp = this.arr[pointer_1];
    this.arr[pointer_1] = this.arr[pointer_2];
    this.arr[pointer_2] = temp;
  }
}


const arr1 = [0, 5, 2, 1, 6];
const arr = new SortableArray(arr1);

// 퀵 셀렉트 실행 ❗
const forthLowestValue = arr.quickSelect(3, 0, arr1.length - 1);
console.log(forthLowestValue); // 5

(3) 빅 오

'퀵 정렬'은 배열을 반으로 나눌 때마다 원래 배열의 모든 셀을 다시 분할해야 하므로 O(N logN)이 걸린다. 반면에, '퀵 셀렉트'는 배열을 반으로 나눌 때마다 찾고 있는 값이 있을 반쪽만 분할하면 된다.

'평균 시나리오'에서, 퀵 정렬의 효율성은 O(N logN)인 반면, 퀵 셀렉트의 효율성은 O(N)(실제로 2N이지만 상수 무시)이다. 따라서, 퀵 셀렉트가 퀵 정렬보다 성능이 더 좋다고 할 수 있다.


🙋‍♀️ 질문

  1. 여기 바로가기 → 이해했다(211024)

✨ 내일 할 것

  1. 프로그래머스 문제 풀이

  2. 책 이어서 읽기

profile
Lee Syong
능동적으로 살자, 행복하게😁
이전 포스트

[TIL] 211020

다음 포스트

[TIL] 211022

0개의 댓글