# 1구역: 피벗(기준 원소)보다 작은 영역
# 2구역: 피벗(기준 원소)보다 큰 영역
# 3구역: 아직 보지 않은 영역


def partition(lst, s, e):
	i = s-1  # 1구역의 끝
	# 2구역은 i+1 ~ j-1
	pivot = A[e]  # 기준원소

	for j in range(s, e-1):  # 3구역의 범위
		if A[j] <= pivot:
			i += 1
			A[i], A[j] = A[j], A[i]  # 1구역을 하나 늘리고, 3구역과 swap
	A[i+1], A[e] = A[e], A[i+1]  # pivot과 2구역 첫번째 원소를 swap
	return i+1  # 2구역의 첫번째 원소를 return (그냥 중앙에 넣어주는 것)


def quick(A, s, e):
	if s < e:
		q = partition(A, s, e)
		quick(A, s, q-1)
		quick(A, q+1, e)


A = [31, 8, 48, 73, 11, 3, 20, 29, 65, 15]
quick(A, 0, len(A)-1)
print(A)

'CS > 알고리즘' 카테고리의 다른 글

Merge Sort in Python (병합 정렬)  (0) 2020.06.09
Insertion Sort in Python (삽입 정렬)  (0) 2020.06.09
크루스칼 알고리즘 (Python)  (0) 2020.05.07
프림 알고리즘 (Python)  (0) 2020.05.07
Call by Value vs Call by Reference  (0) 2020.04.28
import sys


def mergeSort(A, s, e):
	half = (s+e) // 2
	mergeSort(A, s, half)
	mergeSort(A, half+1, e)
	merge(A, s, half, e)


def merge(A, s, half, e):
	tmp = []
	i = s
	j = half+1
	while i <= half and j <= e:
		if A[i] < A[j]:
			tmp.append[A[i]]
			i += 1
	while i <= half:
		tmp.append[A[i]]
		i += 1
	while j <= e:
		tmp.append[A[j]]
		j += 1
	
	i = s
	j = 0
	while i <= e:
		A[i] = tmp[j]
		i += 1
		j += 1


sys.setrecursionlimit(10000)
A = [31, 3, 65, 73, 8, 11, 20, 29, 48, 15]
mergeSort(A, 0, len(A))
print(A)

'CS > 알고리즘' 카테고리의 다른 글

Quick Sort in Python (퀵 정렬)  (0) 2020.06.09
Insertion Sort in Python (삽입 정렬)  (0) 2020.06.09
크루스칼 알고리즘 (Python)  (0) 2020.05.07
프림 알고리즘 (Python)  (0) 2020.05.07
Call by Value vs Call by Reference  (0) 2020.04.28
def insertion(a):
	for cur in range(1, len(a)):  # 인덱스 0까지는 정렬이 되어있다고 치고 1부터 수행
		temp = a[cur]  # 자리를 찾아가려는 원소를 temp에 저장
		prev = cur - 1  # a[cur-1]이 먼저 비교대상이 될 것임
		while 0 <= prev and a[prev] > temp:  # 대소 관계가 맞을 때까지 위치 교환
			a[prev+1] = a[prev]  # 한 칸 뒤로 땡겨
			prev -= 1  # 교환해야 될 애를 더 찾아 나가기 위해 인덱스 1 줄이기
		a[prev+1] = temp  # 마지막으로 비교연산 한 곳+1의 위치에 삽입


arr = [3, 1, 4, 3, 9, 10, 0]
insertion(arr)
print(arr)

# Insertion Sort
# 두번째 원소부터 시작해서/앞에 위치한 애들과 비교를 해서/더 큰 애들을 뒤로 땡긴 후/순서가 맞는 곳에 삽입
# 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더해서 i+1개의 배열을 만드는 과정을 반복한다.
# bubble sort나 selection sort와는 달리 한 개짜리 배열에서 시작해서 그 크기를 하나씩 늘려 나가는 정렬이다.
# 시간복잡도: O(n^2)
# 공간복잡도: n
# 장점: 최선의 경우 O(n)으로 빠르다. 거의 다 정렬이 되어있는 경우 bubble이나 selection sort보다 효율적이다. 
#		추가적인 메모리를 필요로 하지 않는다(in-place). 중복된 원소가 있는 경우 원래 순서를 보장한다(stable)
# 단점: 최악의 경우 O(n^2)로 그닥 효율적이지 않다.

'CS > 알고리즘' 카테고리의 다른 글

Quick Sort in Python (퀵 정렬)  (0) 2020.06.09
Merge Sort in Python (병합 정렬)  (0) 2020.06.09
크루스칼 알고리즘 (Python)  (0) 2020.05.07
프림 알고리즘 (Python)  (0) 2020.05.07
Call by Value vs Call by Reference  (0) 2020.04.28

크루스칼 알고리즘은 최소 신장 트리(MST: Minimum Spanning Tree)를 찾는 알고리즘이다.

프림 알고리즘과 같이 그리디 알고리즘에 속한다.

간선을 가중치 순으로 정렬하고 가중치가 짧은 순서대로 그래프에 포함시키기 때문이다.

 

프림 알고리즘은 비어 있는 트리에 정점을 하나씩 추가시키면서 조금씩 트리의 크기를 키워나가는 방식이었다.

반면 크루스칼 알고리즘은 애초에 모든 정점을 크기가 1인 트리라고 가정한다.

이러한 트리 사이의 간선을 가중치가 작은 순서대로 정렬한 후, 조각조각 간선을 이어 붙여서 최종적으로 하나의 트리로 만들어낸다.

이때 주의점은 정점을 이어붙이는 프림 알고리즘과는 달리 간선을 이어붙이기 때문에 가중치가 작은 순서대로 무조건 간선을 이어붙이다간 사이클이 생길 수가 있다는 것이다.

사이클이 생기면 더이상 트리가 아니기 때문에, 사이클이 생기도록 해선 안된다.

그렇다면 사이클이 생기는 지는 어떻게 알 수 있을까? 직접 노드의 부모를 타고 올라가서 루트가 같은지 확인해야 할까?

처음에는 그렇게 생각했지만, 트리마다 루트를 정해준 후에 두 트리를 합칠 때 루트를 비교하는 방법이 있다는 것을 알게 되었다.

예를 들어보자. A와 B가 결혼하려고 하는데 결혼하기 전에 혹시 A와 B의 집안이 같은 집안인지 확인하고 싶다. 

그럴때 A에게 부모를 물어보고, A의 부모에게 부모를 물어보고, A의 부모의 부모에게 부모를 물어보고...계속 이것을 반복해야 할까? 너무 오래 걸리는 방법이다.

한번에 알아낼 수 있는 방법이 있다. A에게 그의 시조가 누구인지 물어보면 된다.

A의 시조는 ㅇㅇㅇ이고 B의 시조는 ㅁㅁㅁ이니까 두 집안은 다른 집안이야! 이렇게 시조를 저장해놓으면 두 집안이 같은지 O(1)만에 알아낼 수 있을 것이다.

 

여기 코드에서 시조, 즉 루트를 알아내는 함수는 find_set이다. find-set은 집합 처리 부분에서 나오는 그것인데 집합의 루트를 반환한다고 생각하면 된다. 

 

그리고 두 집안이 다르면 결혼을 성사시키는데, 미국의 경우 대부분 여자가 남자의 성을 따라간다.

트리에도 이것을 적용해볼 수 있다. 남자 A의 시조가 스미스 씨였고 여자 B의 시조는 베이커 씨였는데, A와 B가 결혼함으로써 B의 시조가 스미스 씨가 되는 것이다! (실제로는 아니겠지만 크루스칼 알고리즘 사회에서는 그렇다고 치자)

즉, 노드 B의 루트가 A의 루트를 가리키게 하면 된다.

실제로 크루스칼 알고리즘에서 누가 누구를 가리킬 것이냐에 대해서는 그저 한 가지 기준을 정하면 되지만 여기서는 노드의 숫자가 큰 것이 → 작은 것을 가리키게 하는 방법을 썼다.

 

여기 코드에서 두 트리를 병합하는 함수는 union_set이다.

 

갑자기 생각난건데, 전 세계 인구를 족보 순으로 가장 가까운 순으로 연결시켜서 하나의 족보로 만든다면 그것이 크루스칼 알고리즘이 아닐까?

 

# 크루스칼 알고리즘


# 모든 간선의 정보를 저장할 클래스. a는 한 쪽 노드, b는 다른 한 쪽 노드이며 dist는 a와 b 사이의 가중치(거리)이다.
class Edge:
    def __init__(self, a, b, dist):
        self.a = a
        self.b = b
        self.dist = dist


# 루트 노드를 반환하는 함수.
# 루트 노드를 구할 때 그냥 root[x]해도 되겠지만 집합 처리 개념을 사용하기 위해 함수로 따로 빼냈다.
def find_set(x):
    return root[x]


# 두 트리를 병합하는 함수. 일관성을 위해 노드 번호가 더 작은 것을 루트로 만든다.
def union_set(a, b):
    a = find_set(a)
    b = find_set(b)
    if a < b:
        root[b] = a
    else:
        root[a] = b


# edges에는 [정점 a, 정점 b, a-b 사이의 거리]를 담은 Edge 객체들이 저장되어 있다.
edges = list()
edges.append(Edge(1, 7, 12))
edges.append(Edge(1, 4, 28))
edges.append(Edge(1, 2, 67))
edges.append(Edge(1, 5, 17))
edges.append(Edge(2, 4, 24))
edges.append(Edge(2, 5, 62))
edges.append(Edge(3, 5, 20))
edges.append(Edge(3, 6, 37))
edges.append(Edge(4, 7, 13))
edges.append(Edge(5, 6, 45))
edges.append(Edge(5, 7, 73))

n = len(edges)
root = [i for i in range(n)]  
# 모든 트리의 루트를 저장. 맨 처음에는 노드가 하나의 트리이므로 자기 자신이 루트이다.

total = 0  # 최단 거리

edges.sort(key=lambda x: x.dist)  # 우선 간선을 가중치 순으로 정렬. 가중치가 작은 순으로 순회

for edge in edges:  # 모든 간선에 대해서 반복한다.
    if find_set(edge.a) != find_set(edge.b):
    # 두 노드가 포함된 트리의 루트가 서로 다를 때(=두 트리를 합쳐도 사이클이 생기지 않을 때)
        union_set(edge.a, edge.b)  # 두 노드(가 포함되어 있는 트리)를 병합
        total += edge.dist
print(total)

'CS > 알고리즘' 카테고리의 다른 글

Merge Sort in Python (병합 정렬)  (0) 2020.06.09
Insertion Sort in Python (삽입 정렬)  (0) 2020.06.09
프림 알고리즘 (Python)  (0) 2020.05.07
Call by Value vs Call by Reference  (0) 2020.04.28
Selection Sort (선택 정렬)  (0) 2020.04.24

신장 트리는 그래프 G=(V, E)에서 간선을 V의 갯수-1개만 남겨서 트리로 만든 것을 말한다. (V=vertex, E=edge)

최소 신장 트리(MST: Minimum Spanning Tree)는 간선들이 가중치가 있는 그래프에서 간선 가중치의 합이 가장 작은 트리를 말한다.

프림 알고리즘은 이러한 최소 신장 트리를 찾는 방법 중 하나로, 그리디 알고리즘에 속한다.

 

 

# 프림 알고리즘

INF = float('inf')

# 각 정점 사이의 가중치가 주어진다.
weight = [[0, 7, INF, INF, 3, 10, INF],
          [7, 0, 4, 10, 2, 6, INF],
          [INF, 4, 0, 2, INF, INF, INF],
          [INF, 10, 2, 0, INF, 9, 4],
          [3, 2, INF, INF, 0, INF, 5],
          [10, 6, INF, 9, INF, 0, INF],
          [INF, INF, INF, 4, 5, INF, 0]]

# 집합 S: 최종적으로 만들어질 트리. 처음에는 아무것도 포함되지 않았다고 가정한다.
# 프림 알고리즘에서는 모든 정점에 대해 S와의 거리를 저장한 dist라는 배열을 두고, 이 중 가장 가까운 정점을 S에 하나씩 포함시킨다.
# 새로 포함된 정점 때문에 그 정점에 인접한 점들은 S에 포함될 수 있는 최단거리가 갱신될 수 있으므로 확인 후 갱신한다.

V_NUM = len(weight[0])
dist = [INF for _ in range(V_NUM)]  # 모든 정점에 대해서 집합 S와의 최단거리. 처음에는 모두 무한대라고 가정한다.
selected = [False for _ in range(V_NUM)]
dist[0] = 0  # 시작 정점을 선택하고 S에 포함하고, 거리가 0이라고 가정한다. (프림 알고리즘의 시작)

for _ in range(V_NUM):  # 정점의 갯수만큼 반복

    unselected = [idx for idx, val in enumerate(selected) if not val]
    u = min(unselected, key=lambda x: dist[x])
    # u=아직 집합 S에 포함되지 않은 정점 중에서 집합에 연결되기 위해 최소 비용이 드는 점을 구한다.

    selected[u] = True
    print(u)  # S에 포함된 점

    for v in range(V_NUM):
        if weight[u][v] != INF:  # u와 연결된 정점 중에서
            if not selected[v] and weight[u][v] < dist[v]:
                # S에 포함되지 않은 정점 중에서,
                # 이미 알려진 길(dist[v])보다 더 가까운 길로 갈 수 있으면(weight[u][v]) 갱신한다. 다음에 방문하기 위해서..
                dist[v] = weight[u][v]

https://mattlee.tistory.com/46 를 참고하였음

 

 

'CS > 알고리즘' 카테고리의 다른 글

Insertion Sort in Python (삽입 정렬)  (0) 2020.06.09
크루스칼 알고리즘 (Python)  (0) 2020.05.07
Call by Value vs Call by Reference  (0) 2020.04.28
Selection Sort (선택 정렬)  (0) 2020.04.24
Bubble Sort (버블 정렬)  (0) 2020.04.24

Call by Value

함수를 호출하면 그 함수의 지역변수를 할당하기 위해 스택 프레임이 생성되는데, 이 공간은 함수가 종료되면 사라진다. Call by Value로 값을 전달하는 것은 변수의 값을 복사해서 전달하는 것이다. 이 복사된 값은 함수가 종료되어 스택 프레임이 사라질 때 지역변수와 같이 사라진다. 따라서 함수 안에서 값이 변경되어도 외부에 있는 값은 변경되지 않는다.

 

 

Call by Reference

Call by Reference로 값을 전달하면 변수의 주소를 전달하게 되고, 함수 안에서 주소를 이용해 값을 변경하면 외부에 있는 값도 같이 변경된다.

 

 

Call by Assignment

파이썬에서 사용되는 방식으로, 함수에 immutable(int, float, string, tuple)한 객체를 전달하면 Call by Reference로 전달이 되나, 이를 변경하면 Call by Value로 변경되어 외부 값에 영향을 주지 않는다. 반면 mutable(한 객체를 전달하면 자동으로 Call by Reference로 전달이 된다.

'CS > 알고리즘' 카테고리의 다른 글

Insertion Sort in Python (삽입 정렬)  (0) 2020.06.09
크루스칼 알고리즘 (Python)  (0) 2020.05.07
프림 알고리즘 (Python)  (0) 2020.05.07
Selection Sort (선택 정렬)  (0) 2020.04.24
Bubble Sort (버블 정렬)  (0) 2020.04.24

# Selection Sort
# 앞에서부터 원소를 하나씩 선택한 후, 그 뒷부분에서 최솟값을 찾아 그 둘을 swap하는방식으로 정렬하는 방식
# 시간복잡도: O(N^2) <- N(N-1)/2
# 공간복잡도: n
# 장점: 비교횟수는 많지만 bubble sort에 비해 자리를 교환하는 횟수가 적어 많은 교환이 일어나야 할 때(정렬이 많이 이루어져야 할 때) 효율적
# 추가 메모리를 필요로 하지 않는다(in-place). 
# 단점: unstable하다.

 

Python

def selection_sort(lst):
    for i in range(len(lst)-1):  # i = 정렬할 자리. 맨 마지막은 안 봐도 됨
        min_idx = i  # min_idx 은 i와 swap할 원소
        for j in range(i+1, len(lst)):
            if lst[min_idx] > lst[j]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]  # i 자리에 min_idx의 원소를 넣고 swap
    return lst

arr = [3, 9, 3, 1, 5]  # unstable의 예
print(selection_sort(arr))

 

Javascript

function selection_sort(arr) {
    for (let i=0; i<arr.length-1; i++) {
        let min_idx = i;
        for (let j=i+1; j<arr.length; j++) {
            if (arr[min_idx] > arr[j]) min_idx = j;
        }
        let tmp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = tmp;
    }
    
    return arr;
}

'CS > 알고리즘' 카테고리의 다른 글

Insertion Sort in Python (삽입 정렬)  (0) 2020.06.09
크루스칼 알고리즘 (Python)  (0) 2020.05.07
프림 알고리즘 (Python)  (0) 2020.05.07
Call by Value vs Call by Reference  (0) 2020.04.28
Bubble Sort (버블 정렬)  (0) 2020.04.24
def bubble(lst):
    for i in range(len(lst)-1):
        if lst[i] > lst[i+1]:
            lst[i], lst[i+1] = lst[i+1], lst[i]
	

a = [3, 1, 5, 9, 7, 10]
bubble(a)
print(a)
	

# Bubble Sort
# 서로 인접한 두 원소의 대소를 비교해가면서 자리를 교환해 정렬하는 방식
# 시간복잡도: O(n^2)
# 공간복잡도: n
# 장점: 구현이 쉽다. memory가 추가로 들지 않는다(in-place). 중복된 값들이 있을 경우 원래 순서를 보장한다(stable).
# 단점: 정렬이 되어 있건 안 되어 있건 무조건 비교 연산을 수행하기 때문에 수행시간이 무조건 n^2이다.

'CS > 알고리즘' 카테고리의 다른 글

Insertion Sort in Python (삽입 정렬)  (0) 2020.06.09
크루스칼 알고리즘 (Python)  (0) 2020.05.07
프림 알고리즘 (Python)  (0) 2020.05.07
Call by Value vs Call by Reference  (0) 2020.04.28
Selection Sort (선택 정렬)  (0) 2020.04.24

+ Recent posts