ITeus

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

Dijkstra 알고리즘은 특정 Node를 시작점으로 하여, 해당 시작점부터 각 Node의 최단거리를 구하는 알고리즘입니다. 알고리즘은 1. 최초 시작점을 제외, 나머지 Node까지의 거리를 ∞로 설정한다. 2. 시작점에서 각 Node까지의 거리를 갱신 3. 시작점에서 가장 가까운 Node로 이동 4. 2~3을 반복하며, 더이상 이동할 Node가 없을때까지 반복 예시를 보면서 좀더 알아보겠습니다. Kruskal 알고리즘을 포스팅 할때 사용한 숙련된 조교를 한번더 이용하겠습니다. B Node를 시작점으로 진행하겠습니다. B와 연결된 모든 Node와의 거리를 해당 Node의 Distance라고 설정하면 [5,0,11,7,8,2]

그래프에서 모든 Node를 포함하면서, Cycle을 형성하지 않는 Tree를 신장트리라고 합니다. 아래 그림을 보면, 하나의 Graph에 대해서 여러가지의 신장트리가 나온는 것을 확인할 수 있습니다. 이때, Node를 이어주는 간선의 가중치(색갈마다 값이 다르다고 생각합시다)가 모두 다르다면, 간선의 총 합을 최소로하는 최소신장트리 가 존재하게 됩니다. Kruskal 알고리즘은 욕심쟁이 방법론을 활용해서 최소신장트리를 구하는 알고리즘 입니다. 알고리즘은 1. 간선의 가중치들을 작은 순서부터 나열한다 2. 나열된 가중치를 하나씩 연결한다 3. Node의 연결상태가 Cycle을 형성하는지 확인하고, Cycle을 형성하면 해당 간선을 Drop한다. 4. 1~3반복 아래는 예시 Graph와 거리행렬 입니다. 이..