목록3학년 1학기/알고리즘 (Algorithm) (27)
오래 못 할 짓 하지 않기
[ 알고리즘 ] 5. DP - MCM 알고리즘
MCM = Multiply Chain Matrix ▶ 행렬들을 곱할 때 어떤 순서로 곱해야 최소한의 연산을 하는지 구하는 알고리즘 [ 1,3 ] 에 표시되어 있는데 이는 A1, A2, A3까지 곱했을 때 최소한의 연산을 하는 값이 들어가있다. 만약 [1,4] 에 표시가 되어있다고 했을 떈, [1,3] * [ 4 ,4 ] 의 값이 [ 1,4 ]에 들어간다. 이 때 [1,3]의 값은 (새로 계산하는 것이 아니라) 이전에 계산해서 구했던 [1,3]의 최소 연산값을 참조해서 사용한다. A3 * A4 * A5 * A6을 곱하는 [ 3, 6 ] 은 위와 같이 3개의 경우의 수로 나눌 수 있다. 이 때 [ 3, 6 ] 에는 저 3가지 경우에서 가장 Optimal한 값이 들어간다. * A3 ~ A5 까지의 연산에서 O..
[ 알고리즘 ] 4. Dynamic Programming
https://min-h-study-review.tistory.com/266Dynamic Programming알고리즘X디자인 패러다임이다. ● 언제 사용되느냐? : Optimization 문제에서 사용된다. ex) Minimization / Max..~ → 최단 경로 찾기,Job scheduling 과 같이 선택해야 하는 문제에 쓰인다. ● 방법하나의 큰 문제를 Dynamic한 여러 작은 문제로 나누어서 푼다.S라는 큰 문제 하나를 S1,S2,S3...Sm으로 나눈 뒤, 그들을 합한다. 이러면 Divide and Conquer 랑 다를 게 없어보이는데, 차이점으로는 DP는 가장 작은 케이스에서부터 시작한다는 것이다. - 공통점 : 작은 문제를 통해 큰..
[ 알고리즘 ] 3-1 문제 풀이
문제 1 1. Recursion Tree 그리기위와 같은 형태로 나온다. ● 특정 Level a에서의 node의 개수 = 2^a 개 ● Tree 높이 = T(n)이 그 다음 단계에서 얼만큼 줄어드는지 보면 된다. = T(n/2) = 이런 경우에 마지막 높이일 때 줄어들어 있는 정도는 [ n/2^마지막 높이 ] 일 것이다. → n / 2^h = 1 → h = log2 n ● 각 레벨별 합 lv 0 : cn log (n) lv 1 : cn log (n/2)lv 2 : cn log (n/4)...lv h : cn log (n/2^log2 n) = cn * {..
[ 알고리즘 ] 3. Divide and Conquer
● Recurrences : 현재 주어진 함수를 더 작은 함수로 쪼개서 설명하는 방법 방법 1) Substitution Method : 푸는 방법이라기보단 알고있는 게 맞다는 걸 증명하는 방법 방법 2) Recursion - tree : Recursion tree를 만든다. - 각각의 node는 또 다른 작은 문제를 담고있다. → 각 Level의 cost를 합한다. → 모든 Level의 cost를 합한다. 이거 직접 손으로 풀어보기 T(1)은 constant한 값이다. 트리에 있는 Node의 합을 구하기 위해서는 Height를 알아야 한다. 각 레벨마다 Sum을 구했으니 그걸 다 더한다. 각 층을 내려갈 때마다 c뒤에 붙는 것의 분모가 1/4이 됨. = 등비수열의 합 ▼ 풀이 더보기 방법 3) Itera..
[ 알고리즘 ] 2. Function 성능 관련 문제
f(n) =< c g(n)이라고 할 때 5n^2 = O(n^3) 라고 가정하면 n과 c가 어떻게 되어야 하는가? 현재 형태를 식에 맞춰보면 0 ≤ 5n^2 ≤ c * n^3 이렇다. 0 ≤ f(n) ≤ c * g(n) c가 어떻게 되든 g(n)의 계수가 작아지지 않고 n이 어떤 상수가 되든 f(n)의 계수가 커지지 않으므로 답은 무수히 많다. 질문 : C도 고려를 해야하나? 상수는 떼고 그냥 차수만 생각하면 되는 거 아니었음? 2번 문제 풀기 전에 Notation 사이에 =가 있고 f(n) = g(n)이런 꼴이라면 → f(n)은 g(n) 노테이션 종류에 속한다. 1) O - O(n^3)는 5n^2보다 크거나 같다. 2) X - 위에 설명했으니 패스 3) n^2 + cn = O(n^2) 맞음 4) 5) 같..
[ 알고리즘 ] 1. Function 의 성능 분석
함수 f(n)의 성능을 분석하는 방법으로는 다음과 같이 5개가 있다. 우리가 주로 볼 것은 Theta 와 Big - O 이다. ● Theta는 f(n)과 g(n)의 성능이 비슷비슷할 때를 의미하고 ● Big-O는 f(n)의 성능이 g(n)의 성능보다 같거나 낮을 때를 의미한다. n이 무한대일 때 [ f(n) / g(n) ] 의 값이 무한대가 아니라면 f(n) = O(g(n))이라고 할 수 있다. ( *예를 들어 f(n) = 2n^2 / g(n) = n^3 일 때 값은 0이다.) O-notation은 주로 f(n)의 upper bound를 나타낸다. 이거를 이해해보려면 O(n^2) 일 때 여기에 속하는 집합 f(n)으로는 { n^2 , 2n^2 -1 , 100n^2 , n , log n , }이 있다. n..
[ 알고리즘 ] 다이나믹 프로그래밍 (DP)
우선 재귀함수에 대해 이해를 하고 가야한다. 피보나치 수열로 예를 들어보자 15번째 값을 구하려면 14,13번째 값을 알아야한다. 14번재 값을 구하려면 13,12번째... 이렇게 13번째 연산이 반복된다. 재귀함수는 이미 해결한 문제를 다시 반복해서 해결하기 때문에 비효율적이다. 이럴 떈 다이나믹 프로그램을 사용한다. 단, 가정이 필요하다. 1. 큰 문제를 작은 문제로 나눌 수 있다. 2. 작은 문제에서 구한 정답은 그걸 포함하는 큰 문제에서도 동일하다. 우선 피보나치 수열을 예시로 분석해보자 [ 재귀 함수 ] 이렇게 구현하는 경우에는 했던 계산을 또 해야하는 비효율성이 생기고 그로 인해 시간이 오래 걸리므로 필요가 없다. [ 다이나믹 프로그래밍 ] int d [ 100 ]; if ( d [ x ] !..