본문 바로가기

dict5

해시 테이블 - collision resolution method 해시 함수에 의해 특정 인덱스 값이 정해지게 되면 c - universal function이기 때문에 충돌이 발생할 수 밖에 없다. 충돌이 발생했다는 것은 내가 삽입하려고 하는 슬롯에 이미 다른 key value 데이터가 저장되어 있는 것. 그럼 다른 어느 곳에 저장해야 될까? 에 대한 것을 collision resolution method이다. 대표적인 방법 중 하나 Open addressing인데 그 방식은 3가지로 나눌 수 있다. 1. linear probing - 한칸씩 2. quadratic probing - 제곱칸씩 3. double hashing - 해시함수 두개 set 함수 : key 값이 해시테이블에 있으면 update하고 아니면 insert (upsert) set(key, value=N.. 2021. 12. 31.
해시 테이블 해시 테이블은 매우 빠른 삽입, 삭제, 탐색 연산을 제공하는 자료구조 python에서는 dict를 사용 key와 value의 형태로 해시 테이블에 저장 ( 해시 테이블은 보통 배열을 사용, 이 슬롯의 크기를 m이라 함) 해시 테이블에 저장할 때 hash Function을 이용해서 특정한 인덱스(Hash Code)를 지정해주게 됨 python에서는 hash(key)를 입력하게 되면 특정 key가 출력됨 hash function 1. perfect hash function : 이상적인 h.f key -> slot 이 1:1로 매치됨 즉, collision이 발생하지 않음 -> 비현실적 2. universal hash function : x란 key 값과 y란 key 값이 있다고 했을 때 f(x) == f(y.. 2021. 12. 29.
[프로그래머스] 실패율 (Python) https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr dict 활용 문제다 defaultdict 활용하면 좀 더 편하긴 함. - dict 정렬 참고 나의 풀이 def solution(N,stages): member = len(stages) counting = {} result = {} for stage in stages: if counting.get(stage): counting[stage] += 1 else: c.. 2021. 12. 21.
[프로그래머스] 방금 그곡 (Python) https://programmers.co.kr/learn/courses/30/lessons/17683 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 내가 짠 알고리즘은 다음과 같다. 1. #들어가 있는 음은 변환 2. 라디오에서의 play_time 계산 3. play_time과 실제 음악 시간과 비교해서 실제 재생된 음악 값으로 변경 4. 네오가 기억하는 멜로디가 실제 재생 된 음악에 있다면 5. 후보군에 이름, 재생된 시간, 입력된 순서 저장 6. 재생된 시간과, 입력된 순서 기준으로 정렬 7.. 2021. 11. 4.
[프로그래머스] 방문 길이 (Python) https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr set을 활용해서 풀면 된다. 주의해야 할 점은 (0, 0) -> (1, 0)으로 가는 길과 (1, 0) -> (0, 0)으로 가는 길은 동일한 길이다. 나의 풀이 from collections import defaultdict def solution(dirs): answer = 0 load = defaultdict(set) x, y = 0,0 for dir in dirs: if dir =='U': if y+1 -6: load[(x,y)].update([(x,y-1)]) load[(x,y-1)].update([(x,y)]) x,y = x,y-.. 2021. 11. 4.

티스토리툴바