📝 오늘 한 것

1. 삽입 정렬 / 평균 시나리오 / 삽입 정렬 vs 선택 정렬 / 두 배열의 교집합 구하기 / 해시 테이블 / 해시 충돌 / 분리 연결법 / 배열 내 중복 값 유무 확인(해시 테이블 이용) / 스택 / 큐

📖 학습 자료

1. 책 '누구나 자료 구조와 알고리즘'

📚 배운 것

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

📌 지금까지는 최악의 시나리오에서 얼마나 느린가에 초점을 맞췄다

📌 그러나, 대체로 일어나는 시나리오는 평균 시나리오이다

📌 모든 시나리오를 고려하는 방법을 알아보자

1) 삽입 정렬 알고리즘

💡 정렬 알고리즘 > 단순 정렬 알고리즘 > 삽입 정렬

(1) 설명

각 패스스루에서는, 임시로 삭제한 값이 배열의 왼쪽 끝에 도달하거나 자신보다 작은 값을 만날 때까지 왼쪽 값들과 비교하여, 임시로 삭제한 값보다 큰 값들이 있다면 이들을 오른쪽으로 시프트한 후, 만들어진 빈 공간에 임시로 삭제했던 값을 삽입한다.

(2) 코드 구현

p.120
Python으로 구현된 코드 → JavaScript로 수정

function insertSort (arr) {
  // 패스스루
  for (let i = 1; i < arr.length; i++) {
    let temp_value = arr[i]; // 💡 삭제
    let position = i; // 임시로 삭제한 값 temp_value를 삽입할 인덱스

    while (position > 0 && arr[position-1] > temp_value) { // 💡 비교
      arr[position] = arr[position-1]; // 💡 시프트
      position = position - 1; // temp_value를 삽입할 인덱스 기록
    }

    if (position !== i) {
      arr[position] = temp_value; // 💡 삽입
    }
  }

  return arr;
}

const arr1 = [5, 4, 3, 2];
console.log(insertSort(arr1)); // [2, 3, 4, 5]

(3) 빅 오

삽입 정렬 알고리즘에는 총 네 종류의 단계, 삭제 & 비교 & 시프트 & 삽입이 포함되어 있다.

최악의 경우를 가정하면(배열이 역순으로 정렬되어 있는 경우)

• 비교 및 시프트

  1 + 2 + 3 + ... + N - 1

  3개 3번
  4개 6번
  5개 10번
  6개 15번
  10개 45번
  20개 190번

  데이터가 N개일 때, '비교'는 대략 N² / 2 번 일어난다

  한편, 최악의 경우라면 '비교'할 때마다 '시프트'가 일어나므로
  데이터가 N개일 때, '시프트'도 대략 N² / 2 번 일어난다

  → 즉, 비교 + 시프트 = N² 단계

• 삭제 및 삽입

  각 패스스루마다 1번씩 temp_value의 삭제 및 삽입이 일어난다.
  데이터가 N개일 때, 패스스루는 항상 N - 1번을 거치므로 '삭제'도 N - 1번, 삽입도 N - 1번 일어난다.

  → 즉, 삭제 + 삽입 = 2N - 2 단계

• 비교 + 시프트 + 삭제 + 삽입

  빅 오는 상수를 무시하므로 O(N² + N)이라고 할 수 있다.

  그러나, 빅 오는 가장 높은 차수의 N만 고려한다.

  따라서, 선택 정렬 알고리즘의 효율성은 O(N²)이다.

2) 평균 시나리오

💡 버블 정렬 VS 선택 정렬 VS 삽입 정렬

3개의 알고리즘 모두, 빅 오 표기법으로는 N(O²)이다.

좀 더 자세히 살펴보면
최악의 시나리오에서 데이터가 N개일 때, 각각의 정렬의 효율성은 다음과 같다.

버블 정렬 : N² 단계
선택 정렬 : N² / 2 단계
삽입 정렬 : N² + 2N - 2 단계

이를 언뜻 보면, 선택 정렬이 가장 빠르다는 결론을 지을 수 있지만, 사실은 그렇지 않다.

(1) 삽입 정렬 vs 선택 정렬

🔎 삽입 정렬의 시나리오

• 최선의 시나리오 : 패스스루당 1번의 비교만 일어난다 (N 단계)

• 최악의 시나리오 : 모든 데이터를 비교하고 시프트한다 (N² 단계)

• 평균 시나리오 : 대체로 데이터의 반을 비교하고 시프트한다 (N² / 2 단계)

  이처럼 시나리오에 따라 차이가 나는 것은 temp_value가 왼쪽에서 자신보다 작은 값을 만나면 패스스루가 일찍 종료되기 때문이다.

🔎 선택 정렬의 시나리오

• 시나리오에 상관없이 언제나 N² / 2 단계가 걸린다.

  선택 정렬에는 어떤 시점에 패스스루를 일찍 끝낼 메커니즘이 전혀 없기 때문이다. 각 패스스루마다 무조건 선택된 인덱스의 오른쪽에 있는 모든 값들과 비교해야 한다.

🔎 그렇다면, 삽입 정렬과 선택 정렬 중 어떤 게 더 나을까?

• 경우에 따라 다르다.

  거의 정렬된 데이터를 다룬다면, 삽입 정렬이 낫다

  거의 역순으로 정렬된 데이터를 다룬다면, 선택 정렬이 낫다

  임의의 데이터를 다룬다면, 평균적인 경우이므로 효율성은 둘이 같다

(2) 두 배열의 교집합 구하기

cf. 교집합이란?
두 배열에 모두 들어 있는 모든 값들의 리스트(배열)

p.128

function intersection (firstArr, secondArr) {
  const intersection = [];
  for (let i = 0; i < firstArr.length; i++) {
    for (let j = 0; j < secondArr.length; j++) {
      if (firstArr[i] === secondArr[j]) {
        intersection.push(firstArr[i]);
      }
    }
  }
  return intersection;
}

const arr1 = [1, 2, 3, 4, 5];
const arr2 = [9, 7, 5, 3, 1];
console.log(intersection(arr1, arr2)); // [1, 3, 5]

[전제조건]

두 배열의 크기는 같다.
각 배열은 내부적으로 중복 값을 가지지 않는다.

• 효율성(빅 오)

위 교집합 알고리즘에는 두 종류의 단계, 비교 & 삽입이 포함되어 있다.

그러나, 비교 외에 (intersection 배열에의)삽입은 무시해도 좋다. 설사 두 배열이 동일하다 하더라도(삽입이 가장 많이 일어나는 경우에도) 고작 두 배열 중 하나에 들어 있는 값만큼만 삽입하기 때문이다. 빅 오는 가장 높은 차수의 N만 고려하므로 삽입은 무시해도 된다.

따라서, 비교만 고려하면, 위 교집합 알고리즘의 효율성은 O(N²)이다.

그러나, 두 배열에 공통 값이 아예 없는 최악의 시나리오라면 ok이지만,

루프를 돌다가 첫 번째 배열의 값과 일치하는 두 번째 배열의 값을 찾았다면, 굳이 계속해서 첫 번째 배열의 값을 두 번째 배열의 다음 값들과 비교할 필요가 없다.

알고리즘을 향상시키기 위해, 반복문을 종료하는 break를 추가할 수 있다.

function intersection (firstArr, secondArr) {
  const intersection = [];
  for (let i = 0; i < firstArr.length; i++) {
    for (let j = 0; j < secondArr.length; j++) {
      if (firstArr[i] === secondArr[j]) {
        intersection.push(firstArr[i]);
        break; // 추가 ❗
      }
    }
  }
  return intersection;
}

const arr1 = [1, 2, 3, 4, 5];
const arr2 = [9, 7, 5, 3, 1];
console.log(intersection(arr1, arr2));

이를 통해 다음을 구현할 수 있다.

• 두 배열이 공통 값을 가지지 않는, 최악의 시나리오 : N² 번의 비교를 수행

• 두 배열이 동일한, 최선의 시나리오 : N번의 비교를 수행

• 두 배열이 다르지만 일부 값을 공유하는, 평균 시나리오 : N ~ N² 비교 수행

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

📌 해시 테이블은 배열과 유사하지만, 어떤 상황에서는 배열보다 성능이 좋을 수 있다

📌 두 경쟁하는 자료 구조 중 성능이 더 좋은 자료 구조를 선택하는 능력을 길러 보자

[TIL] 211010 해시 테이블(Hash Table) 참고 (해시 코드 설명)

1) 해시 테이블

(1) 해시 테이블이란?

'key: value' 쌍으로 이뤄진 값들의 리스트

// 자바스크립트 예제
const menu = {
  'french fries': 0.75,
  'hamburger': 2.5,
  'hot dog': 1.5,
  'soda': 0.6
}

해시 테이블 key의 value 룩업하는 방법

menu['hot dog']

console.log(menu['hot dog']); // 1.5

(2) 해시 함수로 해싱

• 해싱

  문자를 가져와 숫자로 변환하는 것

• 해시 함수

  문자를 특정 숫자로 변환하는 데 사용하는 코드
  ex) 덧셈 해시 함수, 곱셈 해시 함수 등

  💡 곱셈 해시 함수 예시

  A = 1 / B = 2 / C = 3 / D = 4 / E = 5
  BAD = (2 x 1 x 4) = 8

  ※ 동일한 문자열은 항상 동일한 숫자로 변환해야만, 유효한 해시 함수라고 할 수 있다. (난수나 현재 시간을 계산에 넣어 사용하는 해시 함수는 유효하지 않다.)
  

(3) 해시 테이블 생성 및 룩업

[예제]

유의어 사전 앱 만들기
사용자가 단어를 룩업하면, 가장 인기 있는 유의어 하나를 반환한다

① 해시 테이블로 유의어 사전을 표현

const dictionary = {};

해시 테이블은 배열과 유사하게, 내부적으로 데이터를 한 줄로 이뤄진 셀 묶음에 저장한다. 각 셀마다 주소가 있다.

② 첫 번째 항목 추가

dictionary['bad'] = 'evil';

// 현재까지 해시 테이블
dictionary = {'bad': 'evil'};

💡 해시 테이블이 데이터를 저장하는 순서

• key에 해시 함수를 적용한다 (여기서는 곱셈 해시 함수 이용)
  key가 'bad'이므로 bad에 해시 함수를 적용하면, bad는 (2 x 1 x 4) = 8로 해싱된다

• 셀 8에 key의 value인 'evil'을 넣는다

③ 두 번째, 세 번째 항목 추가

위와 같은 과정을 거쳐 항목을 추가한다

dictionary['cab'] = 'taxi';
dictionary['ace'] = 'star';

// 현재까지 해시 테이블
dictionary = {'bad': 'evil', 'cab': 'taxi', 'ace': 'star'};

④ 해시 테이블 key의 value 룩업

dictionary['bad']

💡 컴퓨터가 해시 테이블 key의 value를 룩업하는 순서

• key에 해시 함수를 적용한다 (여기서는 곱셈 해시 함수 이용)
  key가 'bad'이므로 bad에 해시 함수를 적용하면, bad는 (2 x 1 x 4) = 8로 해싱된다

• 셀 8을 찾아가서 저장되어 있는 value인 'evil'을 반환한다

🔥 해시 테이블이 배열보다 검색이 빠른 이유

배열에서 메뉴의 특정 항목을 룩업하려면,
정렬되지 않은 배열 : 최대 O(N)이 걸림 (선형 검색)
정렬된 배열 : 최대 O(log N)이 걸림 (이진 검색)

반면,
해시 테이블 : O(1)이 걸림

→ 메뉴의 특정 항목을 key로 사용해, 이를 해싱함으로써 그 값을 얻은 후, 이 값에 해당하는 셀로 바로 접근할 수 있기 때문이다

2) 해시 충돌

(1) 해시 충돌이란?

위 예제에서 또 다른 항목을 추가하고자 한다

dictionary['dab'] = 'pat'

'dab'는 8로 해싱되므로 셀 8에 'pat'을 넣고자 한다.
그러나, 셀 8에는 이미 'evil'이 들어 있다.

이처럼 이미 채워진 셀에 데이터를 추가하는 것을, '해시 충돌'이라고 한다.
이를 해결하기 위한 고전적인 방법으로 분리 연결법이 있다.

(2) 분리 연결법

분리 연결법이란 해시 테이블에 연결 리스트(Linked List)에서 사용하는 노드(Node) 객체를 저장하는 것을 말한다. 해시 테이블의 셀마다 연결 리스트를 하나씩 저장하도록 하고, 충돌이 발생하는 데이터는 연결 리스트의 다음 노드로 계속 추가하도록 한다.

쉽게 설명하면 충돌이 일어난 셀에, 하나의 값을 넣는 대신에, 배열로의 참조를 넣는 것을 말한다.

• 'dab'가 8로 해싱되므로 셀 8에 'pat'이라는 값을 넣고자 한다.
• 그러나, 셀 8에는 이미 'evil'이라는 값이 있어 해시 충돌이 발생한다.
• 이를 해결하기 위해 셀 8에 배열을 만든다. 그 배열은 하위 배열들을 가진다. 첫 번째 하위 배열로 ['bad', 'evil']이 들어 있다. 두 번째 하위 배열로 ['dab', 'pat']이라는 하위 배열을 추가한다.

이제 컴퓨터는 'dab'란 key의 'pat'이라는 value를 찾기 위해, 아래와 같은 과정을 거친다.

• 'dab'가 8로 해싱되므로 셀 8을 찾아본다.
• 셀 8은 배열을 포함하므로, 그 배열의 요소(하위 배열)들을 선형 검색한다.
  이때, 하위 배열의 인덱스 0에 있는 값이 'dab'인지를 확인한다.
• 어떤 하위 배열의 인덱스 0에 있는 값이 'dab'라면, 그 배열의 인덱스 1에 있는 값 즉, 'pat' 반환한다.

💡 해시 충돌이 발생해 분리 연결법에 의해 모든 데이터가 한 셀에 들어가게 되면 선형 검색을 해야 하므로, 최악의 경우 해시 테이블 룩업의 효율성은 O(N)이 된다.

따라서, 처음부터 해시 테이블에 충돌이 거의 일어나지 않도록, O(N)이 아니라 O(1)이 될 수 있도록, 해시 테이블을 구현하는 것이 중요하다.

(3) 충돌 조정 방법

• 해시 테이블의 효율성에 영향을 미치는 3가지 요인

  • 해시 테이블에 얼마나 많은 데이터를 저장하는가
  • 해시 테이블에서 얼마나 많은 셀을 사용할 수 있는가
  • 어떤 해시 함수를 사용하는가

  좋은 해시 함수란, 사용 가능한 모든 셀에 데이터를 분산시켜 충돌 가능성을 낮춰주는 함수다.

  그러나, 적은 데이터를 저장하는 데 필요 이상의 많은 셀을 사용한다면, 이 또한 메모리 낭비다.

  따라서, 해시 테이블은 충돌 조정을 수행해야 한다. 좋은 해시 테이블은 메모리를 낭비하지 않으면서 균형을 유지하며 충돌을 피한다.

• 부하율 : 데이터와 셀 간의 비율

  이상적인 부하율 : 0.7 (원소 7개 / 셀 10개)

• 컴퓨터가 해시 테이블의 충돌을 조정 방법

  처음에는 데이터 7개에 셀 10개로 시작해서, 데이터를 더 추가하면 새 데이터가 새로운 셀들에 균등하게 분산되도록, 컴퓨터는 셀을 더 추가하고 해시 함수를 바꾼다.

  (해시 테이블의 크기, 사용할 해시 함수의 종류, 해시 테이블 확장 시점 등은 대부분 사용자가 쓰고 있는 컴퓨터 언어가 결정한다.)

3) 해시 테이블을 사용해 알고리즘 성능 개선

[TIL] 211015 4장 참고

(1) 집합처럼 사용하기

(여기서 집합은 배열 기반 집합을 말한다)

집합에 새로운 값을 삽입할 때는, N + 1 단계가 걸리는 데 반해(O(N)),
해시 테이블에 새로운 값을 삽입할 때는, 오직 1단계가 걸린다(O(1))

const set = {};

set['apple'] = 1; // 삽입

이미 해시 테이블에 중복된 값이 있더라도, 단순히 그 key의 value에 숫자 1을 겹쳐 쓸 뿐이다.

(2) 배열 내 중복 값 유무 확인

중첩 루프를 사용하는 방법은 효율성이 O(N²)인 데 반해,
해시 테이블을 사용하면 효율성이 O(N)이 된다.

배열이 '숫자'로 이루어진 경우에는, 아래 코드에서 {}를 []로 바꿔도 효율성은 같다.
그러나 배열이 '문자열'로 이루어진 경우에는, {}를 사용해야 한다.

p.149

function hasDuplicateValue (arr) {
  const checkedValues = {}; // 해시 테이블(자바스크립트의 Object) 사용
  for (let i = 0; i < arr.length; i++) {
    if (checkedValues[arr[i]] === undefined) {
      checkedValues[arr[i]] = 1;
    } else {
      return true;
    }
  }
  return false;
}

const arr1 = ['he', 'his', 'him', 'his'];
console.log(hasDuplicateValue(arr1)); // true

(3) 예제 : 전자 투표 기계 만들기

• 방법 1 (배열 & 해시 테이블 이용)

배열에 투표를 저장(삽입)
해시 테이블을 이용해 각 후보별 총 투표 수 세기

p.149

// 투표를 저장 (배열)
const totalVotes = [];

function addVotes (candidate) {
  totalVotes.push(candidate); // 각 투표가 들어오는 대로 배열 끝에 '삽입'
}

addVotes('A');
addVotes('B');
addVotes('A');
addVotes('C');

console.log(totalVotes); // ['A', 'B', 'A', 'C']


// 각 후보별 총 투표 수 세기 (해시 테이블)
function countVotes (votes) {
  const votesPerCandidates = {};

  for (let i = 0; i < votes.length; i++) {
    if (votesPerCandidates[votes[i]]) {
      votesPerCandidates[votes[i]]++; // 투표 수 세기
    } else {
      votesPerCandidates[votes[i]] = 1;
    }
  }

  return votesPerCandidates;
}

console.log(countVotes(totalVotes)); // { A: 2, B: 1, C: 1 }

→ 이 방법은 투표를 저장할 때는 효율성이 O(1)이지만, 각 후보별 투표수를 셀 때는 효율성이 O(N)이라 비효율적이다.

• 방법 2 (only 해시 테이블 이용)

처음부터 해시 테이블에 투표를 저장(삽입)

// 투표를 저장
const totalVotes = {};

function addVotes (candidate) {
  if (totalVotes[candidate]) {
    totalVotes[candidate]++;
  } else {
    totalVotes[candidate] = 1;
  }
}

addVotes('A');
addVotes('B');
addVotes('A');
addVotes('C');

console.log(totalVotes); // { 'A': 2, 'B': 1, 'C': 1 }


// 각 후보별 투표 수 세기
console.log(totalVotes['A']); // 2

→ 이 방법은 투표를 저장할 때도 효율성이 O(1)이고, 각 후보별 투표수를 셀 때도 효율성이 O(1)이므로, 방법 1보다 효율적이다.

→ 해시 테이블을 이용하면, O(1) 삽입과 읽기를 구현할 수 있다.

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

📌 여태까지는 효율성과 속도를 중심으로, 다양한 자료 구조를 분석했다

📌 스택과 큐를 이용하면, 코드의 간결성과 유지보수성을 향상시킬 수 있다

📌 스택과 큐는 임시 데이터를 처리할 수 있는 간결한 도구다 (제약을 갖는 배열)

📌 스택과 큐를 이용하면, 데이터를 순서대로 처리할 수 있고, 필요 없어지면 버릴 수 있다

[TIL] 211007 2.이론 공부 필기(원 노트), [TIL] 211010 추상적 자료 구조(ADT) 참고

1) 스택(Stack)

(1) 스택이란?

배열인데, 제약을 갖는 배열이다

다음과 같은 3가지 제약을 갖는다 ( LIFO )

• 데이터는 스택의 끝(위)에만 삽입할 수 있다
• 데이터는 스택의 끝(위)에서만 읽을 수 있다
• 데이터는 스택의 끝(위)에서만 삭제할 수 있다

스택의 위에 새 값을 삽입 : 스택에 푸시한다
스택의 위에서 원소를 삭제 : 스택으로부터 팝한다

(2) 스택 다뤄보기 🙋‍♀️

오래 사용할 데이터를 저장할 때는 일반적으로 스택을 사용하지 않는다
그러나, 임시 데이터를 다뤄야 할 때는 스택이 유용하다

[예제]
자바스크립트 린터(linter) 구현하기

cf. 자바스크립트 린터란?
자바스크립트 코드 각 줄이 문법적으로 올바른지 확인하는 프로그램

여기서는 코드 줄을 검사해서 괄호 문법 오류가 없는지 확인하는 알고리즘을 구현하고자 함

pp.162 ~ 164
Ruby로 구현된 코드 → JavaScript로 수정

2) 큐(queue)

(1) 큐(queue)란?

배열인데, 제약을 갖는 배열이다

다음과 같은 3가지 제약을 갖는다 ( FIFO )

• 데이터는 큐의 끝에만 삽입할 수 있다
• 데이터는 큐의 앞에서만 읽을 수 있다
• 데이터는 큐의 앞에서만 삭제할 수 있다

(2) 큐 다뤄보기 🙋‍♀️

출력 잡(job)부터 웹 애플리케이션의 백그라운드 워커 등에서 큐를 사용한다.

[예제]
프린트가 네트워크 상의 여러 컴퓨터로부터 출력 잡을 받아들일 수 있도록 인터페이스 구현하기

p.167
Ruby로 구현된 코드 → JavaScript로 수정

🙋‍♀️ 질문

1. 스택 다뤄보기

2. 큐 다뤄보기

✨ 내일 할 것

1. 책 '누구나 자료 구조와 알고리즘' 1 ~ 8장 복습

2. 프로그래머스 문제 풀이