I about me

- Uneven Split 단답형, 객관식 문제 출제 예정- Selection Problem- Proof 를 전부 알 필요는 없지만... 과제를 관련 문제를 내주셔서... Problem 3 - 10번 문제 + 강노 풀 것! Uneven Split  Theorem 1nαn (1 - α) n  // 0 α ≤ 1/2  // 위의 회색 참고  Theorem 2nαn(1- α-β)nβn Selection 문제문제: k번째를 숫자가 뭐야?https://bblackscene21.tistory.com/10 [ 알고리즘 공부 ] 선택 문제 알고리즘(Selection) (feat.python 파이썬)▶ 선택문제(Selection)란? ※ ..

1. Iterative AlgorithmC = AB, (이때, n * m 크기의 행렬 A,  m * p 크기의 행렬 B → n * p의 크기의 행렬 C) 시간복잡도위의 알고리즘은 Θ(npm)의 시간 복잡도를 가짐.즉, 일반적으로 Θ(n^3)의 시간 복잡도를 가짐. (for문 3개인 거 확인 가능)2. Divide and conquer Algorithm (Brute force)2^n의 크기를 가지는 동일한 행렬 A, B에 대해 수식은 다음과 같음.다음에 따라 8번의 곱셈과 4번의 덧셈이 필요하다는 것을 알 수 있음.즉, 8개의 n/2 크기의 부분 행렬의 곱과 그들의 합 Θ(n^2) 으로 이뤄질 수 있음.시간복잡도위 수식으로 풀면,  Θ(n^3)의 시간 복잡도를 ..

예상문제 - Ram model 개념 알고리즘 분석의 가장 중요한 도구는 1) RAM 계산 모델 2) 최악의 경우(worst-case)의 점근적 분석(asymptotic analysis)Ram model알고리즘은 컴퓨터 과학의 중요하고 지속적인 부분임왜냐하면 기계-독립적인 알고리즘 방식으로 연구할 수 있기 때문이것은 모든 분석에 RAM 모델의 계산을 사용하기 때문 * RAM: Random Access Machine알고리즘 실행 시간: RAM 모델에서의 단계 수를 세어 측정함각 단계의 정확한 시간은 다르지만, RAM은 그 모든 것을 동등하다고 가정각 "간단한" 작업(+, *, -, =, if, call)은 한 번의 1단계 소요루프 서브루틴은 간단한 작업이 아님이들은 데이터의 크기와 서브..

Induction Proof 자연수 n에 관한 식Base → 가정 → 증명 교재 예시 1  교재 예시 2 교재 예시 3 # 2.

Selection Problemuneven split의 대표적 예시문제: 정렬되지 않은 데이터 집합에서 k번째 요소를 찾아라Divide를 활용하여 Selection 문제를 해결할 수 있음.Sorting을 활용하여 Selection 문제를 해결할 수 있음.아래의 사진을 이해하기 위해 pivot을 활용하는 quick sort 를 먼저 알아보고 작성할게요 ** 어떻게? 시간 복잡도 의미하는 바? 각 componant의 이해