본문 바로가기
반응형

동굴 속 정보183

Binary Tree Traversal, DFS, BFS [ Binary Tree Traversal ] 트리를 순회하는 방법을 "Binary Tree Traversal"이라고 한다. 어떻게 하면 트리의 맨 아래에 있는 가지를 전부 둘러보면서 조회를 할 수 있을까를 방법론으로 만든 것이다. 방법은 3가지가 있다. InOrder, PreOrder 그리고 PostOrder이다. InOrder는 (LVR : Left, Root, Right)라고 하며 왼쪽, 가운데 그리고 오른쪽을 차례대로 순회한다. PreOrder는 (VLR : Root, Left, Right)라고 하며 가운데, 왼쪽 그리고 오른쪽을 차례대로 순회한다. 마지막으로 PostOrder는 (LRV : Left, Right, Root)라고 하며 왼쪽, 오른쪽 그리고 가운데를 차례대로 순회한다. (1) InO.. 2021. 4. 25.
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.
반응형

티스토리툴바