CS Study/CLRS (자료구조 | 알고리즘)

1. Matrix Multiplication (행렬곱)- 많은 사람들은 알겠지만, 행렬 곱에 대해서 알아가보고 넘어가보자.- 다음과 같이 행렬 곱을 할 때, (m x k) x (k x n) = (m x n) 꼴로 연산이 되게 된다.- 여기서 핵심은 k처럼 동일한 숫자가 있어야 한다는 것이다.- 이를 계산하기위해 3중 for문을 이용한 행렬곱 알고리즘을 이용한다고 생각했을 때 , 연산 횟수는 m*k*n 이된다.  2. Matrix Chain Multiplication- 만약 행렬곱이 연속적으로 주어져 있다고 가정하자.- A*B*C*Dcf) A : 5x4 , B. 4x6, C : 6 x 2 , D : 2x7- 행렬 곱은 결합법칙이 성립하기 때문에 계산할 수 있는 방법은 다음과 같다. '''i) (((AB)C..

1. Intro- dynamic programming은 특정한 알고리즘이라기 보단, 기법이라고 하는게 맞다.- DP는 복잡한 문제를 재귀적인 문제로 간단한 subproblems로 나누어 해결하는 기법이다.- 마치 divide-and-conquer(분할-정복)과 유사해보인다.- 하지만, 그 과정에서 subproblem이 중복이 되는 경우가 많기에, 이전에 수행한 연산결과를 재활용한다.- 즉, Dynamic Programming은 "저장하며 풀기"정도로 기억하면 좋다. 2. Rod Cutting Problem- Rod Cutting 문제에 대해서 알아보자.- Rod Cutting은 다음과 같은 문제를 의미한다. Q) 어떤 가치를 지닌 통나무(Rod)를 판다. 이 통나무는 길이에 따라 매기는 값이 달라진다.이..

1. Intro- RBTree는 노드의 속성중 색상을 정의하여 Red or Black으로 나타낸 후, BBST를 유지한다는 독특한 개념의 트리라고 말할 수 있다.- 이러한 RBTree는 탐색, 삽입,삭제 연산의 수행시간이 O(logN)을 넘지않는 특징을 가진다. 2. RBTree의 문제점- RBTree에 대한 설명은 13-2에서 했고, 이러한 RBTree의 문제점은 BBST를 유지하기 위해 까다로운 조건들을 고려해야한다는 것이다.- 그로인해, 프로그램이 복잡해지고, 길이는 증가한다. 즉, 프로그래머가 상대적으로 더 많은 노력을 하게 된다.- 이러한 RBTree을 간단하게 구현하고자 나온게 바로 LLRBTree이다.  3. LLRB Tree(Left-Leaning Red-Black Tree)- 일반적인 R..

1. Red-Black Tree?- Red-Black Tree는 균형 이진 탐색 트리(BBST)의 한 종류로, 삽입과 삭제 연산 후에도 트리가 균형상태를 유지- 이진 탐색 트리의 시간복잡도를 O(log n)으로 보장함- 각 노드에 색깔 속성을 추가하여, BBST를 만족하도록 트리를 유지함- 현재 포스팅에선 RB-Tree을 구현하진 않을 것이고, 그 다음 포스팅 LLRB Tree을 설명할 때 그때 구현하고자 한다.2. RBTree의 특징I) 노드는 Red or Black이다.II) Root Node는 항상 Black이다.III) Red 노드의 자식 노드는 모두 Black이다.--> No Double RedIV) 모든 leaf node는 모드 Black이다.V) Root에서 left node까지의 Black..