Study

[묘공단]파이썬 스터디 4주차

A란 2023. 12. 15. 22:31

이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 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

 

이번장은 이해만으로 시간이 다간거같다.. ㅠㅠ 스터디원들이 모두 열정적으로 잘하셔서 열심히 따라갈수있도록 더 많이 노력해야할듯,,