clrs

1. B-tree?- B-tree는 Tree Data Structure의 일종으로 Binary Tree를 확장하여, - 하나의 노드의 차수의 최댓값이 2보다 큰 Tree 라고 말 할 수 있다.https://velog.io/@emplam27/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-B-Tree [자료구조] 그림으로 알아보는 B-TreeB트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리입니다.velog.io- B-tree에 대해 자료를 수집하는 중, 가장 정리가 잘된 블로그를 공유한다. - B-tr..

1. Amortized Analysis?- 분할 상환 분석(Amortized Analysis)에 대해서 알아보자.- Amortized Analysis는 알고리즘의 시간 복잡도를 분석하는 방법 중 하나로, 특정 연산의 평균 실행 시간을 계산하는 데 초점을 둠- 이는 최악의 경우 시간 복잡도를 항상 고려하는 Worst-case Analysis와 달리, 일련의 연산이 여러번 반복되는 경우 전체 작업에 대한 총 수행 시간을 분석하여 ''연산당 평균 비용''을 구하는 데 초점을 맞춘다. 2. Amortized Analysis가 필요한 이유- 어떤 데이터 구조나 알고리즘에서는 일부 연산이 매우 비싸지만, 다른 연산들은 거의 비용이 들지 않는 경우가 있다.ex) 동적 배열, Hash table...- 이때 단순히 최..

1. Greedy Algorithm?- 매 순간 국소적인 최적해를 찾는 과정을 반복함으로써 전체 문제에 대한 해를 찾는 문제 해결의 한 패러다임- Greedy Algorithm으로 얻은 해가 전체 문제에 대해 반드시 최적의 해라는것을 항상 보장 불가 2. Greedy Algorithm의 최적해를 가질 때2.1. ex 1) 거스름 돈(각각의 동전들이 배수관계)https://www.acmicpc.net/problem/11047n, k = map(int,input().split())cost = list(int(input()) for _ in range(n))cnt = 0 for _ in range(n): p = cost.pop() cnt += k//p k = k%pprint(cnt) 3. 결론..

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