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

안광의·2022년 5월 14일

알고리즘 자료구조

자료구조와 알고리즘

목록 보기

3/7

8장 해시 테이블로 매우 빠른 룩업

해시 테이블
- 해시 테이블은 키(key), 값(value)이 쌍으로 이루어진 값들의 리스트로 조회할때 딱 한단계만 걸리므로 효율성이 O(1)이다.
해시 함수로 해싱
- 문자를 가져와 숫자로 변환하는 과정을 해싱(hashing)이라고 부르며 글자를 특정 숫자로 변환하는데 사용한 코드를 해시 함수라 부른다.
- 해시 함수는 동일한 문자열을 해시 함수에 적용할 때마다 항상 동일한 숫자로 변환해야 한다.
```
//Quickasaurus
//단어를 입력하면 유의어 하나를 반환하는 함수를 구현한다고 하자.
//배열과 유사하게 해시 테이블은 내부적으로 데이터를 한 줄로 이루어진 셀 묶음에 저장한다.

thesaurus = {}
thesaurus['bad'] = 'evil' //이 항목을 해시 테이블에 저장하려고 할때
BAD = 2 * 1 * 4 = 8 //해시 함수는 bad라는 글자를 정해진 규칙에 의해 해싱하여 인덱스 값을 구한다.
셀 8에 'evil'이라는 글자가 저장되고, 이제 'bad'라는 글자가 입력되었을때 해싱 과정을 거쳐 바로 'evil'이라는 글자를 구할 수 있다.
```
- 해시 테이블에서 한 단계만에 값을 찾는 기능은 그 값의 키를 알 때만 가능하며, 반대로 값을 이용해 연관된 키를 찾을 때는 빠른 룩업 기능을 활용할 수 없다.
- 각 키는 해시 테이블에 딱 하나만 존재 할 수 있기 때문에 대부분의 언어는 이미 존재하는 키에 값을 저장하려면 키는 그대로 두고 기존 값만 덮어쓴다.
충돌 해결
```
thesaurus['dab'] = 'pat'  //이와 같은 키/값을 해시 테이블에 저장하려고 할때
DAB = 4 * 1 * 2 = 8 //이미 입력된 키/값('bad' : 'evil')과 충돌하는 문제가 발생한다.
```
- 충돌을 해결하는 고전적인 방법 중 셀에 하나의 키/값이 아닌 배열의 참조를 넣는 방법인 분리 연결법이 있다.
- 그러나 최악의 경우 해시 테이블의 한 셀에 모든 데이터가 들어가게 된다면, 시간복잡도는 O(N)이 된다.
효율적인 해시 테이블 만들기
- 궁극적으로 해시 테이블은 다음 세 요인에 따라 효율성이 정해진다.
  - 해시 테이블에 얼마나 많은 데이터를 저장하는가
  - 해시 테이블에서 얼마나 많은 셀을 쓸 수 있는가
  - 어떤 해시 함수를 사용하는가
- 만약 항상 1~9 사이의 값만 반환하는 해시 함수를 사용한다면, 모든 데이터는 1~9의 셀에만 저장되기 때문에 효율성이 떨어진다. 따라서 좋은 해시 함수란 사용 가능한 모든 셀에 데이터를 분산시키는 함수 이다.
- 이론상 충돌을 피하는 방법은 해시 테이블에 많은 셀을 두는 것이지만 5개의 항목만 저장하고 싶을 때 셀 1000개를 사용하는 것은 메모리 낭비이다.
- 데이터와 셀 간의 비율을 부하율(load factor)이라고 하며 컴퓨터 언어는 해시 테이블이 얼마나 커야 하는지, 언제 해시 테이블을 확장할지를 결정한다.

해시 테이블로 속도 올리기

해시 테이블은 쌍으로 된 데이터와 완벽하게 들어 맞지만 쌍이 아닌 데이터라도 코드르 빠르게 만들때 쓰일 수 있다.

const array = [61, 30, 91, 11]
//위 배열에서 어떤 수를 찾으려면 N단계가 걸리지만
const object = {
  61: true,
  30: true,
  91: true,
  11: true,
}
//위 와 같은 해시 테이블에서는 한단계가 걸린다.

//두 배열의 입력받아 중첩 루프를 통해 부분 집합인지 여부를 리턴하는 함수
function isSubset(array1, array2) {
  let largerArray;
  let smallerArray;

  if(array1.length > array2.length) {
    largerArray = array1;
    smallerArray = array2;
  } else {
    largerArray = array2;
    smallerArray = array1;
  }

  for(let i = 0; i < smallerArray.length; i++) {
    let foundMatch = false;
    for(let j = 0; j < largerArray.length; j++) {
      if(smallerArray[i] === largerArray[j]) {
        foundMatch = true;
        break;
      }
    }
    if(foundMatch === false) { return false; }
  }
  return true;
}

//해시 테이블을 사용하여 한 배열이 다른 배열의 부분 집합인지 여부를 반환하는 함수
function isSubset(array1, array2) {
  let largerArray;
  let smallerArray;
  let hashTable = {};

  if(array1.length > array2.length) {
    largerArray = array1;
    smallerArray = array2;
  } else {
    largerArray = array2;
    smallerArray = array1;
  }
  for(const value of largerArray) {
    hashTable[value] = true;
  }
  for(const value of smallerArray) {
    if(!hashTable[value]) { return false; }
  }
  return true;
}

위 예시에서 배열들의 루프를 사용해서 부분 집합 여부를 리턴하는 함수는 N * M 단계가 걸리지만 해시 테이블을 활용하면 N단계가 걸린다.

9장 스택과 큐로 간결한 코드 생성

스택(Stack)

스택은 데이터를 끝에만 삽입하고 삭제할 수 있는 LIFO(Last In, First Out)의 자료구조로, 가장 나중에 들어온 데이터가 가장 먼저 나간다.

스택은 구현하는데 어떤 데이터 구조를 쓰든 개의치 않고, 작동하는 규칙 집합으로 이루어진 추상 데이터 타입이다.

//부트캠프에서 풀었던 스택을 활용한 코딩 문제
function balancedBrackets (str) {
  const compareArr = '(){}[]';
  if(str === '') return true;
  if(str.length % 2 !== 0) return false;

  const storage = [];

  for(let i = 0; i < str.length; i++) {
    let compareIdx = compareArr.indexOf(str[i])  
    if(compareIdx % 2 === 0) { 
      storage.unshift(compareIdx + 1) 
    } else {
      if(storage.shift() !== compareIdx) return false
    }
  }
  return true;
};

가장 나중에 열린 괄호가 가장 먼저 닫혀야 하는 스택과 같은 특성을 활용하여 올바른 괄호인지 검사하는 함수에 활용할 수 있다.

큐(Queue)

큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 FIFO(First In, First Out) 구조의 자료구조이다.

//부트캠프에서 큐를 활용해 풀었던 인쇄 작업 목록의 최대 용량이 정해져 있는 프린트의 최소 인쇄 시간을 리턴하는 문제
function queuePrinter(bufferSize, capacities, documents) {
  let time = 0;   
  let buffer = Array(bufferSize).fill(0);

  let volum = 0;

  let current = documents.shift(); 

  buffer.push(current); 
  buffer.shift();  

  volum += current; 
  time++; 
  while(volum){

    volum -= buffer.shift();   
    current = documents.shift(); 
    if(current+volum <= capacities){
      buffer.push(current);   
      volum += current;   
    }
    else {
      buffer.push(0);       
      documents.unshift(current); 
    }
    time++;                      
  }
  return time;                
}

10장 재귀를 사용한 재귀적 반복

재귀
- 재귀는 함수가 자기 자신을 호출할 때를 뜻하는 용어로 재귀를 올바르게 사용하면 까다로운 문제 유형을 놀랍도록 간단하게 풀 수 있다.
```
//루프를 사용하여 number부터 0까지 숫자를 출력하는 함수
function countdown(number) {
  for(let i=number; i>=0; i++) {
    console.log(i)
  }
}
//재귀를 사용하여 10부터 0
function countdown(number) {
  console.log(number);

  if(number === 0) {
    return;
  } else {
    countdown(number - 1);
  }
}
```
  루프를 사용할 수 있느 경우라면 대부분 재귀를 사용할 수 있다.
- if(number === 0)처럼 함수가 무한히 반복되지 않는 조건을 기저조건(base case)이라고 하며 모든 재귀함수는 기저 조건이 적어도 하나가 있어야 한다.
호출 스택
- 컴퓨터는 재귀 함수를 실행할 때 하나의 함수가 종료되기 전에 다음 함수가 실행되는 과정을 호출 스택에 기록한다. 가장 나중에 실행된 함수가 가장 먼저 값을 리턴하고 이 값이 호출 스택을 통해 부모 함수에 반환되면 서 최종 값을 리턴한다.
```
//다차원 배열을 입력받아 1차원 배열로 변환하여 리턴하는 함수
function flattenArr(arr) {
  if(arr.length === 0) return []
  if(Array.isArray(arr[0])) return flattenArr([...arr[0],...arr.slice(1)]);
  return [arr[0],...flattenArr(arr.slice(1))];
}
```
- 재귀 함수를 사용하면 다차원 배열처럼 깊이를 모르는 자료구조에 접근할 수 있다.

마치며

대표적인 자료구조들과 재귀에 대해서 공부하고 예전에 풀었던 코딩 문제들을 다시 살펴보면서 공부했던 내용을 복습할 수 있었다. 자료구조와 알고리즘에 대한 개념적인 이해도 중요하지만 결국 어떻게 현업이나 프로젝트에서 활용할 수 있는가에 대한 부분이 중요하다는 생각이 들었다. 부트캠프를 진행한 이후에는 코딩 문제를 놓았었기 때문에 감을 잃지 않기 위해 꾸준하게 코딩 테스트 문제를 풀어야겠다는 생각이 든다.

안광의

개발자로 성장하기

이전 포스트

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

다음 포스트