ITeus

Floyd알고리즘은 두 노드간의 최단거리를 산출하는 알고리즘을 활용해서, 모든 Node간의 최단 거리를 산출하는 알고리즘 입니다. 다음 예시를 봅시다.A~E까지의 5개의 Node이있고, 서로간에 위와같은 거리가 존재할 때, 해당 상태는 우측과같은 거리행렬로 나타낼 수 있습니다(무한대는 갈수 없다는것을 뜻함) A,C,E의 관계를 봅시다.A->C로 바로 연결되어 있기 때문에 A->C로 가는 거리는 4로 생각할 수 있으나, 최소의 거리는 아닙니다.A->E->C로 이동할 경우 2+1 = 3 이 논리가 Floyd알고리즘의 핵심입니다. 위 논리를 활용해서, 거리행렬을 모두 갱신해주면 알고리즘이 종료됩니다. 시작점(N개)와 끝점(N-1)를 비교하고, 이때 중간점(N-2)의 반복비교가 발생하기 때문에 O(N3)의 시간..

두개의 행렬이 있습니다. A(3,4)행렬과 B(4,2) 행렬을 곱할경우, 위처럼 A Matrix의 Row와 B Matrix의 Col의 Vector 곱을 하게됩니다. 이때 한번의 Vector곱을 하기 위해서 4번의 곱,합 연산이 필요합니다. 때문에 행렬의 곱을 컴퓨터가 계산하기 위해선 4*3*2 = 24번의 곱,합 연산이 발생하죠 두개의 행렬을 곱할때는 한가지 경우만 있지만 행렬이 3개 이상일 경우 행렬곱을 할 수 있는 다양한 경우의수가 발생하게됩니다. (Ex. A,B,C,D 행렬이 있다면 A(B(CD)), (AB)(CD), ((AB)C)D).....) 이 경우 Case에 따라 행렬곱을 계산하기위한 총 연산횟수가 다르게 됩니다. 이번 포스트의 알고리즘은 이 경우 중 최소한의 연산으로 행렬곱을 구하는 알고리..

배열의 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번째 위치가 동일한지 비교한다. == ..

합병정렬 알고리즘은 분할정복방법을 사용한 정렬 알고리즘 입니다. 합병정렬은 정렬을 할 배열을 가장 작은 단위(배열의 Element가 2개만 있을때까지)로 분할하고 분할한 작은 단위의 배열을 정렬하고, 정렬된 배열을 합치고 다시 정렬하는 방법을 사용합니다. 출처 : www.101computing.net/merge-sort-algorithm/ Merge Sort Algorithm | 101 Computing Computers are often used to process large amounts of data. Some of the tasks they can be used for is to sort data sets in order, e.g. numerical order or alphabetical orde..

퀵 정렬은 파이썬의 유명한 Package인 Pandas에서 보셨을 수 도 있습니다. (Pandas DataFrame을 정렬하는 방법중 하나로 쓰입니다) pandas.pydata.org/pandas-docs/version/0.15.2/generated/pandas.DataFrame.sort.html pandas.DataFrame.sort — pandas 0.15.2 documentation columns : object Column name(s) in frame. Accepts a column name or a list for a nested sort. A tuple will be interpreted as the levels of a multi-index. ascending : boolean or lis..

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