2JINISHAPPY 2JINISHAPPY

MST를 생성하는 방법에는 Kruskal, Prim 두 가지 알고리즘이 존재한다. Kruskal 알고리즘을 빠른 시간 내에 동작하게 하려면 Union-Find 자료구조(라이브러리가 없기에 직접 구현해야함)를 사용해야 한다는 번거로움이 있지만, 여기에서 다룰 Prim's Algorithm은 priority queue를 가지고 구현할 수 있다. Prim's Algorithm을 관통하는 가장 중요한 property를 정의하고 가자. Cut Property: Edge e = (u,v)는 MST의 edge set T에 속해 있다 ↔ e는 vertex u를 포함한 어떤 vertex set S와 v를 포함한 V(G) - S를 이어주는 edge들 중 제일 cost가 작다 (오른쪽 그림, ←)MST가 위에서 설명한 e ..

이전에 MST(Minimum Spanning Tree)에 대해 다룬 적이 있다. Weighted Connected Graph에서는 edge의 cost 합이 최소가 되게 하는 Subgraph(Tree)를 구성할 수 있고, 이를 MST라고 한다. 이러한 MST를 생성하는 대표적인 알고리즘으로는 Kruskal(크루스칼), Prim(프림)알고리즘이 있다. Kruskal's Algorithm(Greedy) : 그래프 G의 MST를 이루는 edge set을 T라고 가정한다. 각 step마다 T에 추가해도 cycle이 생기지 않는 edge들 중 cost가 가장 작은 edge를 T에 추가한다. 이 과정을 MST가 완성될 때 까지 반복한다. 이와 같이 T에 새로운 edge e를 추가해도 spanning tree의 성질이..

우리는 종종 Connected Component에 대해 들어보곤 한다. 주로 BFS 알고리즘 관련 문제를 풀이할 때 등장하는 개념이며, 정확하게는 maximal connected subgraph(가능한 한 connected한 모든 vertex 및 edge를 포함해야하며, 하나라도 더 추가한 순간 disconnected해야한다)를 의미한다. 여기에서 사이클에 대한 조건을 추가한 개념이 Biconnected Component(BCC)라고 할 수 있다. 위의 그림과 같은 무방향 간선 (연결) 그래프가 있다고 가정하자. 이 상태에서 vertex A 및 A와 연결된 모든 edge를 삭제하면 그래프는 (D,G,H)와 (B,C,E,F,I,J)로 분리된 disconnected graph가 된다. 이렇게 해당 그래프에서..

1. Bubble Sort : 인접한 원소끼리 대소를 비교하고 swap시켜 unsorted part중 가장 작은(sort priority가) element를 sorted part의 직전에 위치시키는 정렬 bubbleSort(A[1 ... N], N): for i in [1 ... N]: for j in [1 ... N-i]: if A[j] > A[j+1]: swap A[j] and A[j+1] bubble sort의 validaity: i번째 stage 후에 Array에서 i번째로 큰 값은 항상 A[n-1-i]번째에 위치하게 된다(loof invariant). 즉, 정렬되어 위치해야 할 올바른 위치에 자리잡게 된다. time complexity: O(N²) i번째 stage에서 가장 큰 element를 ..

그래프의 Vertex에는 순서가 있을까? 대학교의 전공 과목에는 선수 과목이라는 것이 존재한다. 특정 과목을 수강하기 위해서는 해당 과목의 선수 과목을 먼저 수강해야 하는 것이다. 이러한 관계를 이용해서, Topological Sort를 이용하면 올바른 수강 순서를 얻어낼 수 있다. 우리는 Vertex의 정렬 기준을 In-degree, Out-degree의 차수로 나타내어 Sorting Algorithm을 정의해볼 수 있다. Topological Sort: Directed(방향이 있는) Graph G에서 모든 Vertex를 정렬한 것. Vertex 정렬 기준: 임의의 vertex u, v가 있을 때 edge(u,v)가 존재할 경우 vertex u는 vertex v보다 순서가 앞이다. 오직 Cycle이 없..

Cache란 컴퓨터 과학에서 사용하는 '데이터를 미리 복사해 놓는 임시 저장 장소'를 말한다. 원래의 메모리에 접근하는 시간이 오래 걸리거나 값을 재 계산하는 시간을 절약하기 위해 사용한다. 캐시에 미리 값을 복사해 놓는 경우에 빠른 속도로 데이터에 접근할 수 있다. 물론 캐시도 물리적 메모리 영역을 가지고 있기 때문에, 유한한 공간을 가진다. 제한된 메모리 영역을 효율적으로 이용하기 위해서는 자주 사용하는 데이터는 빠르게 접근할 수 있도록 하고, 오래 사용되지 않은 데이터는 캐시 영역에서 쫓아버리는 방법을 사용한다. 이러한 캐시 메모리를 관리하는 알고리즘을 LRU(Least Recently Used) Algorithm이라고 한다. 해당 알고리즘은 가장 오랫동안 참조되지 않은 데이터는 앞으로도 사용될 확..

postfix란 뭘까 수식의 종류에는 prefix, infix, postfix 세 가지가 존재한다 이것은 연산자가 피연산자들 사이에서 어느 위치에 존재하느냐에 따라 나뉜다 우리는 일상생활에서 99.999999% Infix 방식을 이용해서 표기한다. 하지만 Infix방식에는 문제점이 존재한다 5+4*3 이라는 수식이 존재할 때, '*' 연산자가 '+' 연산자보다 우선순위가 높기 때문에 해당 수식을 먼저 계산해줘야 한다 하지만 이것은 계산을 하는 사람이 모든 수식을 차례로 읽은 뒤, 연산 순서를 임의로 정해야 한다. 그렇기 때문에 순차적으로 입력을 받고 이를 해결하는 컴퓨터의 계산 방식과는 약간 다르다. 컴퓨터는 postfix 연산 방식을 선호한다. 위의 수식을 postfix로 전환하면, 5 4 3 * + ..

우리가 정말 많이 사용하는 재귀함수 처음에는 개념과 구현이 조금 헷갈리지만, 시간이 지나면 이만큼 편한게 없다 하지만 재귀함수를 구현할 때에는 몇 가지 주의할 점들이 있고, 이를 지키지 않으면 수많은 오류가 발생할 수 있다 재귀: 특정 개념 or 함수를 정의할 때 자기 자신을 이용하는 방법 ex) 내 연봉은 1년에 천만원씩 증가하고, 입사 첫 연봉은 1억원이었다. 이 경우 현재 나의 연봉은 (작년 연봉 + 천만원)이며, 입사 몇년차인지에 따라 연봉 금액이 달라진다. 현재 연봉을 정의하는 데에 작년 연봉을 이용하는 이러한 예시가 재귀라고 할 수 있다. 재귀를 처음 학습할 때 참고하는 대표적인 예시 두 가지가 있다 그것은 바로 Factorial과 Fibonacci 1️⃣ Factorial: 어떤 자연수 n에..