DevKim

오픈 주소법은 충돌이 발생했을때 재해시 (rehashing) 를 통하여 빈 버킷을 찾아나서는 방법이다. 오픈 주소법은 빈 버킷이 나올때까지 해싱을 반복하기 때문에 선형 탐사법이라고 불리기도한다.. 암튼 주의해야할 점은 버킷에 따로 속성을 부여해줘야한다.! 1. 이 버킷이 데이터가 저장되어있는지 2. 이 버킷이 비어있는지 3. 원래는 뭔가 있었는데, 삭제 명령으로 삭제된 버킷인지 이렇게 총 3가지의 속성을 부여해줘야한다. *재해시 함수를 +1 한 후에 기존의 해시법을 적용하는 방법으로 가정하고 코드를 작성했다. from enum import Enum import hashlib #버킷의 속성지정 class status(Enum): OCCUPIED=0 #데이터가 저장되어있음 EMPTY=1 #버켓이 비어있음 D..

해시법 중에 충돌 대처하는 방법 중 하나인 체인법을 이용하여 구현해보았다. 체인법은 간단하게 해시값이 같은 원소를 연결리스트로 관리하는 방법이다. >> hashlib.sha256(str(key).encode()).hexdigest(),16 이 코드는 처음 알게된 부분이라 따로 etc 카테고리에 issue를 정리할 예정. import hashlib #노드 생성 class Node: #초기화 def __init__(self,key,value,next_v): self.key=key self.value=value self.next=next_v class chaining: def __init__(self,size): self.size=size #테이블의 사이즈 self.table=[None]*self.size #..

[ 개념 ] - 맨 앞부터 스캔하여 순서대로 검색하는 선형탐색과 달리, 이진탐색은 우선, data가 sorting 되어있다는 가정 하에 탐색을 진행한다. 원리는 간단하다. 중앙 값을 선정하여 탐색의 범위를 좁혀나가는 것. 탐색하고자하는 key값이 중앙값 보다 크면 left의 값을 중앙값+1로, key값이 중앙값보다 작으면 right를 중앙값-1로.. 이렇게 점차 탐색 범위를 줄여주는 것이다. [ 적용 기준 ] - 보통 어떤 x에 관해 함수 f(x)가 증가하거나 감소하는 함수일때 start,end를 x에 관한 최소값과 최대값으로 설정하여 이진 탐색으로 문제 해결 [ 코드 ] #검색 대상은 반드시 오름 차순 정렬 되어있어야함! #정렬 되어있다고 가정했을 때의 예제 from typing import Any,S..

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 처음부터 반례까지 모두 찾아내고, 한번에 '성공!'을 받아내는걸 목표로 하고 있는 요즘. 문제 완벽하게 이해하고 반례를 찾아내는게 키포인트다. 꼼꼼하게 집중해서.! DFS로 한번에 해결~ from collections import deque que=deque() dx=[-1,1,0,0] dy=[0,0,-1,1] result=[] t=int(input()) for i in range(t): #테스트 케이스 cnt=0 #배추 ..

www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 정답률이 44%인걸보니 쉬운 문제이구나 생각했다. 토마토 문제를 풀고 푸니 너무 쉬웠다.! 10분만에 풀었다 n=int(input()) m=int(input()) graph={i:[] for i in range(1,n+1)} for i in range(m): x,y=map(int,input().split()) graph[x].append(y) graph[y].append(x) for key in graph: grap..

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 제일 중요한 것은 문제를 이해하는 것 & 반례를 찾는 것 이라고 생각한다. 코드 짜기 전에 문제 완벽하게 이해하고 테스트 케이스 꼼꼼하게 찾아보기. from collections import deque que=deque() m,n=map(int,input().split()) graph=[] visited=[[] for i in range(n)] for i in range(n): for j in ..

www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net # BFS from collections import deque def BFS(graph,start): for key in graph: graph[key].sort() visited=[0 for i in range(a)] queue=deque() queue.append(start) while queue: #큐 안에 원소가 있는 동안 k=queue.popleft() for i..