공간 복잡도를 이용한 시간 복잡도 줄이기

공간 복잡도를 이용한 시간 복잡도 줄이기

• 많은 메모리를 희생하면 답을 더 빨리 구할 수 있음.
  하지만, 대부분의 문제에서는 가능한 모든 입력이 거의 무한하게 많아 미리 답을 계산 할 수 없고, 답을 저장할 공간도 부족함.
• 현실적으로 가능한 수준에서 공간을 희생해서 시간 복잡도를 줄이는 방법을 선택해야 함.

기수 정렬

• 기수 정렬의 아이디어
• 이전까지의 정렬 방법들은 비교 기반의 정렬 방법들이었다면, 분배 방식의 정렬들은 메모리 공간에 나누어 저장하는 방식이다.
• 분배 방식의 정렬에는 기수 정렬과 카운팅 정렬이 있다.
• 기수 정렬은 숫자의 자릿수를 의미하는데 자릿수의 값에 따라서 정렬하기 떄문에 기수 정렬이라는 이름을 얻음.
• 기수 정렬은 다단계 정렬인데, 단계의 수는 데이터의 전체 자릿수와 일치함.
• 기수 정렬 방법
1. 항목들을 저장할 버킷들을 준비한다.
2. 입력 항목들을 순서대로 킷값에 따라 해당 버킷에 넣는다.
3. 위쪽 버킷부터 순차적으로 버킷 안에 들어 있는 숫자를 출력한다.
• 공간이 무한하게 많다면 자릿수만큼 공간을 늘리면 좋지만, 현실적으로 그럴 수 없기때문에 메모리를 아껴야 한다.
• 여러 자리 숫자의 기수 정렬에서는 먼저 낮은 자릿수로 정렬한 다음 차츰 높은 자릿수로 정렬해야 함.
• 버킷에 여러 개의 숫자가 들어 있다면 먼저 들어간 숫자가 먼저 나와야 한다. 그래야 이미 정렬한 자릿수에 의한 숫자들의 상대적인 수넛가 계속 유지되기 때문이다. 따라서 버킷은 큐(Queue)로 구현되어야 한다.
• Python code

  import random
  from queue import Queue
  
  BUCKETS = 10    #10진법으로 정렬
  DIGITS = 4      #최대 자릿수
  data = []
  
  def radix_sort(A):
      queues = []
      for i in range(BUCKETS):
          queues.append(Queue())
      n = len(A)
      factor = 1
      for d in range(DIGITS):
          for d in range(n):
              queues[(A[i]//factor) % 10].put(A[i])
          j = 0
          for b in range(BUCKETS):
              while not queues[b].empty():
                  A[j] = queues[b].get()
                  j += 1
          factor *= 10
          print("step", d+1, A)
  
  for i in range(10):
      data.append(random.randint(1,9999))
  radix_sort(data)
  print("Radix: ", data)

• 복잡도 분석
• 시간 복잡도와 공간 복잡도 모두 O(n)이다.
• 단점
• 정렬에 사용되는 킷값이 자연수로 표현되어야만 적용할 수 있다. 음수를 포함한 정수인 경우, 양수와 음수를 분리하는 방법으로 정렬할 수 있다.
• 실수나 한글, 한자등으로 이루어진 킷값에 대해서는 가능하긴하지만 비현실적으로 많은 버킷이 필요함.

카운팅 정렬(Counting Sort)

• 카운팅 정렬의 아이디어
• 리스트를 한번 스캔하면서 각 항목이 리스트에 몇번 나타났는지 빈도수를 계산한다. 빈도수가 구해지면 가장 작은 항목부터 순서대로 빈도수만큼 나열한다.
• 카운팅 정렬을 적용하기에 가장 좋은 입력은 나타날 수 있는 킷값이 일정한 개수로 제한되는 경우이다.
• Python code

  MAX_VAL = 10
  data = [1, 4, 1, 2, 7, 5, 2]
  
  def counting_sort(A):
      output = [0] * len(A)
      count = [0] * MAX_VAL
  
      for i in A:
          count[i] += 1
  
      for i in range(MAX_VAL):
          count[i] += count[i-1]
  
      for i in range(len(A)):
          output[count[A[i]]-1] = A[i]
          count[A[i]] -= 1
  
      for i in range(len(A)):
          A[i] = output[i]
  
  print("Original : ", data)
  counting_sort(data)
  print("Counting : ", data)

• 복잡도 분석
• 입력 데이터가 크지 않은 일정한 범위의 값을 가진 정수라면 매우 효율적임.
• 입력의 크기가 n이고, 숫자의 범위가 k가지(0~k-1)라면 전체 알고리즘은 O(k+n)의 시간 복잡도를 갖는다.
• 입력 리스트에 추가적으로 O(k+n)의 메모리 공간을 필요로 한다.

문자열 매칭

• 문자열 매칭의 아이디어
• 길이가 n인 텍스트 문자열에서 길이가 m인 패턴 문자열을 찾는 문제
• 전처리 과정을 통해 패턴에 대한 정보를 얻고 이것을 테이블에 저장한 다음 텍스트에서 패턴을 매칭하는 동안 이 정보를 활용한다.
• 문자열 매칭의 대표적인 알고리즘은 KMP(Knuth-Morris-Pratt)와 보이어 무어(Boyer-Moore)가 있는데, 보이어 무어 알고리즘이 더 유리한 것으로 알려져 있음.
• 호스풀(Horspool) 알고리즘
• 보이어 무어 알고리즘의 단순한 형태
• 억지 기법과는 달리 경험적인 전략(휴리스틱)을 이용함.
• 하나의 위치(Shift)에서 패턴은 뒤에서부터 앞으로 검사함.
  BANANA와 APLLEM이 있을 때, BANANA를 APPLEM 순으로 비교하는 것이 아니라 ANANAB 순으로 MELPPA와 비교한다. 가능한 많은 위치를 검사하지 않고 뛰어넘기 위한 전략
• 휴리스틱 전략을 사용하려면 추가적인 공간을 이용해 모든 가능한 알파벳에 대해 패턴에서의 위치를 저장한 표(Shift Table)를 미리 만들어 두는 전처리 과정(preprocessing)이 필요하다.
• Python code

  NO_OF_CHARS = 128
  
  def shift_table(pat):
      m = len(pat)
      tbl = [m]*NO_OF_CHARS
  
      for i in range(m-1):
          tbl[ord(pat[i])] = m-1-i
  
      return tbl
  
  def search_horspool(T,P):
      m = len(P)
      n = len(T)
      t = shift_table(P)
      i = m-1
      while(i <= n-1):
          k = 0
          while k <= m-1 and P[m-1-k]==T[i-k]:
              k += 1
          if k == m :
              return i - m + 1
          else:
              i += t[ord(T[i])]
      return -1
  
  print("패턴의 위치 :", search_horspool("APPLEMANGOBANANAGRAPE", "BANANA"))

• 복잡도 분석
• 최악의 경우 시간 복잡도는 O(mn)
• 평균적인 경우 시간 복잡도는 O(n)
• 보이어 무어(Boyer-Moore) 알고리즘
• 호스풀 알고리즘에 추가적인 휴리스틱을 더해 효율을 높인 방법
• 호스풀 알고리즘이 하나의 휴리스틱을 사용한 것과 달리 보이어-무어 알고리즘은 두 가지 휴리스틱(나쁜 심벌 휴리스틱(Bad Symbol Heuristic), 좋은 접미어 휴리스틱(Good Suffix Heuristic))을 사용해 패턴의 이동량을 계산함.
• 각 휴리스틱을 이용하여 표를 만들고 이를 이용해 나쁜 심벌 이동량 d1과 좋은 접미어 이동량 d2를 각각 계산하고, 이 중에서 더 큰 양만큼 이동하는 것
• 나쁜 심벌 휴리스틱
• 호스풀 알고리즘에서와 동일한 역할
• k개의 문자가 일치한 다음 처음으로 불일치가 발생한 문자를 c라 할때, c가 패턴에 없다면 패턴의 시작이 이 문자 다음에 위치하도록 바로 옮긴다.
• 좋은 접미어 휴리스틱
• 일치된 부분의 전체 또는 일부가 패턴의 다른 부분에도 나타날 경우 이를 좋은 접미어(Good Suffix)라고 함.
• 좋은 접미어가 발견되면 이것을 텍스트의 접미어 부분과 일치되도록 패턴을 바로 옮길 수 있다. 즉, 한꺼번에 여러 칸을 뛰어넘을 수 있는 좋은 정보를 제공한다.
• 복잡도 분석
• 두 종류의 휴리스틱을 사용하고, 표를 만들기가 까다롭지만 최악의 입력에 대해서도 선형 시간이 걸리는 것으로 알려져 있음.
• 이론적으로 이 알고리즘이 더 빠르지만, 자연어와 같은 문자열에 대해서 단순한 버전인 호스풀 알고리즘이 더 자주 사용된다.
• 보이어 무어 알고리즘

해싱

• 공간을 이용해 시간 효율성을 높이려는 전략의 가장 대표적인 예
• 탐색키로부터 레코드가 있어야 할 위치를 바로 계산하고, 그 위치에 레코드가 있는지만 확인하면 됨.
• Hashing에서 Key Value로부터 레코드가 저장 될 위치를 계산하는 함수를 해싱 함수(Hash Function)이라고 함.
• 해시 함수에 의해 계산된 위치에 레코드를 저장한 테이블을 해시 테이블(Hash Table)이라 한다.
• 탐색키가 문자열이거나 실수 또는 굉장히 큰 정수라면 문제가 될 수 있기때문에 작은 정수로 대응 시키는 해시 함수가 필요함. 해시 함수는 탐색키를 입력 받아 해시 주소(Hash Address)를 계산하는데, 삽입이나 삭제, 탐색 연산은 모두 이 주소에서 이루어진다.
• 해시 테이블
• 해시 테이블은 M개의 버킷(BUCKET)으로 이루어지는 테이블
• 하나의 버킷은 여러 개의 슬롯(Slot)을 가지는데, 하나의 슬롯에는 하나의 레코드가 저장됨.
• 버킷이 충분하지 않으면 서로 다른 키가 해시 함수에 의해 같은 주소로 계산되는 상황이 발생하는데 이를 충돌(Collision)이라고 하고 충돌을 일으키는 키들을 동의어(Synonym)이라고 함
• 어떤 버킷에 슬롯 수보다 많은 충돌이 발생하면 그 버킷에 더 이상 항목들을 저장할 수 없게 되는 상황이 발생하는데, 이를 오버플로(Overflow)라고 함. 해싱에서는 오버플로 문제를 반드시 해결해야 함.
• 이상적인 해싱은 충돌이 절대 일어나지 않는 경우인데, 해시 테이블의 크기를 충분히 늘리면 가능하겠지만 메모리가 지나치게 많이 필요하게 됨.
• 실제의 해싱에서는 테이블의 크기를 적절히 줄이고, 해시 함수를 이용해 탐색키의 주소가 한쪽에 몰리지 않고 가능한 전체 테이블에 골고루 배분될 수 있도록 해야 함.
• 선형 조사에 의한 오버 플로 처리
• 해시 함수로 계산된 버킷에 빈 슬롯이 없으면 그 다음 버킷들을 순서적으로 조사하여 빈 슬롯이 있는지 찾는다. 이떄 비어 있는 공간을 찾는 것을 조사(Probing)라고 한다.
• 만약 테이블의 끝에 도달하면 테이블의 처음으로 돌아가고 처음 충돌한 곳까지 다시 오게 되면 테이블이 가득 찬 상태다.
• 삽입 연산
• 선형 조사법은 한번 충돌이 발생한 위치에서 연속적인 충돌이 집중되는 현상인 군집화(Clustering)이 발생한다.
• 선형 조사법은 간단하지만 오버플로가 자주 발생하면 군집화 현상에 따라 탐색의 효율이 크게 저하될 수 있다.
• Python code

  M = 13
  table =  [none]*M
  def hashFn(key) :
      return key % M
  
  def lp_insert(key) :
      id = hashFn(key)
      count = M
      while count > 0 and  (table[id] != None and table[id] != -1) :
          id = (id + 1 + M) % M
          count -= 1
      if count > 0 : 
          table[id] = key
      return

• 탐색 연산
• =탐색 키가 입력되면 해시주소를 계산하고, 해당주소에 같은 키의 레코드가 있으면 탐색 성공
• 해당 키의 레코드를 찾거나, 레코드가 없는 버킷을 만나거나 모든 버킷을 다 검사 할 때까지 탐색이 진행됨.
• Python code

  def lp_search(key) : 
  id = hashFn(key)
  count = M
  while count > 0 :
      if table[id] == None : 
          return None
      if table[id]t != -1 and able[id] == key : 
          return table[id]
      id = (id + 1 + M) % M
      count -= 1
  return None

• 삭제 연산
• 선형 조사법에서 항목이 삭제되면 탐색이 불가능해질 수 있기 때문에 빈 버킷을 한 번도 사용하지 않은 것과 사용되었다가 삭제되어 현재 비어있는 버킷으로 구분해야 함.
• 탐색 과정은 한 번도 사용이 안 된 버킷을 만나야만 중단 되도록 한다.
• Python code

  def lp_search(key) : 
  id = hashFn(key)
  count = M
  
  while count > 0 :
      if table[id] == None : 
          return
      if table[id] != -1 and table[id] == key : 
          table[id] = -1 # -1로 처리 된 것은 사용되었다가 삭제된 버킷을 의미함.
          return
      id = (id + 1 + M) % M
      count -= 1

• 이차 조사법(Quadratic Probing)
• 이중 해싱법(Double Hashing)
• 재해싱(Rehasing)이라고도 불리며 충돌이 발생해 저장할 다음 위치를 결정할 때, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법
• 선형조사법과 이차 조사법은 충돌이 발생하면 해시 함수 값에 각각 1 또는 j^2를 더해서 다음 위치를 얻는다.
• 이중해싱법은 해시 함수 값이 같더라도 탐색키가 다르면 서로 다른 조사 순서를 갖도록 하여 2차 집중을 완화할 수 있다.
• 체이닝(Chaining)에 의한 오버플로 처리
• 선형 조사법과 달리 하나의 버킷에 여러 개의 레코드를 저장할 수 있도록 크기를 변경할 수 있는 리스트 구조로 구현함.
  하나의 버킷에서 아무리 많은 충돌이 발생하더라도 문제 없이 처리할 수 있음.
• 항목을 탐색하거나 삽입하면 킷 값의 버킷에 해당하는 리스트에서 독립적으로 탐색이나 삽입이 이루어짐.
• 필요한 만큼의 메모리만 사용하게 되어 공간적 사용 효율이 매우 우수함.
• 오버플로가 발생할 경우에도 해당 버킷에 할당된 연결 리스트만 처리하므로 효율적임.
• 해시 함수
• 좋은 해시 함수는 충돌이 적어야하고, 주소가 해시 테이블에서 고르게 분포되어야 하며, 계산이 빨라야 함.
• 제산 함수
• 가장 일반적인 방법으로 나머지 연산 %(Modular)을 이용함.
• 테이블의 크기가 M일때 탐색 키 k에 대하여 해시함수는 h(k) = k mod M
• 이때 해시 테이블의 크기 M은 소수(Prime Number)로 선택한다. 즉, 1과 자기 자신만을 약수로 가지는 수라면 나머지 값을 골고루 만들 수 있기 때문이다.
• 폴딩 함수
• 탐색키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용
  탐색키가 32비트고 해시 테이블의 크기가 16비트
• 탐색키를 몇개의 부분으로 나누어 이를 더하거나 비트별 XOR와 같은 부울 연산을 이용하는데, 이를 폴딩(Folding)이라고 한다.
• 탐색키를 여러부분으로 나눈 값들을 더하는 이동 폴딩(Shift Folding)과 이웃한 부분을 거꾸로 더하는 경계 폴딩(Boundary Folding)이 대표적이다.
• 중간 제곱 함수
• 탐색키를 제곱한 다음, 중간의 몇 비트를 취해 해시 주소를 생성하는 방법
• 탐색키를 제곱한 값의 중간 비트들은 보통 비교적 고르게 분산 됨.
• 비트 추출 방법
• 해시 테이블의 크기가 M = 2^k 일 때 탐색 키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용하는 방법.
• 간단하지만, 탐색 키의 일부 정보만 사용하기 때문에 해시 주소의 집중 현상이 일어날 가능성이 많음.
• 숫자 분석 방법
• 숫자로 구성된 키에서 각 위치마다 수의 특징을 미리 알고 있을 때 유용함.
• 키의 각 위치에 있는 숫자 중에서 편중되지 않는 수들을 해시 테이블의 크기에 적합한 만큼 조합하여 해시 주소로 사용하는 방법
  ex)학생의 학번이 202112345라면 입학년도를 의미하는 앞의 4자릿수는 편중되므로 사용하지 않고 나머지 자리의 수들을 조합하여 해시 주소로 사용함.
• 탐색키가 문자열이 경우
• 탐색키가 문자열인 경우는 보통 각 문자에 정수를 대응시켜 바꾸게 된다.
• 가능하면 문자열아느이 모든 문자를 골고루 사용하는 것이 좋음.