6장 긍정적인 시나리오 최적화

김현수·2022년 2월 9일

누구나 자료 구조와 알고리즘 알고리즘

누구나 자료 구조와 알고리즘

목록 보기

6/20

지금까지는 최악의 시노리오에서 얼마나 많은 단계가 걸리는지에 초점을 맞췄다. 하지만 최악의 시나리오 외에도 고려할 가치가 있는 상황들이 있다.

6.1 삽입 정렬

삽입 정렬을 배우면서 최악의 경우가 아닌 다른 시나리오를 분석하는 것에 어떤 장점이 있는지 알아보자.

첫 번째 패스스루에서 임시로 인덱스 1의 값을 삭제하고 이 값을 임시 변수에 저장한다. 값이 없어졌으므로 공백이 생긴다.
이후 각 패스스루마다 다음 인덱스의 값을 삭제한다.
다음으로 공백 왼쪽에 있는 각 값을 가져와 임시 변수에 있는 값과 비교하는 시프트 단계를 시작한다. 왼쪽의 값이 임시 변수 값보다 크다면 그 값을 오른쪽으로 시프트 한다.
왼쪽의 값이 공백으로 이동했기에 이제는 공백이 왼쪽에 있다. 임시 변수 값보다 작은 값을 만나거나 공백이 왼쪽 끝에 도달해야 시프트 단계가 끝난다.
임시 변수 값을 현재 공백에 삽입한다.
1-3단계가 하나의 패스스루다. 배열의 마지막 인덱스에서 패스스루를 시작할 때까지 패스스루를 반복한다.

6.2 삽입 정렬 실제로 해보기

[4, 2, 7, 1, 3]을 삽입 정렬해보자.

인덱스 1의 2를 삭제하고 tempValue라는 변수에 저장한다.
4와 tempValue를 비교한다.
4가 tempValue보다 크므로 4를 오른쪽으로 시프트 한다. 공백이 배열의 왼쪽 끝에 있으므로 더 이상 왼쪽으로 시프트할 수 없다.
tempValue를 다시 배열에 삽입해서 첫 번째 패스스루를 끝낸다. [2, 4, 7, 1, 3]

두 번째 패스스루는 인덱스 2의 7을 삭제하고 tempValue 변수에 저장한다.
4와 tempValue를 비교한다. 4가 더 작으므로 시프트하지 않는다. tempValue보다 작은 값을 만났으므로 시프트 단계가 끝난다.
tempValue를 다시 배열에 삽입해서 두 번째 패스스루를 끝낸다. [2, 4, 7, 1, 3]

인덱스 3의 1을 삭제하고 tempValue 변수에 저장한다.
7과 tempValue를 비교한다.
7이 tempValue보다 크므로 7을 오른쪽으로 시프트한다.
4와 tempValue를 비교한다.
4가 tempValue보다 크므로 4를 오른쪽으로 시프트한다.
2와 tempValue를 비교한다.
2가 tempValue보다 크므로 2를 오른쪽으로 시프트한다. 공백이 배열의 왼쪽 끝에 있으므로 더 이상 왼쪽으로 시프트할 수 없다.
tempValue를 다시 배열에 삽입해서 세 번째 패스스루를 끝낸다. [1, 2, 4 ,7, 3]

인덱스 4의 3을 삭제하고 tempValue 변수에 저장한다.
7과 tempValue를 비교한다.
7이 tempValue보다 크므로 7을 오른쪽으로 시프트한다.
4와 tempValue를 비교한다.
4가 tempValue보다 크므로 4를 오른쪽으로 시프트한다.
2와 tempValue를 비교한다. 2가 더 작으므로 시프트하지 않는다. tempValue보다 작은 값을 만났으므로 시프트 단계가 끝난다.
tempValue를 다시 배열에 삽입한다. 배열이 정렬되었다. [1, 2, 3, 4, 7]

6.2.1 삽입 정렬 구현

const insertionSort = (array) => {
  for (let index = 1; index < array.length; index++) {
    const tempValue = array[index];
    let position = index - 1;

    while (position >= 0) {
      if (array[position] > tempValue) {
        array[position + 1] = array[position];
        position = position - 1;
      } else {
        break;
      }
    }

    array[position + 1] = tempValue;
  }

  return array;
};

for문으로 인덱스 1부터 전체 배열을 시작하는 반복문을 시작한다. 매루프가 하나의 패스스루다.

각 패스스루마다 임시 제거한 값을 tempValue 변수에 저장한다.

position 변수는 tempValue와 비교할 각 인덱스로, tempValue의 바로 왼쪽 인덱스에서 시작한다.

while 문을 돌며 position과 tempValue를 비교하기 시작한다.

만일 array[position]이 tempValue보다 크다면 오른쪽으로 시프트한다. (array[position + 1] = array[position])
- 이어서 다음 값과 비교하기 위해 position을 1 감소시킨다.
만일 tempValue보다 같거나 작은 array[position]을 만났다면 시프트를 종료한다.
while문의 마지막 단계는 공백에 tempValue를 삽입하는 것이다.

6.3 삽입 정렬의 효율성

삽입 정렬에 포함된 단계는 삭제, 비교, 시프트, 삽입의 네 종류다.

비교: 공백 왼쪽에 있는 값과 tempValue를 비교할 때마다 일어난다.
- 최악의 시나리오에선 각 패스스루마다 tempValue를 왼쪽에 있는 모든 수와 비교해야 한다.
- 즉, 1 + 2 + 3 + ... + (N-1) 번의 비교를 수행한다. 이는 대략 (N²/2)번의 비교가 일어난다.
시프트: 값을 한 셀 오른쪽으로 옮길 대마다 일어난다.
- 최악의 시나리오에선 비교할 때마다 시프트해야 한다.
- 즉, 최악의 시나리오에선 비교와 같은 대략 (N²/2)번의 시프트가 일어난다.
- 따라서, 최악의 시나리오에서 비교 + 시프트 = N²이다.
삭제, 삽입: 패스스루당 한 번 일어난다.
- 패스스루는 항상 N-1번이므로, N-1번의 삭제, N-1번의 삽입이 일어난다.

따라서, 이를 모두 더하면 N²+2N-2 단계이다. 빅 오 표기법으로 상수를 모두 제거하면 O(N²+N)이다.

하지만, 다양한 차수가 한데 섞여 있을 때 빅 오 표기법은 "가장 높은 차수의 N만 고려"한다.
즉, O(N²+N)은 O(N²)으로 표기하므로, 삽입 정렬은 O(N²)이다.

6.4 평균적인 경우

최악의 시나리오에서 선택 정렬은 N²/2 단계가 걸리므로 삽입 정렬보다 빠르다.

하지만 정의에 따르면 가장 자주 일어나는 경우가 평균 시나리오다.
따라서 평균 시나리오도 중요하게 고려해야 한다.

삽입 정렬의 시나리오별 단계는 다음과 같다.

최악의 시나리오(역순 정렬): 패스스루마다 모든 값을 비교하고 시프트한다. 비교와 시프트를 합쳐 총 N²번이다.
최선의 시나리오(이미 정렬됨): 패스스루 당 한 번의 비교만 하며 시프트는 한 번도 일어나지 않는다.
데이터가 임의로 정렬된 경우:
- 모든 값을 시프트하는 패스스루가 있을 수도 있고, 시프트를 하지 않는 패스스루가 있을 수도 있다.
- 대체적으로 데이터의 반을 비교하고 시프트할 것이다.
- 최악의 시나리오가 N²이므로, 이것의 절반을 수행하는 평균 시나리오에서는 N²/2 단계가 걸린다고 할 수 있다.

즉, 삽입 정렬은 시나리오에 따라 성능이 크게 좌우된다. 최악 - N²단계, 평균 - N²/2단계, 최선 - N단계.
하지만 선택 정렬은 최악, 평균, 최선의 시나리오 모두 N²/2 단계가 걸린다.

평균적인 경우 두 정렬은 유사하게 수행된다.
거의 정렬된 데이터인 경우 삽입 정렬이 낫다.
대부분 역순으로 정렬된 데이터인 경우 선택 정렬이 더 빠르다.

6.5 실제 예제

두 배열의 교집합을 구한다고 하자. [3, 1, 4, 2]와 [4, 5, 3, 6]의 교집합은 [3, 4]다.

const intersection = (firstArray, secondArray) => {
  let result = [];

  for (let i = 0; i < firstArray.length; i++) {
    for (let j = 0; j < secondArray.length; j++) {
      if (firstArray[i] === secondArray[j]) {
        result.push(firstArray[i]);
      }
    }
  }

  return result;
};

중첩 루프를 돌면서 첫 배열의 각 원소에 대해 두 번째 배열의 모든 원소를 비교한다. 두 배열의 크기가 같다면 N²번의 비교가 일어난다.
만일 두 배열이 동일하다면 N번의 삽입이 일어난다.
빅 오 표기법은 가장 높은 차수만 고려하므로 이 알고리즘은 O(N²)이다.

이 알고리즘은 모든 경우, 즉 교집합이 없을 경우부터 두 배열이 동일한 경우까지 모두 N²번의 비교를 수행한다.
하지만 두 배열의 공통 값이 있다면 첫 번째 배열의 어떤 값을 꼭 두 번째 배열의 모든 원소와 비교하지 않아도 된다.
[3, 1, 4, 2]와 [4, 5, 3, 6]의 예시에서, 4의 루프를 돌 때 두 번째 배열의 첫 번째 요소가 4인 걸 확인하면 두 번째 배열의 다른 원소와는 비교할 필요가 없다.

const intersection = (firstArray, secondArray) => {
  let result = [];

  for (let i = 0; i < firstArray.length; i++) {
    for (let j = 0; j < secondArray.length; j++) {
      if (firstArray[i] === secondArray[j]) {
        result.push(firstArray[i]);
        break;
      }
    }
  }

  return result;
};