본문 바로가기
728x90
반응형

책 리뷰34

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.
[Day5/30] 초보자를 위한 SQL 200제 1. 숫자를 버리고 출력하기 (TRUNC)876.567 숫자를 출력하는데 소수점 두 번째 자리인 6과 그 이후의 숫자들을 모두 버리고 출력SELECT '876.567' as 숫자, TRUNC(876.567,1), TRUNC(876.567,-1) FROM dual;  TRUNC(N,1): 소수점 두 번째 자리부터 버림TRUNC(N,-1): 소수점 이전 일의 자리부터 바로 버리고 출력  2. 나눈 나머지 값 출력하기 (MOD)숫자 10을 3으로 나눈 나머지 값이 어떻게 되는지 출력SELECT MOD(10,3) FROM dual;​ 사원 번호와 사원 번호가 홀수이면 1, 짝수이면 0을 출력 SELECT empno, MOD(empno,2) FROM emp;  사원 번호가 짝수인 사원들의 사원 번호와 이름을.. 2024. 11. 7.
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.
728x90
반응형