[파이썬] 해시 > 폰켓몬

set을 활용한 포켓몬 문제 풀이

https://school.programmers.co.kr/learn/courses/30/lessons/1845

아무리 풀어도 도저히 해시 방법으로 풀 수 없어서 아래와 같이 풀었다.

def solution(nums):
    unique_pokemon_n = len(set(nums))
    N = len(nums)//2
    
    return min(unique_pokemon_n, N)

ChatGPT에게 이 방법을 해시로 풀어달라고 했더니 이게 해시를 사용한 방법이라고 한다.

 

딕셔너리 자료구조를 사용한 풀이

이게 무슨 소리야? 난 중복제거 set 자료구조를 사용한건데?

맞습니다. 일반적으로 해시를 이용한 자료 구조는 키-값 쌍을 사용하는 딕셔너리 또는 해시맵을 떠올리게 됩니다. 그러나 set 자료형도 내부적으로 해시 테이블을 사용하여 중복을 제거하고, 빠른 조회를 가능하게 합니다. 이 때문에 set을 사용한 해결 방법도 해시 테이블을 사용한 접근법에 포함될 수 있습니다.

그럼에도 불구하고, 키-값 쌍을 사용하는 딕셔너리 자료 구조를 활용하는 방식으로 문제를 풀고 싶다면, 다음과 같은 방법을 생각해볼 수 있습니다.

딕셔너리를 사용한 접근 방법

1. 각 폰켓몬 종류를 딕셔너리에 키로 저장하고, 해당 종류가 몇 번 나오는지를 값으로 저장합니다.
2. 딕셔너리에 저장된 폰켓몬 종류의 수와 선택할 수 있는 최대 폰켓몬 수를 계산합니다.
3. 두 값 중 더 작은 값을 반환합니다.

코드 구현 (파이썬)

def solution(nums):
    hash_map = {}
    
    # 딕셔너리에 각 폰켓몬 종류의 수를 저장
    for num in nums:
        if num in hash_map:
            hash_map[num] += 1
        else:
            hash_map[num] = 1
    
    # 중복을 제거한 폰켓몬의 종류 수
    unique_pokemons = len(hash_map)
    
    # 선택할 수 있는 최대 폰켓몬 수
    max_selection = len(nums) // 2
    
    # 폰켓몬 종류의 수와 최대 선택 수 중 더 작은 값을 반환
    return min(unique_pokemons, max_selection)

# 예제 실행
nums = [3, 1, 2, 3]
result = solution(nums)
print(result)  # 출력: 2

코드 설명

1. 딕셔너리 생성: hash_map = {}를 통해 빈 딕셔너리를 생성합니다.
2. 딕셔너리에 각 폰켓몬 종류의 수를 저장:
   • for num in nums 루프를 통해 nums 리스트를 순회합니다.
   • 각 폰켓몬 번호 num이 hash_map에 이미 존재하면, 해당 값(폰켓몬 수)을 1 증가시킵니다.
   • 존재하지 않으면, 새로운 키로 추가하고 값을 1로 설정합니다.
3. 중복을 제거한 폰켓몬의 종류 수: unique_pokemons = len(hash_map)를 통해 딕셔너리의 키 개수를 계산합니다.
4. 최대 선택 수 계산: max_selection = len(nums) // 2를 통해 최대 선택할 수 있는 폰켓몬 수를 계산합니다.
5. 최종 결과 반환: min(unique_pokemons, max_selection)를 통해 두 값 중 더 작은 값을 반환합니다.

이 방법은 명시적으로 딕셔너리를 사용하여 문제를 해결하는 방식으로, 해시 테이블의 특성을 활용하여 데이터의 중복을 관리하고 빠르게 접근할 수 있는 장점을 이용한 것입니다.

해시테이블을 활용한 자료구조의 종류

네, 해시 테이블을 이용한 또 다른 자료 구조는 많이 있습니다. 몇 가지 대표적인 예를 들면 다음과 같습니다:

1. 해시맵 (HashMap)

해시맵은 키-값 쌍을 저장하는 자료 구조로, 해시 함수를 사용하여 키를 해시 테이블 내의 인덱스로 변환하여 데이터를 저장합니다. 이는 파이썬의 dict와 유사합니다.

특징:

• 키를 이용한 빠른 데이터 접근 (평균 O(1) 시간 복잡도)
• 키는 유일하며, 동일한 키가 여러 번 저장될 수 없음

2. 해시셋 (HashSet)

해시셋은 중복되지 않는 요소의 집합을 저장하는 자료 구조로, 요소를 해시 함수로 매핑하여 저장합니다. 파이썬의 set이 해시셋의 구현입니다.

특징:

• 중복을 허용하지 않음
• 요소의 빠른 삽입, 삭제, 검색 (평균 O(1) 시간 복잡도)

3. 해시맵을 이용한 집합 (Hash-based Set)

해시맵을 이용한 집합은 HashMap을 사용하여 HashSet을 구현하는 방법입니다. 이 경우, 키를 저장하고 값은 항상 동일한 불리언 값(True)로 저장하여 집합의 요소를 관리합니다.

특징:

• 중복을 허용하지 않음
• 빠른 삽입, 삭제, 검색

4. 해시 테이블을 이용한 트라이 (Hash-based Trie)

해시 테이블을 이용한 트라이는 트라이 자료 구조에서 각 노드를 해시 테이블로 구현한 형태입니다. 이는 문자열 검색 및 저장에 효율적입니다.

특징:

• 문자열 또는 접두사의 빠른 검색
• 해시 테이블을 사용하여 자식 노드를 관리함으로써 효율적인 메모리 사용

5. 해시 힙 (Hash Heap)

해시 힙은 힙 자료 구조와 해시 테이블을 결합한 것입니다. 힙은 우선순위 큐를 구현하는 데 사용되며, 해시 테이블을 통해 요소의 빠른 검색을 지원합니다.

특징:

• 우선순위 큐의 기능 제공 (최소/최대 힙)
• 요소의 빠른 삽입, 삭제, 우선순위 변경

6. 해시맵을 이용한 이중 연결 리스트 (Hash-based Linked List)

해시맵을 이용한 이중 연결 리스트는 이중 연결 리스트의 각 노드를 해시맵으로 구현한 것입니다. 이는 주로 LRU(Least Recently Used) 캐시와 같은 응용에서 사용됩니다.

특징:

• 순차 데이터 접근이 용이
• 해시 테이블을 사용하여 각 노드의 빠른 검색 및 업데이트

7. 해시맵을 이용한 그라프 (Hash-based Graph)

해시맵을 이용한 그래프는 그래프의 인접 리스트를 해시맵으로 구현한 것입니다. 각 노드는 키로 저장되고, 연결된 노드 리스트는 값으로 저장됩니다.

특징:

• 그래프의 효율적인 저장 및 탐색
• 해시 테이블을 사용하여 노드와 간선의 빠른 접근

이와 같이 해시 테이블을 활용한 다양한 자료 구조들이 존재하며, 각 자료 구조는 특정한 문제 해결을 위한 효율적인 방법을 제공합니다. 해시 테이블의 빠른 접근 속도와 충돌 처리 능력을 잘 활용하면, 여러 가지 복잡한 데이터 관리 작업을 효율적으로 수행할 수 있습니다.

 

이게 무슨 소리야? 생전 듣도보도 못한 자료구조네?

 

해시테이블이란?

해시 테이블(Hash Table)은 데이터를 키-값 쌍(Key-Value Pair)으로 저장하는 데이터 구조입니다. 해시 테이블은 효율적인 데이터 저장, 검색, 삭제를 지원하는 자료 구조로, 해시 함수를 사용하여 데이터를 특정 위치에 매핑합니다. 해시 테이블의 주요 특징과 개념을 아래에 설명하겠습니다.

해시 테이블의 주요 특징

1. 해시 함수(Hash Function):
   • 입력 데이터를 특정 길이의 고유한 해시 값으로 변환하는 함수입니다.
   • 해시 함수는 데이터를 해시 테이블 내의 특정 인덱스로 매핑합니다.
   • 좋은 해시 함수는 충돌을 최소화하고, 균일하게 분포된 해시 값을 생성합니다.
2. 충돌(Collision):
   • 서로 다른 두 입력이 동일한 해시 값을 가지는 경우입니다.
   • 해시 테이블은 충돌을 처리하기 위해 여러 가지 방법을 사용합니다.
3. 충돌 처리 방법:
   • 체이닝(Chaining): 동일한 해시 값을 가지는 모든 요소를 연결 리스트로 저장합니다.
   • 오픈 어드레싱(Open Addressing): 충돌이 발생하면 다른 빈 슬롯을 찾아 데이터를 저장합니다.
     • 선형 탐사(Linear Probing)
     • 이차 탐사(Quadratic Probing)
     • 이중 해싱(Double Hashing)
4. 빠른 접근 속도:
   • 평균적으로 O(1) 시간 복잡도로 데이터를 검색, 삽입, 삭제할 수 있습니다.
   • 해시 함수의 성능에 크게 의존합니다.

해시 테이블의 동작 원리

1. 데이터 삽입:
   • 키를 해시 함수에 입력하여 해시 값을 얻습니다.
   • 해시 값을 인덱스로 사용하여 해시 테이블에 데이터를 저장합니다.
   • 충돌이 발생하면, 충돌 처리 방법에 따라 데이터를 저장합니다.
2. 데이터 검색:
   • 키를 해시 함수에 입력하여 해시 값을 얻습니다.
   • 해시 값을 인덱스로 사용하여 해시 테이블에서 데이터를 검색합니다.
   • 충돌이 발생한 경우, 충돌 처리 방법에 따라 데이터를 검색합니다.
3. 데이터 삭제:
   • 키를 해시 함수에 입력하여 해시 값을 얻습니다.
   • 해시 값을 인덱스로 사용하여 해시 테이블에서 데이터를 삭제합니다.
   • 충돌이 발생한 경우, 충돌 처리 방법에 따라 데이터를 삭제합니다.

예제 (파이썬)

파이썬에서 해시 테이블을 구현하는 가장 기본적인 자료 구조는 딕셔너리(dict)입니다. 딕셔너리는 내부적으로 해시 테이블을 사용하여 데이터를 저장합니다.

# 딕셔너리 생성
hash_table = {}

# 데이터 삽입
hash_table["name"] = "Alice"
hash_table["age"] = 25
hash_table["city"] = "New York"

# 데이터 검색
print(hash_table["name"])  # 출력: Alice
print(hash_table["age"])   # 출력: 25

# 데이터 삭제
del hash_table["city"]

# 데이터 확인
print(hash_table)  # 출력: {'name': 'Alice', 'age': 25}

해시 테이블의 장점과 단점

장점:

• 빠른 데이터 접근 속도: 평균적으로 O(1) 시간 복잡도.
• 효율적인 데이터 저장 및 검색.

단점:

• 해시 함수의 성능에 의존: 좋은 해시 함수가 필요.
• 충돌 처리 필요: 잘못된 충돌 처리 방법은 성능 저하를 초래할 수 있음.
• 메모리 사용: 많은 슬롯을 미리 할당해야 할 수 있어 메모리 사용이 비효율적일 수 있음.

결론

해시 테이블은 키-값 쌍을 저장하고 빠르게 검색할 수 있는 매우 효율적인 자료 구조입니다. 적절한 해시 함수를 사용하고 충돌을 효율적으로 처리하면, 데이터의 검색, 삽입, 삭제를 빠르게 수행할 수 있습니다. 파이썬에서는 딕셔너리 자료 구조가 해시 테이블의 기능을 제공하므로, 딕셔너리를 활용하여 다양한 문제를 효율적으로 해결할 수 있습니다.

 

그렇군요. 오늘은 해시테이블의 동작방법에 대해 배웠고, 해시테이블을 활용한 해시 자료구조에 대해 알아보았습니다.