1. Longest Common Subsequence(LCS)- LCS에 대해서 알아가기 전에 substring과 subsequence의 차이에 대해서 알아보자.- substring : 연속된 부분 문자열- subsequence : 연속되지 않은 부분 문자열 - 여기서 LCS는 subsequence가 최대길이를 가질때를 알고 싶기에 나오게 된 개념이다.2. LCS 구하기- DP로 효율적으로 문제를 해결 가능하다.- LCS는 2개의 문자열을 비교하여 최장인 subsequence를 구해야한다.- 문자열 'BDCABA' 와 'ABCBDAB'가 있다고 생각해보자.- 여기서 하나의 문자열을 기준 문자열, 다른 문자열을 비교 문자열로 가정한다.- 위 표를 보면 문자열 맨 앞에 0을 추가해주었다.- 첫번째 행에 A값..
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..
