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

19장 공간 제약 다루기

• 공간 복잡도의 빅 오

  • 책의 전반에서 다양한 알고리즘의 효율성을 분석하면서 오로지 알고리즘이 얼마나 빠른가, 즉 시간 복잡도에만 초점을 맞췄다면 또 다른 척도로 얼마나 많은 메모리를 소모하는가인 공간 복잡도가 유용할 수 있다.
  • 공간복잡도도 시간복잡도와 마찬가지로 빅 오로 표현할 수 있는데 데이터 원소가 N개일때 알고리즘은 메모리 단위를 얼마나 소모하는지를 나타낸다.

  //새로운 배열을 생성해 추가 메모리를 소모하는 공간복잡도 O(N)의 함수
  function makeUppercase(array) {
    let newArray = [];
    for(let i = 0; i < array.length; i++) {
      newArray[i] = array[i].toUpperCase();
    }
    return newArray;
  }

  //기존 배열을 사용하는 공간복잡도 O(1)의 함수
  function makeUppercase(array) {
    for(let i = 0; i < array.length; i++) {
      array[i] = array[i].toUpperCase();
    }
    return array;
  }

  • 두 함수 모두 문자열을 담긴 배열을 대문자로 변환하는 함수로 첫번째의 경우 새로운 배열을 생성하여 리턴하므로 데이터 원소가 N개일때 N개의 공간이 필요하므로 O(N)의 공간복잡도를 가지며, 두번째 함수의 경우 기존의 배열에 대문자로 변환한 데이터를 저장하므로 0개의 공간이 추가적으로 필요하므로 O(1)로 표현한다.
  • 공간복잡도는 알고리즘에서 새로 생성한 데이터만 고려하며, 추가로 소모한 공간을 보조 공간(auxiliary space)라고 부른다.

• 시간과 공간 트레이드오프

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

  //버전 2
  function hasDuplicateValue(array) {
      let existingValues = {};
      for(let i = 0; i < array.length; i++) {
          if(!existingValues[array[i]]) {
              existingValues[array[i]] = true;
          } else {
              return true;
          }
      }
      return false;
  }

  버전	시간 복잡도	공간 복잡도
  버전1	O(N2)	O(1)
  버전2	O(N)	O(N)

  배열을 받아 중복 값이 있는지 확인해 반환하는 함수로 첫번째 버전은 중첩루프를 사용하여 시간복잡도가 O(N2)이지만 추가적인 메모리를 사용하지 않아 공간복잡도는 O(1)이다.
  반대로 두번째 버전은 배열을 한번만 순회하여 객체를 통해 중복 여부를 검사하여 시간복잡도 O(N), 공간복잡도 O(N)을 가진다.

  => 어떤 알고리즘을 고를지는 상황에 따라서 애플리케이션의 속도가 중요한지, 혹은 메모리를 절약해서 써야하는 상황인지를 고려해서 선택해야 한다.

  function hasDuplicateValue(array) {
      array.sort((a, b) => (a < b) ? -1 : 1);
  
      for(let i = 0; i < array.length - 1; i++) {
          if (array[i] === array[i + 1]) {
              return true;
          }
      }
      return false;
  }

  세번째 버전은 정렬 이후에 중복 여부를 검사하는 함수로 가장 빠른 정렬 알고리즘 기준으로 시간복잡도는 O(NlogN)이고 퀵 정렬의 경우 공간복잡도가 O(logN)이다. 시간과 공간 모두의 효율성을 고려해야 할때 좋은 선택지가 될 수 있다.

• 재귀에 숨겨진 비용

  //재귀를 사용하여 n부터 0까지 출력하는 함수
  function resurse(n) {
    if (n < 0) return;
    
    console.log(n);
    recurse(n - 1)
  }

  //루프를 사용하여 n부터 0까지 출력하는 함수
  function loop(n) {
    while (n >= 0) {
      console.log(n);
      n--
    }
  }

  • 재귀를 사용한 함수는 새 자료 구조를 생성하지 않으니 공간복잡도 O(1)이라고 생각할 수 있으나 재귀는 자신을 호출할 때마다 호출 스택에 항목을 추가하므로 O(N)의 공간복잡도를 가지며, 실제로 약 15,000번 이상 재귀를 실행할 경우
    RangeError: Maximum call stack size exceeded 라는 메세지가 출력된다.
  • 이에 반해 루프를 사용한 함수는 추가로 공간을 차지하지 않고 정상적으로 실행되며, 퀵 정렬이 O(logN)의 공간복잡도를 가지는 이유는 재귀 호출이 logN번 되기 때문이다.

20장 코드 최적화 기법

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

  • 상상할 수 있는 최상의 빅오란 최상의 시나리오의 빅오를 말하며 배열의 각 항목을 출력할 때 최상의 빅오는 O(N)이다.
  • 알고리즘을 최적화하기 위해서는 현재의 빅오를 알고 작업에 걸릴 상상할 수 있는 최상의 빅오를 찾아야 한다.

  authors = [
    {"author_id" => 1, "name" => "Virginia Woolf"},
    {"author_id" => 2, "name" => "Leo Tolstoy"},
    {"author_id" => 3, "name" => "Dr. Seuss"},
    {"author_id" => 4, "name" => "J. K. Rowling"},
    {"author_id" => 5, "name" => "Mark Twain"},
  ]

  books = [
    {"author_id" => 3, "title" => "Hop on Pop"},
    {"author_id" => 1, "title" => "Mrs. Dalloway"},
    {"author_id" => 4, "title" => "Harry Potter and the Sorcerer's Stone"},
    {"author_id" => 2, "title" => "Anna Karenina"},
    {"author_id" => 5, "title" => "The Advantures of Tom Sawyer"},
    {"author_id" => 3, "title" => "The Cat in the Hat"},
    {"author_id" => 2, "title" => "War And Peace"},
    {"author_id" => 3, "title" => "Green Eggs and Ham"},
    {"author_id" => 5, "title" => "The Adventures of Huckleberry Finn"},
  ]

  def connect_books_with_authors(books, authors)
    books_with_authors = []
    
    books.each do |author|
      authors.each do |author|
        if book["author_id"] == author["author_id"]
          books_with_authors <<
            {title: book["title"]
            author: author["name"]}
          end
        end
      end
      
    return books_with_authors
  end

  • 저자의 이름과 ID를 포함하는 해시 테이블로 이루어진 배열과 저자 ID와 책 제목을 포함하는 해시 테이블로 이루어진 배열을 합쳐서 저자 이름과 책 제목을 포함하는새로운 해시테이블로 이루어진 배열을 생성할 때 시간 복잡도는 O(N × M)을 가진다.

• 자료 구조 추가하기

  author_hash_table =
  {1 => "Virginia Woolf", 2 => "Leo Tolstoy", 3 => "Dr. Seuss",
  4 => "J. K. Rowling" 5 => "Mark Twain"}

  • 각 키를 저자 ID로 하고 각 키의 값을 저자 이름으로 하면 O(1)로 저자의 이름을 찾을 수 있기 때문에 시간복잡도가 O(N + M)으로 크게 개선된다.

• 두 수의 합 문제

  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;
  }

  • 숫자 배열을 입력받아 합해서 10이 되는 두 수가 있는지 여부를 리턴하는 함수는 O(N2)의 시간 복잡도를 가진다.
  • [2, 0, 4, 1, 7, 9]의 배열을 순회할때 첫번째 숫자인 2부터 루프가 시작되는데 이 배열 어딘가에 8이 있는지를 알면 O(1)만에 룩업할 수 있고 8을 2의 보수라고 부르기로 한다.

  {2: true, 0: true, 4: true, 1: true, 7: true, 9: true,}

  배열을 해시 테이블로 바꾼다면 보수를 O(1)만에 찾을 수 있게 되고 시간복잡도가 O(N)으로 크게 개선된다.

• 패턴 인식

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

  • 동전 게임

    def game_winner(number_of_coins, current_player="you")
      if number_of_coins <= 0
        return current_player
      end
    
      if current_player == "you"
        next_player = "them"
      elsif current_player == "them"
        next_player = "you"
      end
      if game_winner(number_of_coins - 1, next_player) == current_player ||
        game_winner(number_of_coins - 2, next_player) == current_player
        return current_player
      else
        return next_player
      end
    end

    • 두명의 플레이어가 동전 더미에서 차례대로 동전을 하나 혹은 두개를 없애고 마지막 동전을 없애는 플레이어가 지는 게임을 한다고 하자.
    • 동전 더비에 놓인 동전 개수가 주어졌을 때 게임에서 이길 수 있는지 계산하는 함수를 작성하려면 하위 문제를 사용함으로써 동전 게임에서 이길 수 있는 시나리오를 계산할 수 있다.
    • 위 함수의 시간 복잡도는 O(2N)이고 메모이제이션 기법을 사용한다면 처음 동전 더미의 동전 개수를 N이라고 할때 속도를 O(N)으로 개선할 수 있다.

  • 예제 생성

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

    동전이 1개 ~ 10개일때의 승자를 나열했을 때 동전 1개에서 시작해 2번에 걸러 1번씩 상대방이 이기는 걸 알 수 있다.

    def game_winner(number_of_coins)
      if (number_of_coins - 1) % 3 == 0
        return "them"
      else
        return "you"
      end
    end

    • 즉 각 "them"은 동전 개수에서 1을 뺐을 때 3으로 나눠지는 수이고 수학 연산 하나만 사용하는 알고리즘이므로 시간과 공간 관점에서 모두 O(1)의 시간복잡도를 가진다.

  • 합 교환(sum swap) 문제

    array_1 = [5, 3, 2, 9, 1] # 합계: 20
    array_2 = [1, 12, 5] # 합계: 18
    # array_1의 인덱스 2와 array_2의 인덱스 0을 교환하면 합이 19로 같아진다.

    • 두 숫자 배열의 각 합이 같아지도록 서로 교환할 수 있는 두 배열의 인덱스([2, 0])를 리턴하는 함수가 있다고 할때 중첩 루프를 통해 O(N × M)의 시간복잡도를 가진 알고리즘을 도출할 수 있다.

    • 두 배열의 모든 숫자를 무조건 최소 한 번씩은 방문해야 하므로 최선의 빅오를 O(N + M)으로 정하고 목표로 삼자.

    • 여러 예시를 살펴보면 아래와 같은 패턴이 도출된다.

      1. 합이 같아지려면 더 큰 배열에 있는 더 큰수와 더 작은 배열에 있는 더 작은 수를 교환해야 한다.
      2. 한번 교환할 때 각 배열의 합이 같은 양만큼 바뀐다. 예를 들어 7과 4를 교환하면 한 배열의 합은 3만큼 작아지고 나머지 배열의 합은 3만큼 커진다.
      3. 교환 후에 각 배열의 합이 항상 두 배열 합 사이 딱 중간에 떨어진다.

    • 합계가 각 18, 12인 배열이 있다면 교환시 각 배열의 합은 15가 되어야 하고 첫번째 배열은 3이 작아지고 두번째 배열은 3이 커져야 한다. 첫번째 배열이 [5, 3, 3, 7] 일때 첫번째 루프에서 5와 두번째 배열의 2를 교환해야 한다.

    • 위 패턴대로 각 배열을 합을 통해 각 숫자의 보수를 바로 알 수 있다.

    def sum_swap(array_1, array_2)
      hash_table = {}
      sum_1 = 0
      sum_2 = 0
      array_1.each_with_index do |num, index|
        sum_1 += num
        hash_table[num] = index
      end
    
      array_2.each do |num|
        sum_2 += num
      end
    
      shift_amount = (sum_1 - sum_2) / 2
    
      array_2.each_with_index do |num, index|
        if hash_table[num + shift_amount]
          return [hash_table[num + shift_amount], index]
        end
      end
    
      return nill
    end

    • 위 알고리즘은 array_1의 숫자 N개를 전부 해시 테이블로 복사하므로O(N) 공간을 추가로 소모하지만 시간복잡도가 O(N + M)으로 개선되었다.(array_2를 두 번 순회하므로 2M이지만 상수는 무시한다.)

• 탐욕 알고리즘

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

  • 배열 최댓값

    function max(array) {
      let greatestNumberSoFar = array[0];
    
      for(let i = 0; i < array.length; i++) {
        if(array[i] > greatestNumberSoFar) {
          greatestNumberSoFar = array[i];
        }
      }
    
      return greatestNumberSoFar;
    }

    • 배열에서 최댓값을 구하는 함수로 첫 줄을 보면 배열의 첫 번째 수를 가장 큰 숫자로 가정한 이후 배열을 순회하면서 값을 비교하므로 O(N)의 시간복잡도를 가진다.
    • 위 처럼 탐욕 알고리즘은 그 순간에 이용할 수 있는 정보를 바탕으로 최선처럼 보이는 방법을 찾는다.

  • 최대 부분 합

    [3, -4, 4, -3, 5, -9]

    • 배열 내에 연속된 부분의 최대 합을 찾는 문제에서 탐욕 알고리즘을 적용할 수 있다.
    • 배열의 첫번째 인자부터 최대 합의 시작이라고 가정하다가 합이 0보다 작아지는 경우에는 해당 인자를 제외하고 다음 배열부터를 최대 부분 합이라고 가정한다.

    //부트캠프에서 구현했던 탐욕 알고리즘을 적용한 최대 부분 합 문제
    const LSCS = function (arr) {
      let subArrSum = 0;
      let max = Number.MIN_SAFE_INTEGER;
      for (let i = 0; i < arr.length; i++) {
        subArrSum = subArrSum + arr[i];
        if (subArrSum > max) max = subArrSum;
    
        if (subArrSum < 0) {
          subArrSum = 0;
        }
      }
    
      return max;
    };

  • 탐욕스러운 주가 예측
    [22, 25, 21, 18, 19.6, 17, 16, 20.5]

    • 주식의 주가 변화를 나태내는 배열에서 주가 3개가 순차적으로 커지는 지를 알아내는 함수를 작성한다고 하자. (위 배열에서는 18, 19.6, 20.5가 순차적으로 커지는 주가 3개이다.)
    • 중첩 루프를 이용하면 3번 중첩하여 배열을 순회해야 하므로 O(N3)의 시간 복잡도를 가지지만 탐욕 알고리즘을 활용하면 O(N)의 속도로 최적화할 수 있다.
      1. 현재 주가가 지금까지의 최저가보다 작으면 현재 주가가 새로운 최저가가 된다.
      2. 현재 주주가가 최저가보다 크지만 중간 주가 보다 작으면 중간 주가를 현재 주가로 업데이트한다.
      3. 현재 주가가 최저가와 중간 주가보다 크면 상승세를 이루는 주가 3개를 찾았다는 뜻이다.

    def increasing_triplet?(array)
      lowest_price = array[0]
      middle_price - Float::INFINITY
      array.each do |price|
        if price <= lowest_price
          lowest_price = price
        
        elsif price <= middle_price
          middle_price = price
          
        else
          return true
        end
      end

    • 중간 주가 이후에 기존 저가 보다 더 낮은 주가가 나오는 경우 주가 순차적이지 않은 주가가 최저가로 할당되지만 상승세 3개가 있는지 여부를 올바르게 리턴한다.

• 자료 구조 변경

  • 애너그램 검사기

    • 두 문자열이 주어졌을 때 서로 애너그램인지 알아내는 함수에서 첫 번째 문자열의 모든 애너그램을 생성한 후 두 번째 문자열이 그중 하나와 같은지 확인할 경우 시간복잡도 O(N!)이 걸린다.

    • 두 문자열의 각 문자를 최소 한번 씩은 방문해야 하므로 최상의 빅오를 O(N + M)으로 가정하고 효율적인 알고리즘을 찾아보자.

    • 중첩루프를 사용하여 첫 번째 문자열을 순회하면서 두 번째 문자열에서 그 문자를 삭제하고 루프가 종료되었을때 두 번째 문자열의 문자가 모두 삭제되어 있는지 확인하는 알고리즘은 O(N × M)의 단계를 가지며, 배열을 순회하면서 그 배열의 항목을 삭제하는 오류가 발생할 수 있다.

    • 두 문자열을 정렬하며 두 문자열이 완전히 같은지를 검사하는 알고리즘은 O(NlogN + MlogM)이다.

    • 각 문자를 키로 가지고 개수를 값으로 가지는 해시 테이블을 생성하여 같은지 여부를 리턴하는 함수의 경우 목표로 삼았던 시간복잡도 O(N +M)을 가진다. (자바스크립트 같은 언어에서는 순회하면서 비교를 해야하므로 2(N +M)의 단계를 가지지만 상수를 제외하면 여전히 O(N +M)이다.)

    def areAnagrams(firstString, secondSrting):
      firstWordHashTable = {}
      secondWordHashTable = {}
      
      for char in firstString:
        if firstWordHashTable.get(char):
          firstWordHashTable[char] += 1
        else:
          firstWordHashTable[char] = 1
          
      for char in secondSrting:
        if firstWordHashTable.get(char):
          secondWordHashTable[char] += 1
        else:
          secondWordHashTable[char] = 1
          
      return firstWordHashTable = secondWordHashTable

  • 그룹 정렬

    ["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(NlogN)이지만, 해시 테이블의 자료구조로 변경하면 O(N)으로 개선할 수 있다.

    def group_array(array)
      hash_table = {}
      new_array=[]
      
      array.each do |value|
        if hash_hash[value]
          hash_table[value] += 1
        else
          hash_table[value] = 1
        end
      end
      
      hash_table.each do |key, count|
        count.times do
          new_array << key
        end
      end
      
      return new_array
    end

마치며

이번 포스팅을 끝으로 이 책의 챕터를 모두 마치게 되었다. 책의 제목인 누구나 자료구조와 알고리즘 처럼 깊이 있는 내용이라기 보다는 어떤 자료구조와 알고리즘이 있는지 어떤 장점을 가지고 있고 효율성은 어떻게 분석하는지 등 기초적인 내용을 다루고 있어서 ruby, python 등 접하지 못한 언어로 작성된 코드들이 있음에도 어렵지 않게 이해할 수 있었다.

자료구조와 알고리즘에 대해 처음 접하는 사람들에게는 입문 도서로 좋다고 생각하고 나처럼 비전공 개발자이면서 부트캠프처럼 빠른 기간에 CS 지식을 습득한 사람이라면 복습과 기초를 다지기 위해서 읽어보는 것도 도움이 된다고 생각한다.

책에서 가장 도움이 되었던 부분은 알고리즘을 개선하기 위한 여러가지 예시들과 공간복잡도라는 새로운 개념들이 실무에 자료구조와 알고리즘을 어떻게 적용할 수 있는지 이해하는데 도움이 되었다.