20장 코드 최적화 기법

김현수·2022년 3월 8일
누구나 자료 구조와 알고리즘알고리즘
0

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

목록 보기
20/20


다음의 사고 전략은 지난 몇 년간 코드를 더 효율적으로 바꾸는데 큰 역할을 했다.

20.1 전제 조건: 현재 빅 오 파악하기

알고리즘 최적화에 앞서 반드시 해야 할 것은 현재 코드의 효율성을 파악하는 것이다. 얼마나 빠른지 알아야 더 빠르게 만들 수 있다.

20.2 시작점: 상상할 수 있는 최상의 빅 오

"상상할 수 있는 최상의 빅 오"를 생각하는 것은 모든 알고리즘에 유용하며, 반드시 최적화 프로세스의 첫 단계여야 한다.

배열의 각 항목을 출력하는 함수라면 항목 N개를 각각 처리해야 하므로 최상의 빅 오는 O(N)이다.

현재 빅 오와 최상의 빅 오가 다르다면 최적화할 여지가 있다는 뜻이다. 두 빅 오 간 차이는 최적화로 얻을 잠재적 이익을 나타낸다.

  1. 현재 알고리즘의 빅 오 카테고리 알아내기
  2. 당면한 문제에 기대할 수 있는 상상할 수 있는 최상의 빅 오 알아내기
  3. 상상할 수 있는 최상의 빅 오가 현재 빅 오보다 빠르면 알고리즘을 최대한 최상의 빅 오에 가깝게 만들겠다는 목표로 코드 최적화를 위해 노력할 수 있다.

상상할 수 있는 최상의 빅 오를 항상 달성할 수는 없다. 최상의 빅 오는 최적화로 이뤄낼 수 있는 목표를 제시하는 도구다. 보통은 현재 빅 오와 최상의 빅 오 사이쯤으로 최적화한다.

20.2.1 상상의 나래 펼치기

최적화로 달성할 목표를 제시해준다는 점을 최대한 활용하려면, 상상의 나래를 펼쳐 아주 놀라운 상상할 수 있는 최상의 빅 오를 생각해내는 것이 좋다.

누군가 그 빅 오로 문제를 해결할 수 있다고 말했을 때, 그 말을 믿을 수 있다면 그것을 최상의 빅 오로 삼는다.

20.3 룩업 마법

"O(1) 안에 원하는 정보를 찾을 수 있다면 알고리즘을 더 빠르게 바꿀 수 있을까?"라는 질문에 대한 답이 "예"라면, 해시 테이블 같은 자료 구조를 통해 마법을 부릴 수 있다.

20.3.1 저자 룩업 마법

도서관 소프트웨어를 개발하며 책과 저자 데이터를 두 개의 배열에 넣었다고 하자.

const authors = [
  new Map([
    ["authorId", 1],
    ["name", "Virginia Woolf"],
  ]),
  new Map([
    ["authorId", 2],
    ["name", "Leo Tolstoy"],
  ]),
  new Map([
    ["authorId", 3],
    ["name", "Dr. Seuss"],
  ]),
  new Map([
    ["authorId", 4],
    ["name", "J. K. Rowling"],
  ]),
  new Map([
    ["authorId", 5],
    ["name", "Mark Twain"],
  ]),
];

authors는 해시 테이블을 포함하는 배열이고, 각 해시 테이블은 저자의 이름과 ID를 포함한다.

const books = [
  new Map([
    ["authorId", 3],
    ["title", "Hop on Pop"],
  ]),
  new Map([
    ["authorId", 1],
    ["title", "Mrs. Dalloway"],
  ]),
  new Map([
    ["authorId", 4],
    ["title", "Harry Potter and the Sorcerer's Stone"],
  ]),
  new Map([
    ["authorId", 1],
    ["title", "To the Lighthouse"],
  ]),
  new Map([
    ["authorId", 2],
    ["title", "Anna Karenina"],
  ]),
  new Map([
    ["authorId", 5],
    ["title", "The Adventures of Tom Sawyer"],
  ]),
  new Map([
    ["authorId", 3],
    ["title", "The Cat in the Hat"],
  ]),
  new Map([
    ["authorId", 2],
    ["title", "War and Peace"],
  ]),
  new Map([
    ["authorId", 3],
    ["title", "Green Eggs and Ham"],
  ]),
  new Map([
    ["authorId", 5],
    ["title", "The Adventures of Huckleberry Finn"],
  ]),
];

books도 다수의 해시 테이블을 포함한다. 각 해시 테이블은 책 제목과 authorId를 포함하고, authorId로 author 배열에서 저자를 알 수 있다.

title과 author로 데이터를 구성하려면 books 배열을 순회하며 각 책과 그 저자를 연결시켜야 한다.

중첩 반복문을 사용하는 방법이 있다. 밖에선 각 책을 순회하고, 안에선 저자를 확인하며 각 책과 연결된 ID를 갖는 저자를 찾는다.

function connectBooksWithAuthors(books, authors) {
  const booksWithAuthors = [];
  for (let book of books) {
    for (let author of authors) {
      if (book.get("authorId") === author.get("authorId")) {
        booksWithAuthors.push(
          new Map([
            ["title", book.get("title")],
            ["author", author.get("name")],
          ])
        );
      }
    }
  }
  return booksWithAuthors;
}

이 알고리즘의 빅 오는 O(N * M)이다. 이 예제에선 책 N개를 무조건 순회해야 하므로, 최상의 빅 오는 O(N)이다.

O(1) 만에 저자를 찾을 수 있다면 안쪽 반복문이 없앨 수 있고, O(N)으로 속도를 올릴 수 있다.

20.3.2 자료 구조 추가하기

룩업 마법 능력을 실현할 가장 쉬운 방법 중 하나는 코드에 자료 구조를 추가하는 것이다. 대개 해시 테이블이 적합한데 O(1)만에 룩업할 수 있기 때문이다.

저자 정보가 현재는 배열에 저장되어 있어서 저자를 찾는데 항상 O(M) 단계가 걸린다. 이를 해시 테이블에 저장하면 O(1)만에 찾을 수 있다.

const authorHashTable = new Map([
  [1, "Virginia Woolf"],
  [2, "Leo Tolstoy"],
  [3, "Dr. Seuss"],
  [4, "J. K. Rowling"],
  [5, "Mark Twain"],
]);

이 해시 테이블에서 키는 저자 ID이고, 각 키의 값은 저자 이름이다.

function connectBooksWithAuthors(books, authors) {
  const booksWithAuthors = [];
  const authorHashTable = new Map();
  for (let author of authors) {
    authorHashTable.set(author.get("authorId"), author.get("name"));
  }
  for (let book of books) {
    booksWithAuthors.push(
      new Map([
        ["title", book.get("title")],
        ["author", authorHashTable.get(book.get("authorId"))],
      ])
    );
  }
  return booksWithAuthors;
}

먼저 authors 배열을 순회하며 그 데이터로 authorHashTable을 생성한다. 저자 M명에 M단계가 걸린다.

이어 books 배열을 순회하며 authorHashTable을 사용해 한 단계만에 각 저자를 찾는다. 책 N권에 n단계가 걸린다.

총 O(N + M)단계가 걸린다. O(N * M)단계였던 원래 알고리즘보다 훨씬 빠르다. 단 공간을 O(M)만큼 더 사용한다. 속도를 위해 메모리를 희생할 수 있다면 대단한 최적화다.

20.3.3 두 수의 합(two-sum) 문제

두 수의 합 문제는 숫자 배열을 입력 받아 합해서 10(또는 주어진 다른 수)이 되는 두 수가 배열에 있는지를 true나 false로 반환하는 함수를 작성하는 문제다. 배열에 중복은 없다고 가정한다.

[2, 0, 4, 1, 7, 9] 배열에서 1 + 9 = 10이므로 true를 반환해야 한다. [2, 0, 4, 5, 3, 9]는 false를 반환해야 한다.

중첩 반복문을 사용해 작성할 수 있다.

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

전형적인 중첩 알고리즘으로 O(N²)이다.
배열의 각 수를 무조건 최소 한 번은 방문해야 하므로 최상의 빅 오는 O(N)이다.

[2, 0, 4, 1, 7, 9] 예제에서 배열을 순회한다고 하자. 첫 요소인 2를 순회하며 배열 어딘가에 8이 있는지 알고 싶다. 8이 있는지 O(1)만에 룩업할 수 있다면 바로 true를 반환할 수 있다.

배열 내 어떤 숫자든 O(1) 만에 룩업해야 하므로 숫자를 해시 테이블에 키로 저장한다. 해시 테이블은 다음과 같다.

Map(6) {2 => true, 0 => true, 4 => true, 1 => true, 7 => true, 9 => true}

값은 임의의 항목일 수 있으며, 여기선 true로 한다.

구하려는 숫자는 10에서 그 숫자를 빼서 계산하면 된다. 이 구하려는 숫자를 "보수"라고 칭한다.
이를 토대로 알고리즘을 만들면 다음과 같다.

function twoSum(array) {
  let hashTable = new Map();

  for (let i = 0; i < array.length; i++) {
    if (hashTable.get(10 - array[i])) {
      return true;
    }

    hashTable.set(array[i], true);
  }
  return false;
}

배열의 각 숫자를 한 번씩 순회한다.
각 숫자에 방문할 때마다 보수가 해시 테이블에 키로 있는지 확인한다. 10-array[i]로 구할 수 있다.

만일 찾았다면 합해서 10이 되는 두 수를 찾았다는 뜻이니 true를 반환한다.

각 숫자를 순회하며 그 숫자를 해시 테이블에 키로 삽입한다. 이런 식으로 배열을 검색하며 각 숫자로 해시 테이블을 채운다.

이 방법을 사용하면 O(N)으로 빨라지게 할 수 있다.

20.4 패턴 인식

코드 최적화와 알고리즘 개발에 전반적으로 쓰이는 가장 유용한 전략 중 하나가 패턴을 찾는 방식이다.

20.4.1 동전 게임

동전 더미를 가운데 쌓아놓고, 두 명의 플레이어가 차례로 동전 더미에서 동전을 하나 혹은 두 개 없앤다. 마지막 동전을 없애는 플레이어가 게임에서 진다.

더미에 동전이 하나면 자기 차례인 선수가 진다.
동전이 두 개라면 자기 차례인 선수가 하나만 가져가서 이길 수 있다.
세 개라면 자기 차례인 선수가 두 개를 가져가서 이길 수 있다.
네 개가 남는다면 어떤 선택을 하든 질 수밖에 없다.

동전 더미에 놓인 동전 개수가 주어졌을 때 게임에서 이길 수 있는지 계산하는 함수를 작성하려면 하향식 재귀를 사용할 수 있다.

function gameWinner(numberOfCoins, currentPlayer = "you") {
  if (numberOfCoins <= 0) {
    return currentPlayer;
  }

  let nextPlayer = currentPlayer === "you" ? "them" : "you";

  if (
    gameWinner(numberOfCoins - 1, nextPlayer) === currentPlayer ||
    gameWinner(numberOfCoins - 2, nextPlayer) === currentPlayer
  ) {
    return currentPlayer;
  } else {
    return nextPlayer;
  }
}

기저 조건은 currentPlayer에 0개 이하의 동전이 남았을 때다. 상대방이 마지막 동전을 가져간 것이므로 현재 플레이어가 자동으로 게임에서 이긴다.

다음 플레이 할 nextPlayer를 정의하고 재귀를 수행한다.

현재 더미보다 한 개 적은 경우와 두 개 적은 경우를 재귀 호출해 두 시나리오 모두 다음 플레이어가 지면 현재 플레이어가 이긴다.

이 알고리즘은 O(2ⁿ)이다. 메모이제이션을 활용하면 동전 더미의 개수가 N개일 때 O(N)까지 개선할 수 있다. N은 숫자 하나이므로 O(1)을 목표로 삼을 수 있다.

20.4.2 예제 생성

문제마다 패턴이 고유하나, 수많은 예제를 생성하는 것은 모든 문제에 걸쳐 유용한 패턴 찾기 기법이다.

동전 개수승자
1상대방
2당신
3당신
4상대방
5당신
6당신
7상대방
8당신
9당신
10상대방

패턴이 명확해진다. 코인 1개에서 시작해 2번 걸러 1번씩 상대방이 이긴다. 나머지는 당신이 승자다.

즉, them은 동전 개수에서 1을 뺐을 때 3으로 나눠지는 수다. 나눗셈 계산 하나로 누가 이길지 알 수 있다.

function gameWinner(numberOfCoins) {
  return (numberOfCoins - 1) % 3 ? "you" : "them";
}

시간과 공간 관점에서 O(1)으로 개선할 수 있다.

20.4.3 합 교환(sum-swap) 문제

패턴 인식과 마법 룩업을 함께 사용해 알고리즘을 최적화할 수 있는 예제를 하나 살편다.

정수 배열 두개를 받는 함수를 작성한다. [5,3,2,9,1] [1,12,5]일 때, 1번 배열의 합은 20이고 2번 배열의 합은 18이다. 함수는 서로 교환했을 때 두 배열의 합이 똑같아지는 숫자를 각 배열에서 하나씩 찾아야 인덱스를 반환해야 한다. 1번 배열의 2와 2번 배열의 1을 바꾸면 두 배열 모두 합이 19가 되니 [2, 0]을 반환하면 된다. 없다면 null을 반환한다.

각 배열의 요소를 모두 순회하는 중첩 반복문을 통해 해결할 수 있고, 이 경우 O(N * M)이다. 최상의 시나리오는 두 배열 모두 한 번만 순회하는 O(N + M)이다.

여러 패턴들을 작성해보면, 교환 후 각 배열의 합이 항상 두 배열의 합 사이 중간에 떨어진다는 것을 알 수 있다. 이 패턴을 이용한다.

const shiftAmount = (sum1 - sum2) / 2;

sum1은 첫 배열의 합이고 sum2는 두번째 배열의 합이다. 각 배열의 합의 차이를 반으로 나누면 각 배열이 얼만큼 변해야 하는지 알 수 있다. 따라서 두 배열의 합을 계산하는 것부터 알고리즘을 만든다. 다음으로 배열 하나의 숫자를 순회하면서 나머지 배열에서 보수를 찾는다.

이때 한 배열의 숫자들을 해시 테이블에 저장하면 나머지 배열을 순회하며 보수를 O(1)만에 찾을 수 있다.

function sumSwap(array1, array2) {
  let hashTable = new Map();
  let sum1 = 0;
  let sum2 = 0;

  for (let i = 0; i < array1.length; i++) {
    sum1 += array1[i];
    hashTable.set(array1[i], i);
  }

  for (let num of array2) {
    sum2 += num;
  }

  const shiftAmount = (sum1 - sum2) / 2;

  for (let j = 0; j < array2.length; j++) {
    if (hashTable.get(array2[j] + shiftAmount)) {
      return [hashTable.get(array2[j] + shiftAmount), j];
    }
  }

  return null;
}

이 방식을 사용하면 O(N+M)이다. array2를 두번 순회하므로 엄밀히 말하면 2M이지만 상수는 무시한다.

공간적으로는 O(N)만큼을 더 소모한다.

20.5 탐욕 알고리즘

탐욕(greedy) 알고리즘은 매 단계마다 그 순간에 최선처럼 보이는 방법을 고른다.

20.5.1 배열 최댓값

배열에서 가장 큰 숫자를 찾는 알고리즘을 작성한다.

  1. 중첩 반복문으로 각 숫자를 배열 내 나머지 숫자와 비교하는 방법이 있다. O(N²)이 걸린다.
  2. 배열을 정렬해 마지막 값을 반환하는 방법이 있다. 퀵 정렬을 사용한다면 O(N logN)이 걸린다.
  3. 탐욕 알고리즘을 사용할 수 있다.
function max(array) {
  let greatestNumber = array[0];
  for (let number of array) {
    if (number > greatestNumber) {
      greatestNumber = number;
    }
  }
  return greatestNumber;
}

배열의 첫 번째 수를 greatestNumber로 가정하고 있다. 이것이 "탐욕스러운 greedy" 가정이다. 현재까지 본 가장 큰 숫자이므로 선언한 것이다. 그 순간에 이용할 수 있는 정보를 바탕으로 최선처럼 보이는 방법을 고른다.

이후 배열을 순회하며 greatestNumber보다 큰 숫자를 찾을 때마다 그 숫자를 greatestNumber로 바꾼다. 매 단계마다 그 순간에 알고 있는 정보를 바탕으로 최선의 방법을 고른다.

이 알고리즘은 배열의 숫자를 한 번씩만 처리하므로 O(N)이 소요된다.

20.5.2 최대 부분 합

숫자로 된 배열을 받아 그 배열의 어느 부분에서 계산할 수 있는 가장 큰 합을 반환하는 함수를 작성하려 한다.

[3, -4, 4, -3, 5, -9] 배열의 전체 합은 -4다. 목표는 배열 내 어느 부분에서 계산할 수 있는 가장 큰 합을 찾는 것이다. 이 예시에서는 인덱스 2부터 4까지, 4 + -3 + 5 = 6이다.

배열 내 양수가 적어도 하나 이상 있다고 가정한다.

배열의 모든 부분에 대해 합을 계산한 후 가장 큰 합을 고를 수 있다. 약 N²/2 개의 부분이 만들어지므로 O(N²)이다. 최상의 빅 오는 각 숫자를 한 번씩 검사하는 O(N)이다.

최대 부분 합 문제에 탐욕 알고리즘을 적용하면 배열을 순회할 때 매 단계마다 최대 합을 고르려 할 것이다.

[3, -4, 4, -3, 5, -9]의 맨 앞인 3에서 시작한다. 최대 합은 3이다.
-4에 도달한다. 3과 더하면 현재 합은 -1이다. 여전히 최대 합은 3이다.
4에 도달한다. -1과 더하면 현재 합은 3이다. 여전히 최대 합은 3이다.
-3에 도달한다. 3과 더하면 현재 합은 0이다. 여전히 최대 합은 3이다.
5에 도달한다. 0과 더하면 현재 합은 5다. 최대 합은 5가 된다.
-9에 도달해 5와 더하면 현재 합은 -4고 최대 합은 5이다.

하지만 최대 부분 합은 6이므로 위 알고리즘은 틀렸다.

하지만 탐욕 알고리즘은 대개 살짝 수정해야 한다.

패턴 여러 개를 살펴보면 음수로 인해 앞선 부분의 합이 음수로 떨어지면 방해가 된다. 하지만 음수가 현재 부분 합을 감소 시켜도 합이 여전히 양수라면 방해가 되지 않는다. 다시 수정하면 다음과 같다.

[3, -4, 4, -3, 5, -9]의 맨 앞인 3에서 시작한다. 최대 합은 3이다.
-4에 도달한다. 3과 더하면 현재 합은 -1이다. 현재 합을 0으로 되돌린다.
4에 도달한다. 현재 합, 최대 합은 4이다.
-3에 도달한다. 4와 더하면 현재 합은 1이다. 여전히 최대 합은 4이다.
5에 도달한다. 1과 더하면 현재 합은 6이다. 최대 합은 6이 된다.
-9에 도달해 6과 더하면 현재 합은 -3이다. 현재 합을 0으로 되돌린다.
배열의 끝에 도달했고 최대 합은 6이다.

function maxSum(array) {
  let currentSum = 0;
  let greatestSum = 0;

  for (let num of array) {
    if (currentSum + num < 0) {
      currentSum = 0;
    } else {
      currentSum += num;
      if (currentSum > greatestSum) {
        greatestSum = currentSum;
      }
    }
  }
  return greatestSum;
}

배열을 한 번만 순회하므로 O(N)이다. 공간 복잡도도 O(1)이다.

20.5.3 탐욕스러운 주가 예측

주가 배열을 받아 상승세를 이루는 주가 3개가 있는지 알아내는 함수를 작성한다.

[22, 25, 21, 18, 19.6, 17, 16, 20.5] 라는 배열은 상승세를 이루는 주가가 18, 19.6, 20.5로 3개 있다. 즉, 오른쪽 가격(20.5)이 중간 가격(19.6)보다 크고, 중간 가격이 왼쪽 가격(18)보다 크다. 따라서 true를 반환해야 한다.

[50, 51.25, 48.4, 49, 47.2, 48, 46.9] 는 상승세를 이루는 주가 3개를 포함하지 않으므로 false를 반환해야 한다.

중첩 반복문 3개를 이용할 수 있지만 O(N³)이다. 최상의 빅 오는 각 주가를 한번씩 검사하는 O(N)이다.

이 경우 탐욕 알고리즘을 사용한다는 것은 상승세를 이룰 3개의 주가 중 저점이라고 생각하는 주가를 어떻게든 잡아두는 것이다. 추세의 중간과 고점이라고 생각하는 주가도 똑같이 잡아두고 싶다.

첫 번째 주가를 상승세를 이루는 주가 3개의 저점이라고 가정한다.
중간 주가는 배열에서 가장 높은 주가보다 무조건 더 큰 숫자로 초기화한다. 이를 위해 무한대로 할당한다.

  1. 현재 주가가 지금까지의 최저가보다 작으면 현재 주가가 새로운 최저가가 된다.
  2. 현재 주가가 최저가보다 크지만 중간 주가보다 작으면 중간 주가를 현재 주가로 업데이트 한다.
  3. 현재 주가가 최저가와 중간 주가보다 크면 상승세를 이루는 주가 3개를 찾았다는 뜻이다.

[5, 2, 8, 4, 3, 7]의 예시를 든다. 5부터 순회를 시작하고, 최저가라고 가정한다.
2는 5보다 작으므로 최저가라고 가정한다.
8은 현재 중간 주가인 무한대보다 작으므로 8을 중간 주가로 할당한다. 최저가는 2다.
4는 현재 중간 주가인 8보다 작으므로 4를 중간 주가로 할당한다. 최저가는 2다.
3은 현재 중간 주가인 3보다 작으므로 3을 중간 주가로 할당한다. 최저가는 2다.
7은 현재 중간 주가인 3보다 크므로 배열이 3개짜리 상승세를 포함한다는 뜻으로 true를 반환한다.

배열 내 상승세는 2-3-7, 2-4-7 두 개지만 상승세가 있는지만을 알아내면 되므로 중요하지 않다.

function increasingTriplet(array) {
  let lowestPrice = array[0];
  let middlePrice = Infinity;

  for (let price of array) {
    if (price <= lowestPrice) {
      lowestPrice = price;
    } else if (price <= middlePrice) {
      middlePrice = price;
    } else {
      return true;
    }
  }

  return false;
}

어떤 시나리오에서 알고리즘이 동작하지 않을 것처럼 보이는데 실제로는 동작한다.

increasingTriplet([8, 9, 7, 10])을 예로 들면, 함수 실행 후 중간점은 9, 최저점은 7, 최고점은 10이다. 최고점이 중간점보다 크므로 true를 반환한다. 하지만 최저점 7은 상승세에 속하지 않는다.

함수가 하는 일은 중간점보다 큰 숫자를 찾는 것이다. 중간점은 저점을 찾은 뒤에야 정해지므로 중간점보다 큰 숫자에 도달하면 배열에 상승세가 정해진다는 뜻이다. 저점을 덮어쓰더라도 이 사실은 변하지 않는다.

어쨌든 위 알고리즘을 통해 O(N)으로 개선할 수 있다.

탐욕 알고리즘이 항상 통하지는 않지만, 최적화할 때 시도할 수 있는 방법 중 하나다.

20.6 자료 구조 변경

데이터를 다른 자료 구조에 저장했을 때 어떻게 될지 상상해 보는 것도 유용한 최적화 기법 중 하나다.

배열 형태를 해시 테이블, 트리 등 다른 자료 구조에 저장한다고 생각해 보면 기발한 최적화 기회가 생기기도 한다.

20.6.1 애너그램 검사기

두 문자열이 주어졌을 때 서로 애너그램인지 알아내는 함수를 작성한다. 두 문자열을 비교해 서로 애너그램이면 true를, 아니면 false를 반환한다.

애너그램 생성함수를 사용해 문제를 해결할 수 있다. 첫 문자열의 모든 애너그램을 만들어서 두 번째 문자열에 그 중 하나인지 확인한다. 하지만 이는 O(N!)이 걸려 너무 느리다.

최상의 빅 오는 두 문자열을 한 번씩 순회하는 것으로 O(N + M)이다.

중첩 문자열을 통해 비교할 수 있다. 첫 문자열의 각 문자열을 순회하면서 두 번째 문자열에서 그 문자를 삭제한다. 첫 문자의 모든 문자가 두 번째 문자에 존재한다면 반복문이 종료됐을 때 두 번째 문자열의 문자가 모두 삭제되어있을 것이다. 남아있다면 애너그램이 아니라는 뜻이다. 또한, 아직 반복문이 종료되지 않았는데 두 번째 문자열이 비었어도 애너그램이 아니다.

function areAnagrams(firstString, secondString) {
  const secondStringArray = secondString.split("");

  for (let i = 0; i < firstString.length; i++) {
    if (secondStringArray.length === 0) {
      return false;
    }

    for (let j = 0; j < secondStringArray.length; j++) {
      if (firstString[i] === secondStringArray[j]) {
        secondStringArray.splice(j, 1);
      }
    }
  }
  return secondStringArray.length === 0;
}

배열을 순회하면서 그 배열의 항목을 삭제하는 것은 오류가 발생하기 쉽다. 정확하게 처리한다고 해도 O(N * M)이 소요된다. 목표로하는 O(N + M)보다 느린 속도이다.

두 문자열을 정렬해 서로 똑같으면 애너그램인지를 판단할 수 있다. 이 경우 O(N logN)으로 여전히 O(N + M)보단 느리다.

입력은 문자열이지만 다른 자료 구조인 해시 테이블에 저장한다고 상상해보자. 각 문자열을 키로, 값을 단어 내 문자 출현 빈도로 해서 해시 테이블을 생성할 수 있다. "balloon"을 해시 테이블로 나타내면 Map(5) {'b' => 1, 'a' => 1, 'l' => 2, 'o' => 2, 'n' => 1} 이다.

이 해시 테이블은 문자열 내의 문자들의 순서는 알 수 없다. 하지만 두 문자열이 각 문자를 같은 개수로 가지고 있으면 순서와 상관없이 애너그램이므로 상관 없다.

각 문자열을 해시 테이블로 변환해서 문자 타입별 개수를 기록하는 알고리즘을 작성할 수 있다. 각각 변환하고 두 해시 테이블만 비교하면 된다. 동일하면 두 문자열이 애너그램이라는 뜻이다.

function areAnagrams(firstString, secondString) {
  let firstWordHashTable = new Map();
  let secondWordHashTable = new Map();

  for (let char of firstString) {
    if (firstWordHashTable.has(char)) {
      firstWordHashTable.set(char, firstWordHashTable.get(char) + 1);
    } else {
      firstWordHashTable.set(char, 1);
    }
  }

  for (let char of secondString) {
    if (secondWordHashTable.has(char)) {
      secondWordHashTable.set(char, secondWordHashTable.get(char) + 1);
    } else {
      secondWordHashTable.set(char, 1);
    }
  }

  for (let key of firstWordHashTable.keys()) {
    if(firstWordHashTable.get(key) === secondWordHashTable.get(key)) {
      firstWordHashTable.delete(key);
      secondWordHashTable.delete(key);
    }
  }

  return !(secondWordHashTable.size || firstWordHashTable.size);
}

두 문자열 내 각 문자를 딱 한 번씩 순회하므로 N+M 단계가 걸린다. 그리고 해시 테이블을 비교하는데 N단계가 걸린다. 그래도 O(N+M)이다. 공간을 더 소모하긴 하지만 앞선 버전들보다 빠르다.

어떤 자료 구조를 사용해야 하는지 항상 분명한 것은 아니므로 현재 데이터를 다양한 형식으로 변환한 모습을 상상해 보고 최적화가 가능한지 판단해야 한다. 대부분은 해시 테이블이 탁월한 선택이다.

20.6.2 그룹 정렬

값을 여러 개 포함하는 배열이 있을 때 같은 값끼리 묶어 데이터를 다시 정렬하고 싶다. 단 그룹의 순서는 중요하지 않다.

["a", "c", "d", "b", "b", "c", "a", "d", "c", "b", "a", "d"]를 ["c", "c", "c", "a", "a", "a", "d", "d", "d", "b", "b", "b"]로 정렬한다. 정렬한 배열에서 어떤 알파벳이 먼저 정렬되느냐는 중요하지 않다.

정렬 알고리즘을 사용하면 그룹 정렬이 가능하다. 이는 O(N logN)이다. 이것이 가장 빠른 정렬 알고리즘이니 더 빠르게 정렬하는 법은 없다. 정렬해야 하는 것은 아니니 그룹 정렬의 최상의 빅 오는 O(N)이다.

문자열 배열을 해시 테이블에 저장하면 Map(4) {'a' => 3, 'b' => 3, 'c' => 3, 'd' => 3}이 될 것이다. 해시 테이블 내 각 키값 쌍을 순회하면서 그 데이터를 사용해 각 문자열의 개수만큼배열에 덧붙일 수 있다.

function groupArray(array) {
  let hashTable = new Map();
  let newArray = [];

  for (let value of array) {
    if (hashTable.has(value)) {
      hashTable.set(value, hashTable.get(value) + 1);
    } else {
      hashTable.set(value, 1);
    }
  }

  for (let [key, count] of hashTable) {
    for (let i = 0; i < count; i++) {
      newArray.push(key);
    }
  }
  return newArray;
}

빈 해시 테이블과 빈 배열을 생성한다. 해시 테이블에 각 문자열의 합계를 모아 저장한다. 각 키값 쌍을 순회하며 이 데이터를 newArray에 덧붙인다.

이 알고리즘은 O(N)이다. O(N logN)에 비해 상당히 최적화 했다. 공간을 최대 O(N) 더 사용한다.

20.7 요약

20장에서 소개한 기법은 코드를 최적화하는 데 유용하다. 현재 빅 오와 최상의 빅 오를 알아내는 것이 먼저다. 그래야 다른 모든 기법을 자유자재로 사용할 수 있다.

20.8 작별 인사

알고리즘 디자인과 자료 구조의 올바른 선택이 코드 성능에 중대한 영향을 줄 수 있음을 배웠다.
코드 효율성을 알아내는 법을 배웠다.
코드를 더 빠르고 메모리 효율적이면서 간결하게 최적화하는 법도 배웠다.

벤치마킹 도구로 사용자가 수행한 최적화를 테스트하는 것이 늘 최선이다. 이 책의 지식은 올바른 방향으로 인도하고, 벤치마킹 도구는 올바른 선택인지 확인해 준다.

자료 구조와 알고리즘이라는 주제는 넓고 깊으며, 이 책은 수박 겉핥기 식으로만 다뤘다.

화이팅!

profile
김현수
이전 포스트

19장 공간 제약 다루기

0개의 댓글