Hash, map의 문제 유형 탐구

개념탐구

• Python에서 Dictionary 자료형에 대한 것을 본 적이 있을 것이다.
• 해당 자료형은 [key: value]의 쌍으로 묶여있으며 일반적인 배열/리스트 접근방식으로는 접근할 수 없고 해당 key를 사용해야 접근이 가능하다.
• 가령 다음과 같이 과일의 이름과 그 개수가 담겨있는 Dictionary가 있다고 가정해보자

 

my_dic = {
    'apple': 1,
    'banana': 2,
    'grape': 3
}

• 이때, 'apple'은 key라고 정의하고 옆의 숫자 1은 value라고 정의한다. my_dic에서 바나나의 개수를 알고 싶다면, 다음과 같이 접근 할 수 있다.

print(my_dic['banana']) # 2

• 보통 이러한 자료구조를 python에서는 Dictionary라고 하나, 알고리즘에서 이러한 유형의 자료구조는 hashmap 또는 hash table이라고 부른다. C++에서는 STL로 STL::map 이라는 라이브러리를 통해 이러한 자료구조의 구현이 가능하다.
• 일반적으로 데이터에 접근하는데 드는 시간은 O(1)로 상수시간이며, 이러한 특성 때문에 원소를 찾는데 선형 시간O(N)이 드는 배열/리스트 찾기보다 훨씬 빠르다.

 

 

문제 유형

사실 이러한 자료구조만을 사용하여 문제를 풀어야 하는 문제는 단순 구현으로 생각해볼 수 있다. 하지만 이런 hashmap을 사용해야한다는 느낌이 올 때가 있는데

 

• 입력 데이터의 가공이 일반적인 배열/리스트로 저장해서 접근하기가 매우 까다로움
• 가공한 데이터나 입력 데이터를 찾는데 소요되는 시간이 너무 커서 TLE가 나올 가능성이 높음
  • 이 경우 입력 길이가 1백만이 넘는 꽤 큰 크키의 입력 데이터가 들어온다
• 직관적으로 생각할 때 어떠한 특징을 사용하여 데이터를 찾는 것이 더 쉽다

위 3가지 생각이 든다면 hashmap을 사용하는 것이 좋다. 보통 어떤 데이터를 찾을 때 그 특징이 확실하고, 해당 특징을 이용하여 데이터를 찾아야 할 때 hashmap이 빛을 발한다. key를 특징으로 잡고 value에 그 데이터를 넣어도 되기 때문이다.

 

 

자주 사용할 수 있는 함수

여기에선 collections 모듈의 Counter를 소개한다.

• 위의 코드를 다시 한번 보고오자. 각 과일의 개수가 이상적으로 들어 있지만 입력되는 데이터로부터 과일의 이름과 그 과일의 개수가 몇개인지를 계산해야 하는 경우가 있다.
• Counter는 이러한 일을 하는데 적격인 함수로 특정 수 또는 문자가 데이터 안에 몇 개가 있는지를 계산해 이를 Dictionary형(hashmap형) 으로 반환해 준다.

from collections import Counter

data = ['바나나', '사과', '포도', '배', '바나나', '사과', '배', '자몽', '자두', '바나나']
data_dic = Counter(data)

print(data_dic)

• 이를 실행시켜보면 바나나, 사과, 포도, 배, 자몽, 자두가 해당 data에서 몇개나 출현했는지 그 빈도를 계산해 hashmap형태로 반환한다.
• 다음엔 이를 사용한 문제 몇가지를 소개할 예정이다.