Awesome

인스턴스 변수: 클래스 바로 안쪽에 위치하며, 인스턴스가 생성되었을 때 실제 메모리가 할당된다.

클래스 변수: (=static 변수). 인스턴스 변수에 static을 붙이면 클래스 변수가 된다. 클래스 바로 안쪽에 위치하며, 해당 크래스로 만들어진 모든 인스턴스가 공유하게 되는 변수이다. 클래스이름.클래스변수와 같이 인스턴스를 생성하지 않고도 사용할 수 있다. 프로그램이 종료될 때 사라지며, 앞에 public을 붙이면 전역 변수와 같아진다.

인스턴스 변수와 클래스 변수를 멤버 변수라고 한다. 

지역 변수: 클래스->메서드 내에 선언됨. 블럭을 벗어나면 소멸함.

class Variables
{
    int n;  # 인스턴스 변수
    static int m;  # 클래스 변수 (Variables.m으로 바로 사용 가능)
    
    void method()
    {
    	int k = 0;  # 지역 변수
    }
}

# 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)

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)

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)로 그닥 효율적이지 않다.

스위칭의 필요성

모든 장치에 서로 링크를 연결하는 것은 문제가 있다.

장치가 많아질수록(큰 네트워크일수록) 링크가 많이 필요해져 비용이 많이 들기 때문이다.

또, 링크의 대다수가 유휴시간이 많아져서 효율이 떨어진다.

→ 스위치를 두어서 여러 장치들을 이 스위치에 연결되도록 구성하고, 스위치가 그때 그때 필요할 때마다 두 개의 장치를 연결시켜주도록 한다.

스위칭이란?

그때 그때 필요할 때마다 송신자와 수신자를 연결시켜 주는 것

링크를 효율적으로 사용하고, 비용을 줄이기 위해 나타난 것이 스위치

스위치들이 연결되어 큰 규모의 네트워크를 만들 수 있다. 

스위칭 방식의 종류

1. 회선 교환

- 두 장치 사이에 물리적인 선을 연결하는 방식. 전화망(PSTN: Public Switched Telephone Network)

- 회선이 연결되면 데이터를 주고 받는 동안 계속 유지된다. 즉, 자원이 연결되어 있는 동안 계속 점유된다.

- 두 장치 사이에 고정된 속도를 갖는다.

- 연결을 설정하는데 시간이 소요되고, 그 이후에는 지연시간이 없다.

- 데이터 전송이 많은 경우 유용하다.

2. 메시지 교환

- 전달할 메시지 전체를 한 번에 인접 노드에게 모두 보낸다(메시지 단위로 스위칭). 메시지를 수신한 노드는 다음 노드로 메시지를 전달한다(Store and forward).

- 유휴 링크는 다른 메시지 전송에 쓸 수 있어서 효율적이다.

- 단점은 각 노드가 메시지를 저장할 공간을 확보하고 있어야 한다. (→패킷 교환의 등장)

3. 패킷 교환

- 전체 메시지를 각 노드가 수용할 수 있는 크기(패킷)로 잘라서 보내는 방식

- 한 순간에 트래픽량이 확 늘어나는 형태(bursty)에 적합하다.

- 전송 속도를 다르게 해서 우선순위 적용이 가능하다.

- 링크에 문제가 발생하면 중간에 다른 링크를 선택할 수 있다.

1) 데이터그램(Datagram) 방식

- 패킷 단위로 잘라서 보내는 것.

- 각 패킷이 서로 상관없이 독립적으로 처리 된다. 따라서 연결 설정 과정이 없다.

- 각 패킷이 서로 연관성이 없기 때문에 목적지에 순서와 상관없이 도착할 수 있다.

- IP

2) 가상회선(Virtual-circuit) 방식

- 데이터를 보내기 전에 연결 설정을 한다. 연결 설정을 할 때 가상 회선(경로)가 정해지고, 그 순서로만 전송된다. 즉, 동일한 경로로 순서대로 목적지에 도착한다.

- 회선 교환과의 차이점은 경로를 남들과 공유할 수 있다는 것이다.

2-1) SVC

- 가상 회선이 필요할 때만 연결되는 것

2-2) PVC

- 가상회선이 이미 연결 설정이 되어 있어 연결 설정이 없다.

크루스칼 알고리즘은 최소 신장 트리(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)

신장 트리는 그래프 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 를 참고하였음

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로 전달이 된다.