ITeus

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..

Huffman Coding은 글자의 빈도수를 기반으로 text를 2진수의 조합으로 변환하는 알고리즘입니다. 글자의 출현 빈도수가 높을수록 작은 2진수를, 글자수의 빈도가 낮을수록 높은 2진수를 부여합니다. 그렇게되면 기존의 Text를 2진수로 무손실 압축을 할 수가 있습니다(정보의 손실X) 과거 Huffman이 고안하여 Huffman Coding이라고 하며, 원본을 알기 위해선 Coding 된 Text와 함께 Huffman Tree가 필요합니다. Huffman Tree의 생성 알고리즘은 1. 문자의 총 출현 빈도를 가지고, 가장 높은 빈도수의 문자부터 Top Node의 Left Node에 추가해줍니다. 2. Right Node로 이동하여 1번을 반복합니다. 3. Unique Text의 개수만큼 Node가..

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는 큰 값을 갖는 ..

알고리즘에서, 무게를 가지는 추 n개를 가지고, M의 무게의 무게를 맞출수 있다면, 이를 Scale이 가능하다고 합니다. 이번 알고리즘은 주어진 n개의 추를 가지고 무게 M을 Scale할 수 있는지를 확인하는 알고리즘 입니다. 위와같은 상황에서 4개의 추 가지고 12를 만들 수 있을까요? 이런 상황에선 간단하게 12 = 5+7 또는 4+1+7의 조합으로 가능한 것을 알 수 있습니다. 하지만 M이 커지고, 추의 개수가 증가하면 그 조합을 모두 확인하기란 어렵습니다. 이제 Scale 가능 여부를 확인하는 알고리즘을 보겠습니다. 무게 Wx인 추를 추가하여, 무게 k를 측정할 수 있는지 여부를 알기 위해선 1. W1~W(x-1)의 추를 가지고 k-Wx(=Wx가 추가되기 전 무게)를 측정할 수 있는지 여부와 2...

Heap이란 완전 Binary트리를 형성하는 자료구조의 일종입니다. teus-kiwiee.tistory.com/29 Heap 이때 Max_heap과 Min_heap이 있으며, 아래 예시를 보면 이해하기 쉽습니다. Random한 Array를 Max Heap 또는 Min Heap을 만들었을 경우의 모습입니다. 따로 설명이 필요없어보이네요 이때 Tree구조를 언어에서 teus-kiwiee.tistory.com 이때, Heap의 형성 후 Top Node의 값이 Max Or Min 값을 갖게 됩니다. 이때 Top Node의 값을 활용해서 Data를 정렬하는 방법을 Heap Sort 알고리즘 이라고합니다. 알고리즘은 1. Random Array에 Max heap 형성 2. 0번 Node의 값 추출 3. 마지막 No..

1. Insert Sort Insert Sort알고리즘은 주어진 배열을 정렬하는 알고리즘 중 하나입니다. 해당 알고리즘은 정렬된 Array를 구축하고, 새로운 원소를 정렬된 Array에 Insert하는 알고리즘이어서 Insert 정렬이라고 불립니다. 알고리즘은 1. N번째 원소를 뽑는다(0~N-1번째 원소까지는 정렬이 되어있는 상태) 2. N번째 원소를 0~N-1 사이에 정렬된 위치로 이동시킨다. 3. N+1의 원소에서 1~2번 반복 이렇게 마지막 원소까지 이동하면 정렬이 완료되게 됩니다. 이 알고리즘은 모든 원소를 한번씩 선택(n) 하여 선택된 원소를 정렬된 원소들과 비교(n-1)를 진행하기 때문에 1+2+3+....n-1 = n(n-1)/2 = O(n2)의 시간복잡도를 갖습니다. 이때 n-1번을 모두..