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. 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)를 판다. 이 통나무는 길이에 따라 매기는 값이 달라진다.이..
