📝 오늘 한 것

1. 빅 오 표기법 / 버블 정렬 알고리즘 / 배열에 중복 값 있는지 확인하는 방법 / 선택 정렬 알고리즘 / 빅 오의 역할 / 같은 분류에 속하는 알고리즘의 효율성 비교

2. 알고리즘 코드 구현 (자바스크립트)

📖 학습 자료

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

📚 배운 것

[TIL] 211010 참고
새롭게 알게 된 내용들 위주로 정리함

3장. 빅 오 표기법

📌 경쟁 자료 구조와 알고리즘의 시간 복잡도를 표현하는 형식적인 방법

📌 빅오 표기법으로 실제 쓰이는 시나리오를 분석해서 경쟁 자료 구조와 알고리즘 중 최선을 고를 수 있다.

📌 빅 오 표기법은 일반적으로 '최악의 시나리오'를 의미한다.

💡 데이터가 증가할수록, 단계 수는 어떻게 변하는가?

1) O(1)

데이터가 증가해도 단계 수는 항상 일정

ex. 배열 읽기 / 배열 맨 끝 삽입, 삭제

2) O(N)

데이터가 증가한 만큼 단계 수가 증가

ex. 주어진 수가 소수인지 판별하는 알고리즘
cf. 소수 : 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수

p.69
Python로 구현된 코드 → JavaScript로 수정

function isPrimeNumber (num) {
  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false;
    }
    return true;
  }
}

console.log(isPrimeNumber(13)); // true

항상 자기 자신을, 2부터 시작해서 자기 자신 바로 이전 수까지로 나누는 과정을 거친다.
즉, 함수의 인자로 전달되는 숫자가 증가하면 그 증가분과 비례하여 단계 수도 증가하므로, 위 알고리즘의 시간 복잡도는 O(N)이다.

3) O(log N)

데이터가 2배씩 증가할 때마다 1단계 추가

4장. 빅 오로 코드 속도 올리기

📌 빅 오를 사용해 작성한 알고리즘의 효율성을 평가하고, 효율성을 높이기 위해 알고리즘을 수정하고자 함

1) 버블 정렬 알고리즘

💡 정렬 알고리즘 > 단순 정렬 알고리즘 > 버블 정렬

정렬 알고리즘은 모두 다음의 문제를 해결한다.
정렬되지 않은 배열이 주어졌을 때, 어떻게 오름차순으로 정렬할 수 있을까?

정렬 알고리즘 중에는 단순 정렬 알고리즘이 있다.
이는 이해하기 쉬워서 붙여진 이름일 뿐, 실제로는 이보다 효율적인 알고리즘이 존재한다.

단순 정렬 알고리즘에는 버블 정렬 / 선택 정렬 / 삽입 정렬 알고리즘이 있다.

(1) 설명

각 패스스루마다, 정렬되지 않은 값 중 가장 '큰 값'인 버블이, 올바른 위치로 가게 된다.

cf. 패스스루(passthrough)란?
한 개의 데이터를 제자리에 위치시키는 알고리즘의 주요 절차

처음 패스스루에서 교환을 적어도 한 번 수행했다면, 다음 패스스루를 수행해야 한다.

(2) 코드 구현

p.81
Python으로 구현된 코드 → JavaScript로 수정

function bubbleSort (arr) {
  // 어떤 인덱스까지 아직 정렬되지 않았는지
  let unsorted_until_index = arr.length - 1;
  // 배열의 정렬 여부
  let sorted = false;
  let swap;

  // 패스스루
  while (!sorted) {
    sorted = true;
    
    // 비교 & 교환
    for (let i = 0; i < unsorted_until_index; i++) {
      if (arr[i] > arr[i+1]) {
        swap = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = swap;
        sorted = false;
      }
    }

    unsorted_until_index = unsorted_until_index - 1;
  }

  return arr;
}


const arr1 = [4, 3, 2, 1]
console.log(bubbleSort(arr1)); // [1, 2, 3, 4]

처음 패스스루에서 교환을 적어도 한 번 수행했다면(sorted가 false가 됨), 다음 패스스루를 수행해야 한다.(sorted가 false이므로)

패스스루를 한 번 수행할 때마다, 정렬되지 않은 값 중 가장 큰 값이 올바른 위치에 정렬되므로, unsorted_until_index이 1씩 감소한다.

unsorted_until_index가 0이 되면, for 구문의 조건식(i < unsorted_until_index)을 만족하지 못해 for 구문을 실행할 수 없으므로 while 문을 종료하게 된다.

'처음부터 정렬되어 있는 배열'의 경우,
unsorted_until_index가 0이 아니므로 처음에 for 구문에 진입은 하지만,
if 구문의 조건식인 arr[i] > arr[i+1] 을 만족하지 못해 if 구문이 실행되지 않으므로 sorted = true인 채로 while 문을 종료하게 된다.

(3) 빅 오

버블 정렬 알고리즘에는 두 종류의 단계, 비교 & 교환이 포함되어 있다.

• 비교

  데이터가 N개일 때
  첫 번째 패스스루에서 N-1번 비교해야 하고
  두 번째 패스스루에서 N-2번 비교해야 하고
  세 번째 패스스루에서 N-3번 비교해야 하고
  ...
  마지막 패스스루에서 1번 비교해야 한다.

  위 예제의 경우, 데이터가 4개이므로 총 3+2+1 즉, 6번 비교를 해야 한다.

• 교환

  데이터가 N개일 때
  최악의 시나리오(배열이 내림차순으로 정렬되어 있는 경우)를 가정하면
  교환을 매 비교마다 해야 한다

  위 예제(최악의 시나리오)의 경우, 데이터가 4개이므로 비교한 횟수만큼 6번 교환을 해야 한다.

데이터가 4개일 때, 비교 & 교환의 최대 단계 수는 12개가 된다.

그런데, 데이터의 개수가 5, 10, 15, 20개...로 늘어나면, 최대 단계 수는 급격히 늘어난다. (데이터 개수, 최대 단계 수: 5개, 20개 / 10개, 90개 / 15개, 210개 / 20개, 380개)

정리하면, 데이터의 개수가 N개일 때, 대략 N^2 단계가 걸린다.
따라서 버블 정렬의 효율성은 O(N^2)라고 할 수 있다.
이는 좋은 알고리즘은 아니므로 수정할 수 있는지 고민해봐야 한다.

2) 배열에 중복 값이 있는지 확인하는 방법

(1) 중첩 루프(for 구문) 활용

• 코드 구현

  p.86

function hasDuplicateValue (arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (j !== i && arr[i] === arr[j]) {
        return true;
      }
    }
  }
  return false;
}

const arr1 = [5, 1, 1, 4];
console.log(isNested(arr1)); // true

• 효율성(빅 오)

빅 오(Big-O)는 데이터량에 비례해 알고리즘에 얼마나 많은 단계가 필요한지를 측정하는 도구이다.
따라서, 위 알고리즘의 효율성을 알아보기 위해 위 함수를 빅 오로 표현하려면 아래 질문에 답해야 한다.

위 함수의 인자로 데이터 N개를 포함하는 배열이 주어졌을 때, 최악의 시나리오에서 얼마나 많은 단계가 걸리는가?

위 함수에서 알고리즘에 포함된 단계의 유형은 비교이다.

최악의 시나리오는, 배열이 중복 값을 포함하지 않는 경우이다.
이 경우, i를 사용해 배열 내 원소를 모두 순회할 때마다 j를 사용해 배열 내 원소를 모두 순회해야 한다.
즉, 배열의 원소의 개수가 N개일 때, N^2(배열의 원소의 개수 x 배열의 원소의 개수) 단계가 걸린다.

→ 중첩 루프 알고리즘의 효율성 : O(N^2)

위 함수에 단계 수를 기록하는 코드를 추가하면 아래와 같다.

function hasDuplicateValue (arr) {
  let steps = 0;
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      steps++;
      if (j !== i && arr[i] === arr[j]) {
        return true;
      }
    }
  }
  console.log(steps);
  return false;
}

const arr1 = [5, 1, 2, 4];
console.log(hasDuplicateValue(arr1)); // 16 false

(2) 중첩 루프 활용 x

• 코드 구현

p.88

function hasDuplicateValue (arr) {
  const IndexIsNumberAlreadySeen = [];
  for (let i = 0; i < arr.length; i++) {
    if (IndexIsNumberAlreadySeen[arr[i]] === undefined) {
      IndexIsNumberAlreadySeen[arr[i]] = 1;
    } else {
      return true;
    }
  }
  return false;
}

const arr1 = [5, 9, 2, 9];
console.log(hasDuplicateValue(arr1)); // true;

• 효율성(빅 오)

마찬가지로 위 알고리즘의 효율성을 알아보려면
위 함수를 빅 오로 표현하기 위해
최악의 시나리오일 때 알고리즘에 필요한 단계 수를 알아내야 한다.

위 함수에서 알고리즘에 포함된 단계 중 주요 유형은 비교이다.
(이때 삽입은 중요치 않게 본다. 뒤에서 설명할 것.)

최악의 시나리오는, 배열이 중복 값을 포함하지 않는 경우이다.
이 경우, i를 사용해 배열 내 원소를 모두 순회해야 한다.
즉, 배열의 원소의 개수가 N개일 때, N단계가 걸린다.

→ 수정한 알고리즘의 효율성 : O(N)

위 함수에 단계 수를 기록하는 코드를 추가하면 아래와 같다.

function hasDuplicateValue (arr) {
  let steps = 0;
  const IndexIsNumberAlreadySeen = [];
  for (let i = 0; i < arr.length; i++) {
    steps++;
    if (IndexIsNumberAlreadySeen[arr[i]] === undefined) {
      IndexIsNumberAlreadySeen[arr[i]] = 1;
    } else {
      return true;
    }
  }
  console.log(steps);
  return false;
}

const arr1 = [5, 9, 2, 8];
console.log(hasDuplicateValue(arr1)); // 4 false

💡 (1)을 (2)로 수정함으로써 코드가 좀 더 효율적으로 작동하도록 최적화했다. O(N^2) → O(N)

5장. 빅 오를 사용하거나 사용하지 않는 코드 최적화

📌 빅 오 표기법으로는 두 알고리즘의 속도가 같은데, 실제로는 어느 한쪽이 더 빠른 경우가 있음

📌 이처럼 빅 오 표기법만으로 유의미한 차이를 발견할 수 없는 알고리즘들의 효율성을 평가하고자 함

1) 선택 정렬 알고리즘

💡 정렬 알고리즘 > 단순 정렬 알고리즘 > 선택 정렬

(1) 설명

각 패스스루마다, 정렬되지 않은 값 중 가장 '작은 값'이, 올바른 위치로 가게 된다.

(2) 코드 구현

p.100

• 내가 작성한 코드

  맞은 줄 알았는데 책을 확인하니 틀린 거 같다.

  내 코드는 arr[i]가 각 패스스루의 최솟값이라 for 루프의 if 구문이 실행되지 않음에도(→ 비교x) 쓸데없이 같은 자리(숫자)끼리의 교환은 일어난다.(→ 교환o)

  즉, arr[i]가 그 자체로 각 패스스루의 최솟값인 경우(최솟값이 이미 올바른 위치에 있는 경우)를 고려하지 않았다.

  🔥 추가!

  다만, 어차피 빅 오는 (상수 고려x / 가장 높은 차수만 고려o)이므로, 선택 정렬의 경우 최솟값을 고려하든 안 하든 빅 오로 표기되는 효율성에는 차이가 없다.

function selectionSort (arr) {
  // 패스스루
  for (let i = 0; i < arr.length - 1; i++) {

    let min = arr[i];
    let minIndex = i; // 각 패스스루 최솟값의 인덱스 minIndex

    // 비교
    for (let j = i + 1; j < arr.length; j++) {
      if (min > arr[j]) {
        min = arr[j];
        minIndex = j;
      }
    }

    // 교환
    arr[minIndex] = arr[i];
    arr[i] = min;
  }

  return arr;
}

const arr1 = [9, 2, 5, 1];
console.log(selectionSort(arr1)); // [1, 2, 5, 9]

• 책을 참고해 수정

  교환 부분에 if (minIndex !== i) 를 추가한 후 min 변수 이동

function selectionSort (arr) {
  // 패스스루
  for (let i = 0; i < arr.length - 1; i++) {
    let minIndex = i; // 각 패스스루 최솟값의 인덱스 minIndex

    // 비교
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[minIndex] > arr[j]) {
        minIndex = j;
      }
    }

    // 교환
    if (minIndex !== i) {
      let min = arr[minIndex];
      arr[minIndex] = arr[i];
      arr[i] = min;
    }
  }

  return arr;
}

const arr1 = [9, 2, 5, 1];
console.log(selectionSort(arr1)); // [1, 2, 5, 9]

(3) 빅 오

선택 정렬 알고리즘에는 두 종류의 단계, 비교 & 교환이 포함되어 있다.

• 비교

  데이터가 N개일 때
  첫 번째 패스스루에서 N-1번 비교해야 하고
  두 번째 패스스루에서 N-2번 비교해야 하고
  세 번째 패스스루에서 N-3번 비교해야 하고
  ...
  마지막 패스스루에서 1번 비교해야 한다.

• 교환

  각 패스스루마다 최대 1번의 교환이 일어난다.

  최솟값이 이미 올바른 위치에 있느냐에 따라 교환을 안 하거나 교환을 한 번 하기 때문이다.

  최악의 경우를 가정해도 데이터가 N개일 때, 교환은 N - 1번밖에 일어나지 않는다.

2) 빅 오의 역할

(1) 빅오 표기법은 상수를 무시한다

위에서 살펴봤듯이, 선택 정렬의 단계 수가, 버블 정렬의 단계 수보다 훨씬 적다. 자세히 따져보면, 대략 2배 정도 적다. 그러므로 선택 정렬이 버블 정렬보다 더 효과적임을 알 수 있다.

그러나, 선택 정렬과 버블 정렬을 빅 오로 표현하면, 둘 다 O(N^2)이다.
선택 정렬의 시간 복잡도는 O(N^2 / 2)로 표현해야 맞을 것 같지만, 그렇지 않다.
빅오 표기법은 상수를 무시하기 때문이다.

마찬가지로, 실제로는 O(N)보다 100배 느린 O(100N)이라 해도, 빅 오 표기법으로는 똑같이 O(N)이다.

그렇다면 빅오 표기법은 엉터리인 것인가?

(2) 빅 오의 역할

그렇지 않다.
빅 오 표기법은 '다른' 분류에 속하는 알고리즘의 효율성을 비교할 때 매우 유용하다.

예를 들어, O(100N)과 O(N^2)을 비교하면
특정 시점 이전까지는 O(100N)이 O(N^2)보다 느리지만,
특정 시점 이후부터는 계속해서 O(100N)이 O(N^2)보다 빠르다.

따라서, O(100N)이 O(N)으로 표시된다 하더라도
데이터가 많을 때 O(N)은 O(N^2)보다 항상 빠르다고 할 수 있다.

그러나, 선택 정렬과 버블 정렬의 경우처럼 '같은' 분류에 속하는 알고리즘의 효율성을 비교하기 위해서는 위에서처럼 더 자세히 분석해야 한다.

💡 '같은' 분류에 속하는 알고리즘의 효율성 비교

ex. 두 원소마다 하나 걸러 하나를 뽑아 새 배열 생성
해당 알고리즘에는 두 종류의 단계, 룩업(lookup) & 삽입이 포함되어 있다.

p.108
Ruby로 구현한 코드 → JavaScript로 수정

• 첫 번째 방법

  데이터가 N개일 때, N번의 룩업과 N/2번의 삽입 → O(1.5N)
  빅오 표기법으로 표현할 땐, O(N)

function makeNewArray (arr) {
  const newArray = [];
  for (let index in arr) {
    // 룩업(lookup)
    if (index % 2 === 0) {
      newArray[index/2] = arr[index]; // 삽입
    }
  }
  return newArray;
}

const arr1 = [5, 3, 7, 4, 6];
console.log(makeNewArray(arr1)); // [5, 7, 6]

• 두 번째 방법

  데이터가 N개일 때, N/2번의 룩업과 N/2번의 삽입 → O(N)
  첫 번째 방법보다 빠르다

function makeNewArray (arr) {
  const newArray = [];
  let index = 0;

  for (let i = 0; i < arr.length / 2; i++) {
    newArray[i] = arr[index]; // 룩업 & 삽입
    index += 2;
  }

  return newArray;
}

const arr1 = [5, 3, 7, 4, 6];
console.log(makeNewArray(arr1)); // [5, 7, 6]

✨ 내일 할 것

1. 책 계속 읽기