알고리즘

에라토스테네스의 체란? 소수를 판별하는 알고리즘이다. 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 소수란? 간단하게 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의할 수 있다. 단일 숫자 소수 여부 확인 어떤 수의 소수의 여부를 확인 할 때는, 특정한 숫자의 제곱근까지만 약수의 여부를 검증하면 O(N^1/2)의 시간복잡도로 빠르게 구현할 수 있다. 수가 수(N이라고 가정)를 나누면 몫이 생기는데, 몫과 나눌 수 있는 둘 중에 하나는 N 제곱근 이하이기 때문이다. 만약, 대량의 소수를 한꺼번에 판별해야할 경우는 '에라토스테네스의 체'를 이용한다. 에라토스테네스의 체 원리 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 ..

1. Hash Table 해쉬 테이블(Hash Table)은 입력값이 키-값 쌍(Key-value pair)일 때 이를 저장하는 자료구조이다.대부분의 언어에서 해쉬 테이블은 이미 구현되어 있다. 예를 들어 자바스크립트에서 객체(Object) 자료형이 해쉬테이블로 구현되어 있고 파이썬은 dictionary 자료형을 해쉬 테이블로 사용할 수 있다.해쉬 테이블의 장점Hash tableHash tableLinked listArrayaccessO(1)O(n)O(1)insertO(1)O(1)O(n)append O(1)O(1)deleteO(1)O(1)O(n)빠른 검색 및 삽입유연한 크기 조정(메모리 효율 좋음)해쉬 테이블의 단점무작위성(순서가 없으므로 순서대로 자료를 저장해야 할 경우 list 사용) 해쉬 테이블은 ..