[묘공단]파이썬 스터디 4주차
이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 8장 써머리입니다.
- 해시
해시함수를 사용해서 반환한 값을 인덱스로 삼아 키와 값을 저장해 빠른 데이터 탐색을 제공하는 자료구조.
** 고려사항: 충돌을 유의
- 해시 특징
- 단반향 작동.
- 찾고자하는 값 바로 찾기 가능 O(1).
- 값을 인덱스로 활용할 시 적절한 변환과정 필요.
- 자주사용하는 함수
- 나눗법셈
h(x) = x mod m
키를 소수로 나눈 나머지를 활용. K 값으로는 충돌이 적게 발생하는 소수를 사용하며 상황에 따라 아주 많은 데이터를 저장하기 위해 큰소수를 사용해야 한다.
->장점 : 떠올리기 쉬운 가장 단순한 방법, 단점 : 큰소수를 구하는 효율적인 방법 부재.
- 곱셈법
h(x) = ((X*A) mod 1)*m
#X: 최대 버킷의 개수, A : 황금비. 무한소수
1단계 : 키에 황금비 곱학기
2단계 : 소수부분만 취하기
3단계 : 해시테이블에 매핑
->장점 : 소수가 필요없음. 해시테이블이 커져도 추가작업 불필요.
- 문자열 해싱
키의 자료형이 문자열. 문자열의 문자를 숫자로 변환하고 그 숫자들을 다항식의 값으로 변환해서 해싱.
#공식
hash(s) = (s[0]+s[1]*p+s[2]*p^2 .... s[n-1]*p^n-1)mod m
#P: 31(홀수면서 메르센소수) , m: 해시테이블 최대 크기.
*메르센 소수란?
해시함수 적용시 유의할점 : 값이 해시테이블 크기에 비해 너무 클 수 있다는 점. 오버플로를 방지하도록 해야함!
#다음의 연산을 활용해 문자열 해시 함수 수정
hash(s) = (s[0]%m+s[1]*p%m+s[2]*p^2%m .... s[n-1]*^(n-1)p%m)%m
- 충돌처리
- 체이닝으로 처리하기
해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결.
- 해시테이블 공간활용성 떨어짐.
- 검색 성능 떨어짐. O(N)
- 개방주소법으로 처리하기
빈 버킷 값을 찾아 충돌값을 삽입. 체이닝보다 메모리를 효율적으로 사용가능.
1) 선형 탐사 방식 : 다른 빈 버킷을 찾을때까지 #h1 :1차 해시함수.
h(k,i) = (h(k)+i)mod m
#m: 수용가능한 최대 버킷
충돌값들이 모이는 영역인 클러스터 형성 -> 제곱수만큼 이동하여 탐사2) 이중 해싱 방식
해시 함수 2개 사용.
h(k,i)=(h1(k)+i*h2(k))mod m
#h1: 1차 해시함수, h2: 2차 해시함수.
#첫번째 함수에 충돌 발생시 해당위치를 기준으로 어떻게 위치를 정할지 결정 : 두번째 해시함수
클러스터를 줄이기위해 m을 제곱수로하거나 소수로함.
해시문제의 핵심은 키와 값을 매핑하는과정.
*** 이번 문제는 이해가 힘들어서 책의 풀이를 참고하여 분석해 작성하였습니다.
(임시저장으로 작성해둔게 날라가서,,,퇴근후 다시 간단하게 재작성,,ㅠㅠ)
*몸풀기
1. 두개의 수로 특정값 만들기
n개 양의 정수로 이루어진 리스트 arr과 정수target이 주어졌을때 이중에서 합이 tartget인 두수가 arr에 있는지 찾고, 있으면 True, 없으면 False.
def pair_sum(arr, target):
numbers = {} # 해시 테이블
for num in arr:
complement = target - num
if complement in numbers:
return True
numbers[num] = True # 아니라면 현재 숫자를 해시 테이블에 추가
# 조건을 만족하는 쌍이 없으면 False
return False
2. 문자열 해싱을 이용한 검색 합 수 만들기
문자열 리스트 string_list와 쿼리 리스트 query_list가 있을때 각 쿼리 리스트에 있는 문자열이 string_list의 문자열 리스트에 있는지 여부 확인.
def check_strings_exist(string_list, query_list):
result_list = [] # 리스트 초기화
for query in query_list:
# 현재 쿼리가 string_list에 있는지 여부를 결과 리스트에 추가
result_list.append(query in string_list)
return result_list
*모의테스트
3. 완주하지 못한 선수
def solution(participant, completion):
# 딕셔너리를 생성하고 각 참가자의 등장 횟수를 기록
participant_dict = {}
for name in participant:
if name in participant_dict:
participant_dict[name] += 1 #만약 이미 등록된 참가자면 +1
else:
participant_dict[name] = 1
# 완주자 명단을 통해 각 참가자의 등장 횟수를 감소
for name in completion:
participant_dict[name] -= 1
# 등장 횟수가 0이 아닌 참가자가 완주하지 못한 선수
for name, count in participant_dict.items():
if count != 0:
return name
4. 할인 행사
def solution(want, number, discount):
want_dict = {} # 원하는 제품과 수량을 매핑할 딕셔너리 생성
# want과 number를 매핑하여 딕셔너리에 저장
for i in range(len(want)):
want_dict[want[i]] = number[i]
answer = 0 # 회원가입 가능한 경우의 수를 저장할 변수
# discount 리스트를 10일씩 끊어서 검사
for i in range(len(discount) - 9):
discount_10d = {} # 현재 10일 동안 할인하는 제품의 수량을 기록할 딕셔너리 생성
# 10일 동안 할인하는 제품의 수량을 딕셔너리에 기록
for j in range(i, i + 10):
if discount[j] in want_dict:
# 할인 제품이 원하는 제품 목록에 있다면 수량 기록
discount_10d[discount[j]] = discount_10d.get(discount[j], 0) + 1
# 할인한 제품 수량이 want_dict와 같다면 회원가입 가능
if discount_10d == want_dict:
answer += 1
return answer
5. 오픈 채팅방
def solution(record):
answer = [] # 최종 결과를 저장할 리스트
uid = {} # 사용자의 uid와 닉네임을 기록할 딕셔너리
# 레코드를 순회하며 사용자의 닉네임을 기록
for line in record:
cmd = line.split(" ")
# Enter 또는 Change일 경우에만 사용자의 닉네임을 업데이트
if cmd[0] != "Leave":
uid[cmd[1]] = cmd[2]
# 최종 결과 생성
for line in record:
cmd = line.split(" ")
action = cmd[0]
user_id = cmd[1]
if action == "Enter":
answer.append(f"{uid[user_id]}님이 들어왔습니다.")
elif action == "Leave":
answer.append(f"{uid[user_id]}님이 나갔습니다.")
return answer
6. 베스트 앨범
def solution(genres, plays):
answer = []
genre_dic = {} # 장르별 총 재생 횟수 기록
play_dic = {} # 각 노래의 고유 번호와 재생 횟수 기록
# 각 장르와 노래의 플레이 횟수를 딕셔너리에 기록
for i in range(len(genres)):
genre = genres[i]
play = plays[i]
genre_dic[genre] = genre_dic.get(genre, 0) + play
play_dic[i] = (genre, play)
# 재생 횟수 기준으로 장르를 내림차순으로 정렬
sorted_genres = sorted(genre_dic.items(), key=lambda x: x[1], reverse=True)
for genre, _ in sorted_genres:
songs = [song for song, play in play_dic.items() if play[0] == genre]
sorted_songs = sorted(songs, key=lambda x: (play_dic[x][1], -x), reverse=True)
answer.extend(sorted_songs[:2])
# 각 장르에서 가장 많이 재생된 두 개의 노래를 answer에 추가
return answer
7. 신고 결과 받기
def solution(id_list, report, k):
# reported_user: 각 유저가 신고한 유저 기록
# count: 각 유저가 정지된 횟수 기록
reported_user = {}
count = {}
# 각 신고 기록을 분석하여 reported_user 딕셔너리를 만들기.
for r in report:
user_id, reported_id = r.split()
if reported_id not in reported_user:
reported_user[reported_id] = set()
reported_user[reported_id].add(user_id)
# 각 유저별로 정지 여부를 확인하고 정지되면 count 딕셔너리 업데이트
for reported_id, user_id_list in reported_user.items():
if len(user_id_list) >= k:
for uid in user_id_list:
if uid not in count:
count[uid] = 1
else:
count[uid] += 1
# 최종적인 결과
answer = []
for i in range(len(id_list)):
if id_list[i] not in count:
answer.append(0)
else:
answer.append(count[id_list[i]])
return answer
이번장은 이해만으로 시간이 다간거같다.. ㅠㅠ 스터디원들이 모두 열정적으로 잘하셔서 열심히 따라갈수있도록 더 많이 노력해야할듯,,