자료구조 및 알고리즘 2

해시(hash)

해시(hash)란 해시란 다양한 길이를 가진 데이터(key)를 고정된 길이를 가진 암호화된 데이터(value)로 변환시키는 것이다. 암호화된 데이터는 단방향 암호화로 이루어진 특성을 가지고 있으며, 이러한 특성으로 인해 패스워드 설정, 블록체인 등에 사용한다. 또한, 해시는 해시 테이블(hash table)이라는 곳에 key와 value가 한 쌍으로 저장된다. 그리고 key값이 해시 함수를 통해 변환된 후, 다른 작업을 거쳐 배열의 인덱스로 변환된다. 그래서 이 배열의 인덱스를 이용해서 value를 찾을 수 있으므로 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 된다. 결론은 해시를 사용하면 장점은 1. key에 대한 암호화 2. 검색과 저장을 빠르게 할 수 있다! 위의 두 사진처럼 임의의 길..

시간복잡도

알고리즘을 평가하는 데는 2가지 기준이 있다. 첫째, 알고리즘 실행시간에 해당하는 시간 복잡도 둘째, 메모리 사용량에 해당하는 공간 복잡도. 일반적으로 알고리즘을 평가할 때는 메모리의 사용량보다 실행 시간에 초점을 준다. 그러므로 시간 복잡도에 대해 정리해보겠다. 시간 복잡도란? - 알고리즘이 다수의 입력값에 대한 문제를 얼마나 빠른 시간 내에 해결하는지 알 수 있는 척도(표기법). 알고리즘의 효율성을 판별할 수 있다. 시간 복잡도 표기법 3가지 1. 빅-오메가: 최고의 성능일 경우(Best Case) 2. 세타: 평균의 성능일 경우(Average Case) 3. 빅-오: 최악의 성능일 경우(Worst Case) 표기법의 3가지 중, 대부분 Big-O를 활용한다. 그 이유는, 평균의 성능 일 때가 좋아 ..