[Data Structure] Hash Table, Deque, 투포인터

1. Hash Table 

• 해쉬 테이블(Hash Table)은 입력값이 키-값 쌍(Key-value pair)일 때 이를 저장하는 자료구조이다.
• 대부분의 언어에서 해쉬 테이블은 이미 구현되어 있다. 예를 들어 자바스크립트에서 객체(Object) 자료형이 해쉬테이블로 구현되어 있고 파이썬은 dictionary 자료형을 해쉬 테이블로 사용할 수 있다.

해쉬 테이블의 장점

Hash table	Hash table	Linked list	Array
access	O(1)	O(n)	O(1)
insert	O(1)	O(1)	O(n)
append		O(1)	O(1)
delete	O(1)	O(1)	O(n)

1. 빠른 검색 및 삽입
2. 유연한 크기 조정(메모리 효율 좋음)

해쉬 테이블의 단점

1. 무작위성(순서가 없으므로 순서대로 자료를 저장해야 할 경우 list 사용)

 

해쉬 테이블은 언제 사용해야 하나?

• 사용 조건1 : string을 기반으로 정보를 기록하고 관리해야 할 때
  예를 들어 마라톤 선수들이 레이스를 완주했는지 알아보고자 할 때
  선수 이름을 기준으로 완주 여부를 기록해야 한다.
  이 때 선수 이름(string)을 기준으로 정보를 기록하고 관리해야 하므로
  해쉬 테이블을 사용하는 것이다.
  대부분의 string 기반 정보 관리 상황에서는 해쉬 테이블을 사용한다.
• 사용 조건2 : 검색이 많이 필요한 경우
• 사용 조건3 : 저장, 삭제, 읽기가 빈번한 경우

[JS 예시 Code]

• key가 존재하는지 확인 (Object.keys())

const studentInfo = {};
studentInfo[2024390] = "카리나";
studentInfo[2024392] = "아이유";
studentInfo[2024393] = "장원영";
studentInfo[2024401] = "차은우";

if (Object.keys(studentInfo).includes('2024390')) {
    console.log("학생이 존재합니다");
} else { console.log("학생이 존재하지 않습니다"); }

• key와 value 모두 접근 (for-in문)

for (let key in studentInfo) { 
    console.log(key, studentInfo[key]);
}
  
// 결과    
// 2024390 카리나
// 2024392 아이유
// 2024393 장원영
// 2024401 차은우

• key들에 접근

// 1. for-in문
for (let key in studentInfo) { 
    console.log(key);
}
  
// 결과    
// 2024390
// 2024392
// 2024393
// 2024401

// 2. Object.keys()
console.log(Object.keys(studentInfo));

// 결과 
// [ '2024390', '2024392', '2024393', '2024401' ]

• value들을 접근

// 1. for-in문
for (let key in studentInfo) { 
    console.log(studentInfo[key]);
}
  
// 결과    
// 카리나
// 아이유
// 장원영
// 차은우

// 2. Object.values()
console.log(Object.values(studentInfo));

// 결과
// [ '카리나', '아이유', '장원영', '차은우' ]

• key에 해당하는 value을 가져오기 (dictionary[key])

console.log(studentInfo[2024390]);

// 결과
// 카리나

 

2. Deque

• 덱은 양쪽에서 삽입과 삭제가 가능하며 스택과 큐를 합친 자료구조이다.
• 따라서 스택과 큐로만 해결하기 어려운 상황에서 사용된다.
• 스택과 큐의 성질을 모두 이용해야 풀 수 있는 문제라면 덱을 사용하면 된다.
• 덱은 스택과 큐에 대한 이해가 충분하다면 덱을 사용해야 한다는 것을 바로 알 수 있기 때문에 문제를 많이 풀어보는 것이 중요하다.

[Deque 예시 Code]

• Array로 구현해보기

// CASE : 배열
const deque = [];

// 덱에 값 추가
deque.push(1); // 오른쪽에 추가
deque.unshift(2); // 왼쪽에 추가

// 덱에서 값 삭제
deque.pop(); // 오른쪽에서 삭제
deque.shift(); // 왼쪽에서 삭제

// 덱의 크기
const dequeSize = deque.length;

// 덱 출력
console.log(deque);

• Class로 구현해보기 (투포인터 활용)

// CASE : class

class Deque { 
    constructor() { 
        this.arr = [];
        this.head = 0;
        this.tail = 0;
        this.length = 0;
    }//constructor()

    pushFront(data) { 
        if (this.arr[0]) { 
            for (let i = this.arr.length; i > 0; i--) { 
                this.arr[i] = this.arr[i - 1];
            }
        }
        this.arr[this.head] = data;
        this.tail++;
    }//pushFront

    pushBack(data) {
        this.arr[this.tail++] = data;
    }//pushBack

    popFront() { 
        if (this.head >= this.tail) {
            return null;
        } else { 
            const result = this.arr[this.head++];
            return result;
        }
    }//popFront

    popBack() { 
        if (this.head >= this.tail) {
            return null;
        } else { 
            const result = this.arr[--this.tail];
            return result;
        }
    }

    size() { 
        for (let i = this.head; i < this.tail; i++) { 
            this.length++;
        }
        return this.length
    }
}//Deque{}

const deque = new Deque();

deque.pushBack(1); // [1]
deque.pushFront(2);  // [2, 1]
console.log(deque.popBack()); // 1
console.log(deque.popFront()); // 2
console.log(deque.size()); // 0
console.log(deque); // arr [2, 1], head: 1, tail: 1

 

3. 투포인터

투포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다.

완전탐색이나 이분탐색 알고리즘에서 유용하게 활용할 수 있다. 

 

특징

• 포인터 2개를 준비함. (ex: start, end)
• 탐색을 시작할 때는 start=end=0 이거나 end만 배열의 끝에서 시작함.
• 두 포인터들의 관계가 start <= end일때만 탐색이 진행됨
• 2개의 포인터는 현재 부분 배열의 시작(start)과 끝(end)을 가르킴.

추가로 슬라이딩 윈도우 알고리즘은 마치 창문을 밀면서 이동하는 것처럼 항상 구간의 넓이가 고정되어 있는 투포인터 알고리즘이다.