전체 글133 알고리즘 - 해시법(2) 저번 포스팅에 이어서 체인법입니다. 이번에는 노드를 key, value, next 이렇게 세 가지로 구성해서 key 값도 넣겠습니다. 또한 value가 str형일 때 hashlib을 사용해 해시값을 구해보겠습니다. chain_hash.py from __future__ import annotations from typing import Any, Type import hashlib class Node: def __init__(self, key: Any, value: Any, next: Node) -> None: self.key = key # 키 self.value = value # 값 self.next = next # 뒤쪽 노드 참조 class ChainHash: def __init__(self, capac.. 2020. 10. 27. 알고리즘 - 해시법(1) 이진 검색에 이어 해시법입니다. 해시법 해시법은 데이터를 저장할 위치를 간단하게 연산으로 구하는 방법입니다. 이 방법은 데이터의 검색뿐만 아니라 추가, 삭제도 효율적으로 할 수 있습니다. 배열에서 각각의 원소 값을 배열의 크기로 나누어 원소에 접근할 때 기준 값으로 합니다. 원소 값 5 6 20 31 37 53 78 해시값 (7로 나눔) 5 6 6 3 2 4 1 해시값을 배열의 인덱스로 생각하고 다시 만들어 보면 인덱스 0 1 2 3 4 5 6 원소 None 78 37 31 53 5 6 20 만약 숫자 21을 추가한다면 다른 원소들을 이동할 필요 없이 21을 7로 나눈 값인 0에 넣어주면 됩니다. 인덱스 0 1 2 3 4 5 6 원소 21 78 37 31 53 5 6 20 하지만 문제가 있습니다. 6번 .. 2020. 10. 26. 알고리즘 - 이진 검색 선형 검색에 이어 이진 검색입니다. 이진 검색은 배열을 정렬시켜야 하며 선형검색 보다 더 빠르게 검색할 수 있습니다. 이진 검색은 배열의 중앙 원소에 집중한다고 생각하면 됩니다. 11 24 37 41 53 72 88 위와 같이 오름차순으로 정렬된 배열이 있을 때, 숫자 24를 찾는다고 가정합니다. 배열 중간에 위치한 41을 기준으로 배열을 나누어 생각합니다. 숫자 24는 41보다 작기 때문에 41 뒤에 있는 배열은 생각하지 않고 41 앞쪽에 있는 11, 24, 37만 봅니다. 11 24 37 앞쪽 배열만 가지고 오면 지금 찾고 있는 숫자인 24가 중앙에 위치하게 됩니다. 이렇게 현재 찾는 숫자의 인덱스를 알 수 있습니다. 이진검색 코드 from typing import Any, Sequence def b.. 2020. 10. 25. 알고리즘 - 선형 검색 선형검색은 배열에서 검색하는 방법 중 가장 기본적인 알고리즘입니다. 6 4 3 2 1 5 8 9 이렇게 직선으로 늘어선 배열에서 검색할 때, 원하는 키 값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘입니다. 선형검색 코드 from typing import Any, Sequence def line_search(x:Sequence, key:Any) -> int: i = 0 while True: if i == len(x): return -1 if x[i] == key: return i i += 1 # 검색한 원소의 값이 있으면 인덱스 값 i 리턴, i가 x의 크기와 같으면 -1 리턴 print('-----선형검색-----') num = int(input('원소의 수를 입력하세요.:.. 2020. 10. 21. 이전 1 ··· 13 14 15 16 17 18 19 ··· 34 다음
