2JINISHAPPY 2JINISHAPPY

BST(Binary Search Tree)는 아래와 같은 편향 이진 트리(Skewed Binary Tree)일 경우, 성능이 악화된다 Complete Binary Tree일 때 탐색 시간복잡도는 O(log N)이지만, (최악의 경우) 연결리스트의 형태를 한 Skewed Binary Tree일 경우 시간 복잡도가 O(N)에 수렴한다 이러한 편향 현상은 BST에서 Insert, Delete 연산으로 인해 발생할 수 있어서, 이를 보완하기 위한 자료구조로 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)가 존재한다 그 대표적인 예시인 AVL Tree와 Red-Black Tree에서도 아래에서 소개할 Rotation 연산을 이용해서 스스로 Height 균형을 유지하기 때문에..

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

DP를 사용하는 알고리즘들은 처음의 문제를 더 작은 문제로 분할하고, subproblem들로부터 원래 문제의 답을 계산해 나가는, 분할정복과 비슷한 재귀적 문제 해결 방식이다. DP가 분할정복과 구분되는 점은 어떤 부분 문제가 두 번 이상 사용될 시 이를 여러 번 구하지 않고 한 번만 구한 뒤 계산 결과를 재활용 할 수 있다는 특징이다. 이렇게 한 번 계산한 값을 저장해 두었다 재활용하는 최적화 기법을 memoization(메모이제이션)이라 한다 ❗ 1. 문제 정의 조건과 구하고자 하는 바를 정확하게 정의 2. Recursion 정의 정의된 문제에 대한 부분 문제를 정의한 뒤 부분 문제를 이용한 점화식을 세운다 3. DP 적용 - 메모이제이션을 적용하여 점화식 계산 - 중간 계산 값을 저장할 data s..

이전에 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..

Edit Distance 어떤 단어와 '비슷한(가까운)' 단어를 정의하기 위한 Dynamic Programming 알고리즘 Edit Distance : 두 String이 얼마나 가까운지 나타내는 척도 String A와 B 간의 Edit Distance는 'A에서 아래 3가지 type의 연산을 최소한 몇 번 수행하여 B로 만들 수 있는가❓'로 정의된다. Insertion: A에 Symbol 하나를 추가 (ex. excution ➡ execution) Deletion: A에 Symbol 하나를 제거 (ex. mmom ➡ mom) Substitution: A의 Symbol 하나를 다른 Symbol로 교체 (ex. intentien ➡ intention) Edit Example A ..

Loop Invariant(루프 불변량)은 프로그램 루프에서 모든 반복 시의 전후로 변하지 않는 성질을 의미한다. 이것은 반복문의 내용이 실행될 수록 원하는 결과값을 도출하는 과정을 이탈하지 않음을 보이는 특성이다. j = 10 for i in range(0, 10): j-=1 위와 같은 코드에서, loop 중에는 'i+j=10' 이라는 성질은 불변하고, 이것을 loop-invariant라고 볼 수 있다. loop-invariant는 코드가 작동하는 원리를 설명하는 특성이고, 이것이 명확하게 드러나지 않는다면 협업 시 다른 프로그래머가 이해할 수 있도록 도울 수 있는 코드를 작성해야 한다. 이것은 또한 변수간의 긴밀한 관계(루프 시 변하지 않는 성질)를 가지고 있는 iterative(반복) 알고리즘을 설..

Bellman-Ford(벨만 포드) 알고리즘은 Dynamic Programming 기반으로 Edge-Weighted Graph에서 최단거리를 계산하는 알고리즘이다. 특정 Vertex(source)에서 다른 모든 vertex로의 shortest path를 구하며(single-source shortest path), 매 step 마다 해당 shortest path의 distance를 update하는(dynamic) 알고리즘이다. 이 때, 다른 알고리즘과 구분되는 점은 Edge의 Weight가 negative여도 올바르게 동작한다는 점이다. 벨만 포드 알고리즘은 다음의 recurrence relation 아래 작동한다. dist(u) = vertex s에서 u까지의 실제 shortest path의 길이 dis..

그래프 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-..