반응형 전체 글233 Hash Table과 Collision [ Hash Table ] 해쉬는 중복이 안 되는 것을 목표로 하고 만들어진다. 그래서 어떠한 값이 해쉬로 만들어질 때는 일반적으로 중복이 없다. 다만 기술이 발전하면서 연산 속도가 높아지는 과정을 통해 과거에 안전하다는 해쉬들도 깨지고 있다. MD5가 대표적인 예로 1996년에 collision 문제가 지적되었고 2005년 Birthday Attack으로 안전하지 않은 것이 증명되었다. 다시 원점으로 돌아와서 해쉬는 키값을 통해 중복되지 않는 해쉬를 만들어서 다른 어떤 것들과 함께 있어도 구별이 되어야 한다. 그럼 값들로 이루어진 값을 가지고 있다면 검색에서 엄청나게 빠른 속도를 보여줄 것이다. 이런 기술은 암호화폐로 이어졌고 역시 목표는 중복이 없는 것이다. 해쉬 테이블(Hash Table)은 해쉬 .. 2021. 4. 24. 점화식 Recusion Tree로 풀기 [ 점화식 기본 수식 ] 재귀의 기초 지식 내용을 알아보기 전에 아래의 수식이 어떤 시간 복잡도를 가지고 있는지를 눈으로 읽혀둔다. 처음 봤을 때는 이게 무슨 말인지 모를 수도 있지만, 나중에 딱 이 수식만을 알기 위해 찾을 경우가 존재하므로 글의 가장 상단에 위치시켰다. 하나의 항목을 제거하기 위해 입력을 반복하는 재귀 알고리즘이다. $$T(n) = T(n-1) + n => O(n^2)$$ 입력을 2개로 분할 후, 정렬 작업을 수행하는 재귀 알고리즘이다.(Quick Sort, Merge Sort) $$T(n) = 2T(n/2) + cn => O(nlogn)$$ 하나의 단계마다 입력을 절반으로 줄이는 재귀 알고리즘이다.(Binary Search) $$T(n) = T(n/2) + c => O(logn)$$.. 2021. 4. 21. Binary Search Algorithm [ 이진 탐색 알고리즘 ] 이진 탐색 알고리즘(Binary Search Algorithm)은 리스트에 존재하는 특정 값을 찾기 위해서 리스트의 범위를 절반씩 좁혀가며 찾는 알고리즘이다. 처음부터 끝까지 값을 비교하는 순차 탐색에 비해 이진 탐색 알고리즘은 속도가 월등하게 빠르다. 이진 탐색은 시작, 끝 그리고 중간에 있는 데이터의 인덱스를 통해 범위를 줄이고 비교대상을 찾는다. 다만 이진 탐색 알고리즘을 사용할 때는 리스트 안의 값들이 이미 정렬이 되어 있어야 한다. 정렬이 되어 있지 않은 리스트에서는 이진 탐색 알고리즘을 사용할 수 없다. 그러므로 Mege Sort나 Quick Sort 등을 사용해서 리스트를 먼저 정리하고 이진 탐색을 사용해야 하는 것이다. 정렬이 완료된 리스트에서 범위를 절반을 나누.. 2021. 4. 12. 이전 1 ··· 33 34 35 36 37 38 39 ··· 78 다음 반응형
