ITeus

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

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번을 모두..