ITeus

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와 거리행렬 입니다. 이..

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