2JINISHAPPY 2JINISHAPPY

암호화 알고리즘은 암호화/복호화에 사용되는 키, 그리고 양방향 가능 유무를 기준으로 분류할 수 있다. Symmetric-Key Algorithm 대칭 키 알고리즘 대칭 키 암호는 암호화 알고리즘의 한 종류로, 암호화와 복호화에 같은 암호 키를 사용하는 알고리즘을 의미한다. 암호화를 하는 송신자가 평문을 암호화 하고, 해당 암호 키를 공유해서 복호화를 하는 수신자는 암호문을 복원한다. 공유되는 암호 키를 대칭 키라고 한다. 공개 키 암호화 방식과 비교해서 계산 속도가 빠르다는 장점이 있지만, 같은 키를 공유해야 하기 때문에 언젠가 한 번은 키를 전달해야 한다. 이 때, 키를 전송하는 과정에서 정보를 탈취당할 수 있다는 위험성이 있다. Public-Key Algorithm 공개 키(비대칭 키) 알고리즘 암호..

이전에 Biconnected Component와 Cut Vertex에 대해 포스팅한 적이 있다 https://2jinishappy.tistory.com/169?category=903864 무방향그래프에서의 Cut Vertex와 Biconnected Components 우리는 종종 Connected Component에 대해 들어보곤 한다. 주로 BFS 알고리즘 관련 문제를 풀이할 때 등장하는 개념이며, 정확하게는 maximal connected subgraph(가능한 한 connected한 모든 vertex 및 edge를 포.. 2jinishappy.tistory.com 간단히 요약하자면 Cut Vertex: Connected Undirected Graph에서 특정 정점을 제거했을 때 2개 이상의 Conn..

그래프 G 상에서 vertex u에서 v로의 가장 짧은 path의 길이를 찾는 문제를 최단경로 문제라고 한다. 최단 경로 문제는 주로 1️⃣ edge에 weight가 존재하는지 2️⃣ edge weight 범위가 0이상인지/정수인지 3️⃣ 특정 vertex u에서 도달 가능한 path만 구하는지/모든 vertex set에 대해 구하는지 에 따라 사용할 알고리즘을 정하게 된다. 그 중 Dijkstra Algorithm은 edge에 weight가 존재하면서, 범위가 0 이상 이고 특정 vertex u에서 도달 가능한 vertex들의path를 구할 때 사용하는 알고리즘이다. 위 그림과 같은 형태에서 vertex f -> d로의 path는 여러 형태가 존재할 수 있지만, shotest path는 f-b-a-c-..

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이 없..