728x90 반응형 책 리뷰/파이썬 알고리즘 인터뷰17 11장. 해시 테이블(5) - 예제(중복 문자 없는 가장 긴 부분 문자열) 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴한다.입력: "abcabcbb"출력: 3입력: "pwwkew"출력: 3 풀이1. 슬라이딩 윈도우와 투 포인터로 사이즈 조절이 문제는 "슬라이딩 윈도우"와 "두 포인터" 기법을 사용하여 해결할 수 있다.슬라이딩 윈도우는 문자열의 특정 구간을 반복적으로 이동하면서 중복 없이 가장 긴 구간을 찾는 방법이다. 1. 슬라이딩 윈도우와 두 포인터의 역할윈도우: 문자열에서 중복 없는 구간을 나타낸다.두 포인터 (start와 index): start는 현재 윈도우의 시작 위치, index는 현재 문자의 위치를 나타낸다.이 방법은 두 포인터를 이용해 윈도우의 크기를 조절하며 중복이 생길 때마다 시작 위치를 업데이트하는 방식으로 작동한다. 예시를 통해 이해하기입력: ".. 2024. 11. 9. 11장. 해시 테이블(4) - 예제(보석과 돌) 문제. 보석과 돌J는 보석이며, S는 갖고 있는 돌이다. S에는 보석이 몇 개나 있을까? 이때, 대소문자는 구분한다. 입력: J ="aA", S = "aAAbbbb"출력: 3 풀이1. 해시 테이블을 이용한 풀이이 문제는 S의 각 문자 빈도를 해시 테이블로 계산한 후, J의 각 문자에 해당하는 빈도 수를 더하는 방식으로 해결할 수 있다. S = "aAAbbbb"freqs = {}for char in S: if char not in freqs: freqs[char] = 1 else: freqs[char] +=1 freqs # {'a': 1, 'A': 2, 'b': 4} S의 각 문자가 몇 번씩 등장하는지 세기 위해 해시 테이블을 생성한다.S의 문자를 순.. 2024. 11. 8. 11장. 해시 테이블 (3) - 충돌 처리 방식 (개별 체이닝 파이썬 구현) 다음의 기능을 제공하는 해시맵을 디자인하라.- put(key, value): 키, 값을 해시맵에 삽입한다. 만약 이미 존재하는 키라면 업데이트한다. - get(key, value): 키에 해당하는 값을 조회한다. 만약 키가 존재하지 않는다면 -1을 리턴한다.- remove(key, value): 키에 해당하는 키, 값을 해시맵에서 삭제한다. 풀이1. 개별 체이닝 방식을 이용한 해시 테이블 구현 우리가 구현할 MyHashMap 클래스의 전체 메소드는 아래와 같다.초기화 __init__()삽입 put()조회 get()삭제 remove()class MyHashMap: def __init__(self): def put(self, key:int, value: int) -> None: .. 2024. 11. 4. 11장. 해시 테이블 (2) - 충돌 처리 방식 (개별 체이닝, 오픈 어드레싱) 파이썬 딕셔너리는 해시 테이블을 기반으로 한 자료형으로, 충돌 해결을 위해 오픈 어드레싱 방식을 사용합니다. 이를 통해 메모리 할당 오버헤드를 줄이고, 성능 저하를 막기 위해 로드 팩터를 낮게 설정하여 최적화를 이루고 있습니다. 충돌 (Collision)해시 함수가 아무리 좋아도 충돌(Collision)은 피할 수 없습니다.예를 들어, 그림 1에서 윤아와 서현의 해시 값이 모두 2로 같아 충돌이 발생했습니다.이렇게 충돌이 발생했을 때는 어떤 방법으로 이를 처리할 수 있을까요?우선 개별 체이닝(Separate Chaining) 방식을 살펴보겠습니다. 1. 개별 체이닝 (Separate Chaining)우선, 입력 데이터는 아래의 표와 같이 구성되었습니다.해시는 키를 해싱한 결과 값이며, 윤아와 서현의 .. 2024. 11. 1. 이전 1 2 3 4 5 다음 728x90 반응형
