71일차 CS50 [알고리즘2]

2021. 01. 14 금요일

여기에서 무료로 CS 강의를 들을 수 있고, 여기서 들은 것을 바탕으로 정리해보고자 한다.

CS50 강의 4일차이다. 어제에 이어서 알고리즘 파트를 마무리 했다. 전체 정리 본

오늘은 삽입 정렬, 시간 복잡도, 합병 정렬, 이진 탐색 강의를 들었다. 아래는 강의 자료를 기반으로 다시 정리해본 것이다.

생각해보기 부분은 나의 생각이므로 정답이라고 할 수는 없다.

---

5. 삽입 정렬

삽입 정렬이란?

정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법이다. 따라서 자료를 여러 번 비교하거나 교환할 필요가 없다.

실행

삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분, 두 개의 부분으로 나누면서 동작한다. [5, 1, 6, 2, 4, 3]이라는 배열을 삽입정렬해주어야 한다면 다음과 같이 수도코드를 작성할 수 있다.

1. 첫 번째 자리(5)는 이미 정렬된 부분이라고 간주한다.
2. 정렬되지 않은 부분의 맨 앞자리인 1은 5보다 작기 때문에 5는 오른쪽으로 이동하고 1이 첫 번째 자리로 온다.
3. 다음으로 정렬되지 않은 부분의 6을 살펴본다.
4. 6은 5보다 크기 때문에 이동할 필요가 없다.
5. 같은 방식으로 계속 실행하면 모두 정렬된다.

삽입 정렬을 직접 작성해보았다.

const insertionSort = function (arr) {
  let sorted = [arr[0]];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] >= sorted[i - 1]) {
      sorted.push(arr[i]);
    } else {
      for (let j = 0; j < i; j++) {
        if (arr[i] <= sorted[j]) {
          const left = sorted.slice(0, j);
          const right = sorted.slice(j);
          sorted = left.concat(arr[i], right);
          break;
        }
      }
    }
  }
  return sorted;
};

삽입 정렬은 자료의 양이 적을 때 성능이 우수하며 자료 대부분이 이미 정렬 되어있는 경우 효율적이다. 삽입 정렬은 이미 정렬된 자료에 새로운 자료를 삽입해야 하는 경우가 발생하면, 정렬된 자료들이 자리를 이동해야 하므로 안정성이 낮다.

생각해보기

Q1. 삽입 정렬이 다른 정렬에 비해 갖는 장점과 단점을 무엇인가?
A1. 비교와 교환횟수가 적은것이 장점이고, 지정된 위치 변화가 잦을 가능성이 크므로 안정성은 낮은편인 것이 단점이다.

Q2. 삽입 정렬이 버블 정렬, 선택 정렬보다 선호되는 경우는 언제인가?
A2. 우선 데이터의 양이 적을 경우 버블 정렬이 선택 정렬보다 효율적일 수 있고, 여기에 어느 정도 정렬이 되어있다고 가정하면 삽입 정렬이 더 효율적일 것이다. 그리고 데이터의 양이 많은 경우 버블 정렬보다 선택 정렬이 효율적일 것이고, 여기에 어느 정도 정렬이 되어있다면 삽입 정렬이 더 효율적일 것이다. 데이터의 양이 적고, 어느 정도 정렬이 되어있다는 두 조건을 만족하는 경우라면 삽입 정렬 알고리즘을 선택하면 될 것이다.

---

6. 시간 복잡도

시간 복잡도란?

알고리즘을 수행할 때 걸리는 시간을 기준으로 효율성을 분석하는 것이다. 시간 복잡도가 낮을수록, 연산자의 사용 횟수가 적을수록 효율성이 높은 알고리즘이 된다.

Big-O 표기법

컴퓨터 과학에서 “대략”을 나타내는 공식적인 개념으로 시간 복잡도를 나타내는 표현. 최악의 경우를 나타냄.

• 선형 탐색 : O(n)
• 버블 정렬 : O($n^2$). n개의 자료를 갖는 배열은 n-1쌍을 비교한다. 전체 비교 횟수를 식으로 나타내면 $n^2/2 - n/2$ 이고 가장 중요한 부분은 $n^2/2$ 가 되고 계수를 제외하면 $n^2$ 이 남고 O($n^2$) 으로 표현한다.
• 선택 정렬 : O($n^2$). n개의 자료가 있다면 첫 번째 자료와 나머지 n-1개의 자료 중 가장 작은 값의 자리를 교환해 주어야 한다. 즉, 비교 횟수는 버블 정렬과 마찬가지가 되고, 시간복잡도는 O($n^2$) 으로 표현한다.
• 삽입 정렬 : O($n^2$). n개의 자료가 있다면 첫 번째 자료는 정렬이 되었다고 생각하고, n-1개의 자료 중 첫 번째 자료와 정렬된 자료를 비교한다. 따라서 마찬가지로 시간복잡도는 O($n^2$) 으로 표현한다.

Big 𝛺 표기법

Big-O와 비슷한 표기법인데, Big 𝛺는 최선의 경우를 나타낸다.

• 선형 탐색 : 선형 탐색의 최선의 경우는 찾고자 하는 값을 바로 찾는 상황이다. 𝛺(1)로 나타낸다.
• 버블 정렬 : 최선의 경우를 생각해보면 버블 정렬은 교환이 이루어지지 않더라도 배열이 정렬된 사시을 모르기 때문에 여전이 n-1번의 비교를 해줘야 한다. 따라서 𝛺(n)로 표기한다.
• 선택 정렬 : 배열이 정렬되었다는 것을 알 수 없어 최소값을 계속 찾아주어야 하므로 𝛺($n^2$)로 표기한다.
• 삽입 정렬 : 정렬되지 않은 부분에서 정렬된 부분으로 옮겨갈 때, 정렬된 부분의 가장 큰 수와 비교하기만 하면 되기 따문에 𝛺(n)로 표기한다.

---

7. 합병 정렬

합병 정렬이란?

원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다. 그리고 이 과정은 재귀적으로 구현된다.

실행

[3, 5, 2, 6, 4, 1]이라는 배열을 가지고 합병정렬을 한다면 다음과 같이 수도코드를 작성할 수 있다.

1. 배열은 반으로 나뉘고, 원소가 1개가 될 때까지 계속해서 나누어지게 된다.
2. 모든 원소가 1개가 되었을 때, 다시 합치면서 정렬이 이루어지게 된다.
3. step 4에서 5로 넘어가면서 3과 5의 크기를 비교하고 정렬된 채로 넘어가는 것처럼 나머지 나누어진 부분도 같은 방식으로 병합된다.

이렇게 나누어지고 합쳐지는 중간 단계의 배열을 임시로 저장하고 함수가 종료될 때까지 기억하고 있어야 하기 때문에, 메모리의 필요한 공간이 늘어난다.

합병 정렬을 직접 코드로 작성해 보았다.

const mergeSort = function (arr) {
  if(arr.length === 1) return arr;

  let halfLth = Math.floor(arr.length / 2)
  let leftArr = arr.slice(0, halfLth)
  let rightArr = arr.slice(halfLth)

  return merge(mergeSort(leftArr), mergeSort(rightArr))
};

function merge (left, right) {
  let result = [];
  while(left.length > 0 && right.length > 0){
    if(left[0] <= right[0]) result.push(left.shift());
    else result.push(right.shift());
  }
  return result.concat(left, right);
}

이렇듯 합병 정렬은 절반, 그리고 그 절반을 나누는 방식으로 진행되기 때문에 시간이 짧게 걸린다는 것을 쉽게 예상할 수 있을 것이다. n개의 원소가 있을 때 완전히 다 나누어지기까지 호출되는 함수의 개수는 $\log n$개라는 것을 알 수 있다. 그리고 합쳐지는 과정에서 각 원소들의 크기를 비교하기 때문에 n번의 비교 과정이 있다. 따라서 합병 정렬의 시간 복잡도는 O($n\log n$)이다.

생각해보기

Q. 합병 정렬에서의 가장 큰 단점은 무엇일까?

A. 아무래도 메모리 공간이 많이 필요하다는 것이 단점이다. 배열을 나눠주는 과정에서 배열을 임시로 저장하고 함수가 종료될 때까지 기억하고 있어야하기 때문에 메모리의 필요한 공간이 늘어나게 된다. 하지만 요즘에는 저장공간을 늘리는 것 보다 처리속도를 높이는 것이 더 부담되는 일이므로 지금까지 다뤄본 알고리즘 중에 가장 효율적인 알고리즘이라고 할 수 있을 것이다.

---

8. 이진 탐색

이진 탐색이란?

자료를 절반으로 나눈 후 찾는 값이 어느 쪽에 있는지 파악해 탐색의 범위를 반으로 줄여나가는 탐색 알고리즘이다.

이진 탐색의 효율성

이진 탐색의 기본은 정렬된 배열일 때 가능하다는 것이다. 50을 찾는 이진 탐색 수도코드는 다음과 같다.

1. 먼저 최소값을 배열의 첫 번째 값(1), 그리고 최대값을 배열의 마지막 값(63)으로 정한다.
2. 중간값을 계산한다. 29가 될 수도 있고 38이 될 수도 있는데, 어떤 값을 정하던 알고리즘은 일관적이기 때문에 상관없다.
3. 29를 중간값으로 사용했을 때, 50은 29보다 크기 때문에 왼편에 있는 값은 볼 필요가 없다.
4. 최소값은 38로 정해지고, 최대값은 그대로 남겨둔 후 같은 방식으로 진행한다.

이진 탐색을 직접 코드로 작성해 보았다.

const binarySearch = function (arr, target) {
  return search(arr, target, 0, arr.length-1);
};

function search(arr, target, start, end){
  let mid = Math.floor( (start+end) / 2);

  if(arr[start] > target || arr[end] < target) return -1;
  if(target === arr[mid]) return mid;
  else if(target < arr[mid]){
    return search(arr, target, start, mid-1);
  }
  else {
    return search(arr, target, mid+1, end);
  }
}

이진 탐색 vs 선형 탐색

이진 탐색은 일반적으로 선형 탐색보다 탐색 속도가 짧지만, 배열을 정리하는 시간이 추가된다. 그렇기 때문에 배열의 값을 선형 탐색하는 것이 배열을 정렬한 후 이진 탐색을 사용하는 것보다 빠르게 보이기도 하고, 실제로 어떤 상황에서는 선형 탐색이 이진 탐색보다 빠르기도 하다.

하지만 배열을 여러 번 탐색할 계획을 하고 있다면 이진 탐색이 유용하게 사용될 것이다. 찾고자 하는 값이 배열에 없는 경우 선형 탐색은 배열의 길이가 얼마든 상관없이 배열 전체를 훑어보아야 배열 안에 찾고자 하는 값이 없다는 것을 알 수 있다. 하지만 이진 탐색에서는 찾고자 하는 값이 최소값보다 작거나 최대값보다 크다면 해당 원소가 배열 안에 없다는 것을 바로 알 수 있다.

생각해보기

Q. 이진 탐색이 선형 탐색보다 효율적인 경우는 언제인가?

A. 우선 배열이 정렬되어 있는 경우는 당연히 이진 탐색이 훨씬 효율적이다. 배열이 정렬되어 있지 않은 경우에서, 데이터의 양이 적은 경우라면 선형탐색이 더 효율적일 수 있을 것이고, 데이터의 양이 많아질 수록 이진 탐색이 점점 더 효율적이게 될 것이라고 생각한다.