ITeus

이전 포스팅에서 단순한 방법으로 Distinct Value List를 구하는 방법에 대해서 알아보았습니다. 이번에는 보다 빠른 속도로 Distinct Value List를 구하는 방법으로, Hash 탐색을 이용하는 방법입니다. Hash 탐색방법은 이름 에서 알 수 있듯, Hash 알고리즘을 활용합니다. teus-kiwiee.tistory.com/32?category=913862 Hash Hash는 값을 입력받아 해당 값에서 특정 값을 추출하고, 추출한 값을 Index로 하는 Hash Table을 만드는 구조입니다. 이때 Hash Fucntion으로는 다양한 방법이 존재하며, 다양한 값에서 균등한 Hash Code가 teus-kiwiee.tistory.com Hash탐색을 활용 할 경우, Distinct ..

이번 포스팅은 주어진 Data에서 Distinct Value로 구성된 List를 구하는 알고리즘 입니다. 현재 가장 유명한 방법은 Hesh Map을 사용하는 방법이지만, 해당 방법 이전에 Brutal Algorithm 방법으로 구하는 Distinct Value를 구하는 방법에 대해서 알아보겠습니다. 해당 알고리즘은. 1. Random List에서 N번째 원소를 Pick한다 2. N번째 원소가 Distinct List에 있는지 확인한다. 3. 있으면 Pass하고, 없으면 Distinct List에 추가한다. 4. 모든 Random List의 원소를 확인할 때까지 1~3반복 알고리즘이 너무 직관적이라, 특별히 설명이 필요 없어보입니다 ^_^;; 해당 알고리즘은 n개의 Element에 대해서, k번(disti..

Hash는 값을 입력받아 해당 값에서 특정 값을 추출하고, 추출한 값을 Index로 하는 Hash Table을 만드는 구조입니다. 이때 Hash Fucntion으로는 다양한 방법이 존재하며, 다양한 값에서 균등한 Hash Code가 나오는 것이 중요합니다. (만약 Hash Fucntion 결과 모두 97만 나온다고하면, Hash를 하는 의미가 없습니다) 이런 Hash를 구축하기 위해서는 1. Hash Fucntion 2. Hash Table 두가지가 필요합니다. 1. Hash Function 입력받은 Element를 원하는 숫자의 Index로 변형할 때 사용하는 함수입니다. 예를들어봅시다. Hash Table이 0~99개의 index를 가질때, Hash Function을 거친 Element를 Hash C..

1. Binary Tree Binary Tree는 한개의 Node가 최대 2개의 자식 Node를 갖는 Tree구조를 의미합니다. Binary Tree를 구현하는 방법은 1. Array를 이용하여 간접구현 2. Class & Struct를 사용한 Pointing 구현 두가지 방법이 있습니다. Binaray Tree는 이중 두번째, Class를 이용해 Node를 만든고, Node를 이용해 Binary Tree를 만드는 방법입니다. Binary Tree는 Node를 구성되어 있으며, 이 Node는 left_Node, Value, right_Node로 구성됩니다. 이때 Binary Search Tree는 Key_value를 기준으로 Left_node의 value는 작은값이, Right_node는 큰 값을 갖는 ..

배열의 Data를 정렬시켰을 때 n번째 위치의 값을 찾는 알고리즘 입니다. 해당 알고리즘은 Quick_Sort알고리즘에서 활용했던 Partition을 재활용합니다 :) teus-kiwiee.tistory.com/8 Quick Sort 퀵 정렬은 파이썬의 유명한 Package인 Pandas에서 보셨을 수 도 있습니다. (Pandas DataFrame을 정렬하는 방법중 하나로 쓰입니다) pandas.pydata.org/pandas-docs/version/0.15.2/generated/pandas.DataFrame.sor.. teus-kiwiee.tistory.com 탐색 방법 살펴보면.. 1. partition을 진행 2. partition 후 바꿀 위치와 내가 찾는 n번째 위치가 동일한지 비교한다. == ..

이진탐색 알고리즘은 분할정복 방법론을 활용한 탐색알고리즘입니다. 이진탐색 알고리즘의 순서를 살펴보면 1. Data를 오름차순으로 정렬한다. 2. Data의 중간위치의 값과 내가 찾을 값을 비교한다 if 내가 찾을 값 = 중간위치값 -> 탐색끝 else if 내가 찾을 값 1~중간값 이전까지의 데이터에서 다시 이진탐색 else if 내가 찾을 값 > 중간위치값 -> 중간값+1~마지막까지의 데이터에서 다시 이진탐색 보면 알수있지만, 한번 탐색을 하고, 그 이후에 데이터를 분할하여 다시한번 알고리즘을 적용한다. 때문이 이러한 알고리즘은 분할정복 알고리즘이라고 부릅니다. 이진탐색 알고리즘의 성능은 T(n) = T(n/2) + O(1), T(1) = 1 을 보입니다. 이걸 점화식을 풀어주면 T..