ITeus

Queue는 Array를 활용한 사용자 자료구조 중 하나입니다. Queue의 원리는 First In First Out(FIFP) 가장 먼저 들어온 Element가 가장 먼저 나간다 입니다. 정수기의 종이컵 / 놀이공원 대기열을 생각하면 쉽습니다. Queue 역시 자료구조이기 때문에, Element의 Add와 Delete가 존재합니다. 하지만 FIFP의 원칙 때문에 Delete는 Output에서만, Add는 Input 에서만 가능합니다. 이때 Delete부분을 보면, Output Pointer가 움직이면서 첫번째 위치는 더이상 Pointing하지 못하는 것을 알 수 있습니다. 때문에 선형 Queue의 경우 Queue가 채워진 후 삭제되면 Capacity가 같이 감소하는 단점이 있습니다. Python으로 구..

Stack은 자료구조에서 가장 처음 배우는 자료구조입니다. Stack은 말 그대로 데이터를 쌓는 자료구조라고 할 수 있습니다. 쌓아올린 탑의 아래부분을 건드리면 탑이 무너지죠? Stack또한 마찬가지 입니다. Stack은 오직 최 상당의 Element만 접근, 삭제, 추가가 가능합니다. 이러한 Stack의 특수성을 고려해 Element의 추가는 push, Element의 제거 및 반환은 pop 이라고 합니다. 이때 Stack에 Pointer라는것이 있는것을 알 수 있습니다. 모든 자료구조는 Maximum Size가 있기 때문에, Element의 추가, 삭제에 따라 Pointer가 움직이고 이 Pointer의 위치를 통해서 현재 Stack의 상태를 확인할 수 있습니다. Python으로 구현된 Stack 자..

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