- 활동일시
일시 : 2022.10.17(월) 18:00 ~ 20:00 (총 2시간)
- 오늘의 계획
- 알고리즘 공부
- Divide-and-conquer
- Master Theorem
- 오늘의 활동
1) Divide-and-conquer
Divide-and-conquer (분할정복) 이란? : Divide(분할) + conquer(정복)
1) 주어진 문제를 subproblem으로 쪼갠다. 이 때 subproblem은 input size가 작은 원래 문제를 뜻함. -> Divide
2) 1번에서 나눈 subproblem 들을 (recursive하게) 해결한다.
3) 2번에서 푼 subproblem 들의 답을 적절하게 조합 (combine, merge) 해 본 문제 해결.Basecase ---(해결)---> 전체 case
2) Master Theorem
Input size가 n일 때 divide-and-conquer 알고리즘의 일반적 패턴
1) 문제를 size가 n/b인 a개의 subproblem으로 recursive하게 나눈다.
2) 각각의 subproblem 을 해결한 뒤, O(n^d) 시간을 사용하여 bsubproblem의 답을 merge한다. (이때 a, b, d > 0).
T(n) = aT(n/b) + O(n^d)
일반해 T(n)은 다음과 같다.
- 활동 소감
오늘은 알고리즘 중 divide-and-conquer에 대해 공부했다. 저번학기 자료구조 시간에 들어보고, 개인적으로 공부했을 때 들어본 divide-and-conquer을 공부해보니 좋았다. 분할 후 정복해 나가는 알고리즘인 것은 알고 있었지만 이것이 세부단계는 어떻게 진행되고, 이렇게 분할해 해결하는 것이 얼마나 좋은 시간복잡도를 가지고 있는지 알지는 못했었다. 오늘 이렇게 공부하면서 divide-and-conquer이 어떻게 이루어지는 알고리즘인지 알게 되었다. (계속해서 공부하는 단계지만 아직까지 Big-Oh 표기를 통해 시간복잡도를 구하는 것은 너무 어렵다..ㅠㅠ)
