목록전체 글 (229)
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..
지난 학기에 운영체제 수업을 듣고., A+을 받았던 과목이지만, 영어 수업이었고 완벽하게 이해를 못한 느낌이 들어 다시 공부를 시작하고, 정리를 해보려고한다. 오늘은 몸 풀기! +) 어차피 복습용으로 적는거라.. 폰트나 가독성에 시간을 쏟지는 않을 것이다.. * 참고 * 조성호 - '쉽게 배우는 운영체제' 책을 참고했다. (영어 원서보다가 한글 책 보니 이해가 너무 잘된다ㅠㅠ(감격)) 1) 생활속의 운영체제 *운영체제 = sw와 hw의 결합인 펌웨어와 유사하다. -> 윈도우,mac,ios,mp3,내비.. 등등 2) 운영체제의 필요성 운영체제를 사용하고 공부해야하는 이유를 알아보자 - 여러 작업을 동시에 사용할 수 있게 되면서, 사용 규칙이 필요해짐 - 새로운 기능추가, 성능 변경 가능 - 자원 관리 - ..
www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 한달 전에 풀었던 문제이지만.. 꽤 생각을 많이 했었던 기억이 난다(?) n,L=map(int,input().split()) List=list(map(int,input().split())) List=sorted(List,key=lambda x:x) cnt=0 m=0 for i in range(n-1): m+=List[i+1]-List[i] if m > L-1: cnt+=1 m=0 print(cn..
www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 정답률이 꽤 낮은 문제. n=int(input()) List=list(map(int,input().split())) List=sorted(List,key=lambda x:x) sum=0 for i in range(n): if sum+1 >= List[i]: sum+=List[i] else: break print(sum+1)
www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 그리디 알고리즘은 많은 사람들이 어려워하는 이유가 분명있다. 코드는 짧지만 획기적인 사고를 해야 풀 수 있다. 최선의 방법을 생각해내지 못하면 코드는 밑도 끝도 없이 길어짐... n=0 while(1): L,P,V=map(int,input().split()) if(L==0 and P==0 and V==0): break else: n+=1 result=(V//P)*(P-(P-L)) if (V%P)
www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net result=0 n=int(input()) data=[] for i in range(n): data.append(int(input())) #음수 따로,양수따로 리스트 분리 후, 양수는 내림차순, 음수는 오름 차순으로.. m_data=[i for i in data if(i0)] p_data=sorted(p_data,reverse=True) #마이너스,0 리스트 부터 if(len(m_data)%2==0): # 데..