Python 코딩테스트: 딕셔너리 문법과 기능, 해시테이블, Counter

파이썬에서 딕셔너리는 매우 유용한 데이터 구조 중 하나로, 키-값 쌍을 저장합니다.

이는 해시 테이블을 기반으로 하여 매우 빠른 검색 속도를 제공합니다.

코딩테스트에서 딕셔너리를 잘 활용하면 문제를 효율적으로 해결할 수 있습니다. 

지금부터 파이썬 딕셔너리의 문법과 유용한 기능을 정리하겠습니다.

 

1. 딕셔너리 생성

딕셔너리는 중괄호 {}를 사용하여 생성합니다. 다음은 몇 가지 생성 방법입니다.

# 빈 딕셔너리 생성
dict1 = {}

# 초기 값으로 딕셔너리 생성
dict2 = {'a': 1, 'b': 2, 'c': 3}

# dict() 함수로 생성
dict3 = dict(a=1, b=2, c=3)

# 리스트를 이용하여 생성
dict4 = dict([('a', 1), ('b', 2), ('c', 3)])

 

2. 요소 접근 및 추가

딕셔너리의 요소는 키를 통해 접근하며, 새로운 키-값 쌍을 추가할 수 있습니다.

# 요소 접근
print(dict2['a'])  # 출력: 1

# 요소 추가 및 갱신
dict2['d'] = 4
dict2['a'] = 10
print(dict2)  # 출력: {'a': 10, 'b': 2, 'c': 3, 'd': 4}

 

3. 요소 삭제

딕셔너리에서 요소를 삭제하는 방법은 여러 가지가 있습니다.

# del 키워드 사용
del dict2['a']
print(dict2)  # 출력: {'b': 2, 'c': 3, 'd': 4}

# pop() 메서드 사용
value = dict2.pop('b')
print(value)  # 출력: 2
print(dict2)  # 출력: {'c': 3, 'd': 4}

# popitem() 메서드 사용 (파이썬 3.7+부터는 마지막 요소를 삭제)
item = dict2.popitem()
print(item)  # 출력: ('d', 4)
print(dict2)  # 출력: {'c': 3}

 

4. 딕셔너리 탐색

딕셔너리의 키, 값, 키-값 쌍을 탐색할 수 있습니다.

dict2 = {'a': 1, 'b': 2, 'c': 3}

# 키 탐색
for key in dict2.keys():
    print(key)  # 출력: a, b, c

# 값 탐색
for value in dict2.values():
    print(value)  # 출력: 1, 2, 3

# 키-값 쌍 탐색
for key, value in dict2.items():
    print(key, value)  # 출력: ('a', 1), ('b', 2), ('c', 3)

 

5. 딕셔너리 메서드

딕셔너리는 여러 유용한 메서드를 제공합니다.

# get() 메서드: 키가 없으면 None을 반환하거나 기본값 설정 가능
print(dict2.get('a'))  # 출력: 1
print(dict2.get('z', '없음'))  # 출력: 없음

# keys(), values(), items() 메서드: 키, 값, 키-값 쌍을 반환
print(dict2.keys())   # 출력: dict_keys(['a', 'b', 'c'])
print(dict2.values()) # 출력: dict_values([1, 2, 3])
print(dict2.items())  # 출력: dict_items([('a', 1), ('b', 2), ('c', 3)])

# in 연산자: 키 존재 여부 확인
print('a' in dict2)  # 출력: True
print('z' in dict2)  # 출력: False

# update() 메서드: 다른 딕셔너리와 병합
dict2.update({'d': 4, 'e': 5})
print(dict2)  # 출력: {'a': 1, 'b': 2, 'c': 3, 'd': 4, 'e': 5}

# clear() 메서드: 모든 요소 삭제
dict2.clear()
print(dict2)  # 출력: {}

 

6. 딕셔너리 컴프리헨션

딕셔너리 컴프리헨션을 사용하면 간결하고 읽기 쉬운 코드로 딕셔너리를 생성할 수 있습니다.

# 예제: 키를 제곱한 값을 가지는 딕셔너리 생성
squares = {x: x*x for x in range(1, 6)}
print(squares)  # 출력: {1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

# 조건부 딕셔너리 컴프리헨션
even_squares = {x: x*x for x in range(1, 11) if x % 2 == 0}
print(even_squares)  # 출력: {2: 4, 4: 16, 6: 36, 8: 64, 10: 100}

 

7. 딕셔너리의 활용 예제

예제 1: 문자열에서 각 문자의 빈도 수 세기

text = "hello world"
frequency = {}

for char in text:
    if char in frequency:
        frequency[char] += 1
    else:
        frequency[char] = 1

print(frequency)  # 출력: {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

예제 2: 학생의 성적 관리

grades = {'Alice': 85, 'Bob': 92, 'Charlie': 87}

# 학생 추가
grades['David'] = 90

# 성적 갱신
grades['Alice'] = 88

# 성적 조회
print(grades['Bob'])  # 출력: 92

# 전체 학생의 성적 출력
for student, grade in grades.items():
    print(f"{student}: {grade}")

결론

파이썬의 딕셔너리는 매우 강력하고 유연한 데이터 구조로, 다양한 상황에서 유용하게 사용될 수 있습니다.

특히 코딩테스트에서는 딕셔너리를 적절히 활용하여 문제를 효율적으로 해결할 수 있습니다. 

 

---

해시테이블이란?

해시테이블(Hash Table)은 컴퓨터 과학에서 매우 중요한 데이터 구조로, 키(Key)-값(Value) 쌍을 저장하고 빠르게 검색할 수 있는 기능을 제공합니다.

해시테이블의 핵심 아이디어는 해시 함수(Hash Function)를 사용하여 데이터를 배열의 인덱스로 매핑하는 것입니다.

이를 통해 평균적으로 O(1)의 시간 복잡도로 검색, 삽입, 삭제가 가능하게 됩니다.

해시테이블은 딕셔너리(Dictionary)나 맵(Map)과 같은 추상 자료형의 기반이 되며, 파이썬의 딕셔너리 역시 내부적으로 해시테이블을 사용합니다.

 

해시테이블의 원리

1. 해시 함수 (Hash Function): 해시 함수는 임의의 크기를 가진 입력 데이터를 고정된 크기의 해시 값으로 변환하는 함수입니다. 이 해시 값은 일반적으로 배열의 인덱스로 사용됩니다.
2. 해시 값 (Hash Value): 해시 함수에 의해 생성된 고정된 크기의 값입니다. 이 값은 해시테이블 내의 특정 위치(버킷, Bucket)를 가리키는 데 사용됩니다.
3. 버킷 (Bucket): 해시 값에 의해 참조되는 배열의 각 요소입니다. 각 버킷은 하나 이상의 키-값 쌍을 저장할 수 있습니다.

해시테이블의 주요 기능

• 삽입 (Insert): 키를 해시 함수에 입력하여 해시 값을 생성하고, 이 해시 값이 가리키는 버킷에 키-값 쌍을 저장합니다.
• 검색 (Search): 키를 해시 함수에 입력하여 해시 값을 생성하고, 이 해시 값이 가리키는 버킷을 검색하여 해당 키-값 쌍을 찾습니다.
• 삭제 (Delete): 키를 해시 함수에 입력하여 해시 값을 생성하고, 이 해시 값이 가리키는 버킷에서 해당 키-값 쌍을 제거합니다.

 

충돌 처리 (Collision Handling)

해시 함수는 다른 키에 대해 동일한 해시 값을 생성할 수 있습니다. 이를 **해시 충돌 (Hash Collision)**이라고 하며, 해시테이블은 충돌을 처리하는 방법이 필요합니다. 주요 충돌 처리 방법은 다음과 같습니다.

 

1. 체이닝 (Chaining):

각 버킷을 연결 리스트로 구현하여 충돌이 발생하면 해당 버킷의 리스트에 키-값 쌍을 추가합니다.

hash_table = [[] for _ in range(size)]

def insert(key, value):
    hash_value = hash_function(key)
    hash_table[hash_value].append((key, value))

def search(key):
    hash_value = hash_function(key)
    for k, v in hash_table[hash_value]:
        if k == key:
            return v
    return None

2. 오픈 어드레싱 (Open Addressing):

충돌이 발생하면 해시 값을 기반으로 새로운 버킷을 찾는 방법입니다.

대표적인 오픈 어드레싱 기법으로는 선형 탐사 (Linear Probing), 이차 탐사 (Quadratic Probing), 이중 해싱 (Double Hashing)이 있습니다.

def insert(key, value):
    hash_value = hash_function(key)
    while hash_table[hash_value] is not None:
        hash_value = (hash_value + 1) % size
    hash_table[hash_value] = (key, value)

def search(key):
    hash_value = hash_function(key)
    while hash_table[hash_value] is not None:
        if hash_table[hash_value][0] == key:
            return hash_table[hash_value][1]
        hash_value = (hash_value + 1) % size
    return None

 

해시 함수의 설계

해시 함수는 키를 가능한 균일하게 분산시켜 충돌을 최소화하는 것이 중요합니다. 좋은 해시 함수의 예로는 djb2 해시 함수, MurmurHash, SHA-256 등이 있습니다. 파이썬에서는 내장 함수 hash()를 사용하여 기본적인 해싱을 제공합니다.

파이썬에서의 딕셔너리와 해시테이블

파이썬의 딕셔너리는 해시테이블을 기반으로 구현되어 있습니다.

이를 통해 매우 빠른 속도의 키-값 쌍 삽입, 검색, 삭제 기능을 제공합니다. 딕셔너리의 사용 예시는 다음과 같습니다.

# 딕셔너리 생성
my_dict = {}

# 키-값 쌍 삽입
my_dict['apple'] = 1
my_dict['banana'] = 2

# 값 검색
print(my_dict['apple'])  # 출력: 1

# 키-값 쌍 삭제
del my_dict['banana']

# 존재 여부 확인
print('banana' in my_dict)  # 출력: False

해시테이블은 그 효율성 덕분에 다양한 애플리케이션에서 중요한 역할을 합니다.

특히, 검색과 삽입이 빈번한 작업에 매우 적합합니다.

코딩 테스트에서도 해시테이블을 적절히 활용하면 효율적인 해결책을 구현할 수 있습니다.

 

---

 

딕셔너리 값에 요소를 추가하기

딕셔너리의 값이 리스트인 경우, 해당 리스트에 값을 하나씩 추가할 수 있습니다:

# 딕셔너리 생성
my_dict = {'a': [1], 'b': [2], 'c': [3]}

# 특정 키의 값 리스트에 요소 추가
my_dict['a'].append(2)
my_dict['a'].append(3)

print(my_dict)  # 출력: {'a': [1, 2, 3], 'b': [2], 'c': [3]}

만약 딕셔너리의 값이 처음에는 정수였지만, 이를 리스트로 변경하여 요소를 추가하고 싶다면, 다음과 같이 할 수 있습니다:

# 딕셔너리 생성
my_dict = {'a': 1, 'b': 2, 'c': 3}

# 특정 키의 값을 리스트로 변경하고 요소 추가
if not isinstance(my_dict['a'], list):
    my_dict['a'] = [my_dict['a']]

my_dict['a'].append(2)
my_dict['a'].append(3)

print(my_dict)  # 출력: {'a': [1, 2, 3], 'b': 2, 'c': 3}

 

---

Counter

Counter는 파이썬의 collections 모듈에 포함된 클래스 중 하나로, 해시 가능한 객체를 세는 데 유용합니다. 주로 항목의 개수를 셀 때 사용됩니다.

from collections import Counter

# 리스트에서 각 요소의 개수 세기
data = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple']
counter = Counter(data)

print(counter)  # 출력: Counter({'apple': 3, 'banana': 2, 'orange': 1})

# 특정 요소의 개수 확인
print(counter['apple'])  # 출력: 3

# 요소 추가
counter['apple'] += 1
print(counter['apple'])  # 출력: 4

# 모든 요소와 개수 확인
print(list(counter.items()))  # 출력: [('apple', 4), ('banana', 2), ('orange', 1)]

Counter는 기본적으로 딕셔너리처럼 동작하며, 각 요소의 개수를 자동으로 세줍니다. 추가적으로, Counter 클래스는 다음과 같은 유용한 메서드를 제공합니다:

• elements(): 모든 요소를 반복 가능한 객체로 반환
• most_common(n): 가장 많이 등장한 n개의 요소를 리스트로 반환
• subtract(): 요소의 개수를 빼기

예제: Counter 사용

from collections import Counter

# 데이터
data = ['a', 'b', 'c', 'a', 'b', 'a']

# Counter 생성
counter = Counter(data)

# 요소 개수 출력
print(counter)  # 출력: Counter({'a': 3, 'b': 2, 'c': 1})

# 가장 흔한 요소 2개 출력
print(counter.most_common(2))  # 출력: [('a', 3), ('b', 2)]

# 요소 추가
counter.update(['a', 'b'])
print(counter)  # 출력: Counter({'a': 4, 'b': 3, 'c': 1})

# 요소 제거
counter.subtract(['a', 'b'])
print(counter)  # 출력: Counter({'a': 3, 'b': 2, 'c': 1})