(2021.10.27) 알고리즘 수업들으면서 정리하기 14탄 greedy algorithms 개념 (생각보다 내용이 없다) Greedy algorithms : 탐욕 알고리즘 greedy algorithm은 dynamic algorithms과 마찬가지로 optimization에 쓰인다. greedy algorithm은 the activity selection problem에도 쓰인다. dynamic algorithms vs greedy algorithms - dynamic algorithms은 problem을 sub-problem으로 나누어서 sub-problem을 overlapping 하며 larger sub-problem으로 build up 해간다. - greedy algorithms은 problem을..

(2021.10.14) 알고리즘 수업들으면서 정리하기 13탄 7주차 보충강의내용- Knapsack problem (보충강의 있는지 모르고 실강 전에 안들었다..) Knapsack problem:dynamic programming 문제: item 여러개가 있는데, 그 item은 각각의 value와 weight를 가진다. knapsack은 W(kg)까지 수용할 수 있다. 이때, knapsack에 담을 수 있는 최대 value가 무엇인가?? 우선, 이 문제를 navie approach로 풀어본다면 각각의 item을 순서대로 넣을지 말지를 결정하기 때문에 2 x 2 x ... x 2=2^n 의 시간이 걸린다. --> O(n^2) Dynamic programming 의 4단계를 거쳐 문제를 풀어볼 수 있다. Ch..

(2021.10.14) 알고리즘 수업들으면서 정리하기 12탄 7주차 실강 내용- rod cutting problem (손글씨가 아닌 모든 첨부사진은 교수님 강의노트가 출처-알고리즘 교재) Rod cutting problem 설명하시기 전에 왜 dynamic programming인가?? 에 대한 수업을 하셨다 Why dynamic programming?? duplicate computation(반복적인 계산)이 많을 때, dynamic programming이 아주 효과적임! 예를 들어 생각하면 이해하기 쉽다. n개에서 k개를 고르는 이항정리 문제는 위와 같이 표현할 수 있다. 이것으로 코드를 만들어본 것이 아래다. C(n,k)=C(n-1,k-1)+C(n-1,k)에서 다시 C(n-1,k-1)과 C(n-1,k..

(2021.10.10) 알고리즘 수업들으면서 정리하기 11탄 6주차 내용- LCS optimal substructure 을 찾는 것에 중점을 두자 recurrence를 쓸 수 있어야 함 LCS(The longest common subsequence) Definition[subsequence] Definition[common subsequence] 만약 Z가 X의 subsequece 이면서, Y의 subsequence이면, Z는 X와 Y의 common subsequence라고 한다. Z는 consecutive(연속적) 일 필요는 없으나 in order (순서대로) 여야한다. Definition[Prefix of a subsequence] X= 이라는 sequence에 대해 prefix of X (for i..

(2021.10.10) 알고리즘 수업들으면서 정리하기 10탄 6주차 내용- 새로운 개념 등장 Dynamic programming Dynamic programming 의 개념 Dynamic programming 의 4단계

(2021.10.10) 알고리즘 수업들으면서 정리하기 9탄 5주차 내용-3 마지막!!! Binary search 주어진 배열에서 찾고자하는 값이 있는 인덱스를 찾는 problem 이다. Divide-and-conquer approach Divide A[1..n] into two parts A[1..mid-1] and A[mid+1..n] Conquer: if A[mid]=x, return mid if A[mid]x, return A[1..mid-1] for next iteration Combine: just return the result (key: can reduce the array to it's half for the next iteration) BINARY_SEARCH(A,low,high,key)..

(2021.10.09) 알고리즘 수업들으면서 정리하기 8탄 5주차 내용-2 Quick sort input: sequence of numbers output: permutation (오름차순) Divide-and-conquer approach Divide: Partiton the array into two subarrays(A[p..q-1] and A[q+1..r]) (A[p..q-1] ≤ A[q] < A[q+1..r]) Conquer: Sort the two A[p..q-1] and A[q+1..r] by recursive calls to quick sort Combine: no work is needed to combine them(subarrays are already sorted) a pivot x..

(2021.10.09) 알고리즘 수업들으면서 정리하기 7탄 5주차 내용인데 이해하는데 오래걸림.. Maximum-subarray problem

(2021.10.08) 알고리즘 수업들으면서 정리하기 6탄 5주차 내용 -1 (4주차는 추석이어서 수업 없었음) Maximum-subarray problem input: sequence of numbers A[1 ... n] output: subarray의 greatest sum(contiguous subarray of A) A[i ... j] Naive approach 교수님께서 어떠한 문제를 풀 때는 naive하게 풀어보는 것부터 시작해보라고 하셨다 (naive 뜻을 몰라서 처음엔 무슨 말인지 이해하지 못했음) Divide-and-conquer approach Subproblem: Find a maximum subarray of A[low..high] (original call low=1, high=..

(2021.10.07) 알고리즘 수업들으면서 정리하기 5탄 3주차 내용 끝!! Divide-and-Conquer algorithms Divide-and-conquer를 이용하여 merge sort의 T(n) 계산 proof by telescoping 은 수업시간에 했음 ↓↓↓↓↓↓↓↓ proof by induction on n 은 과제로 했음 ↓↓↓↓↓↓↓↓ (답이 맞는지는 아직 모름..) Master Method for solving recurrences 과제로 했던 master method 문제들 ↓↓↓↓↓↓↓↓

(2021.10.07) 알고리즘 수업들으면서 정리하기 4탄 3주차 내용 Merge Sort insertion sort가 incremental approach로 정렬하는 반면, (정렬된 배열의 원소개수가 늘어남) merge sort는 divide-and conquer approach로 정렬한다. --> divide-and-conquer approackh는 recursion의 개념을 기반으로 한다. Divide-and-conquer Divide the problem into several su-bproblems Conquer the sub-problems by solving them recursively. Combine the solutions to the sub-problems to get the solu..

(2021.10.06) 알고리즘 수업들으면서 정리하기 3탄 3주차 내용 Asymptotic Notation (점근적 표기) 알고리즘의 런타임을 표기하기 위해서 highest-order term으로 정의하는 것을 점근적 표기라고 한다. 점근적 표기에는 세가지가 있다. Big O: 상한선 제시 - upper bound Big Omega: 하한선 제시 - lower bound Big Theta: 상한선과 하한선 둘다 제시 (Big O는 Big theta로 표기가능하지만, Big theta는 Big O로 표기할 수 없음 - 교수님 왕강조) Big O --> 상한선 제시 : upper bound Big Omega --> 하한선 제시 : lower bound --> BEST case performance를 얘기할 ..

(2021.10.06) 알고리즘 수업들으면서 정리하기 2탄 2주차+3주차 내용 Insertion sort - loop invariants statement: j-1 번째까지는 정렬되어 있음이 계속 보장된다. Initialization(초기조건): first iteration 전에도 참이어야 하는데, j=2부터 시작되는 것을 통해 first iteration 전에는 j=1임을 생각할 수 있다. j=1 일 때, A[1]은 원소가 하나이기 때문에 정렬 상태이므로 참이다. Maintenance(유지조건): 한 iteration이전에 참이었다면, 다음 iteration 이전에도 참을 유지해야 하는데, inner loop에 들어가기 전에는 out of order이고, loop를 나오는 순간에 key값이 order가..

(2021.10.06) 알고리즘 수업들으면서 정리하기 1탄 2주차 내용 insertion sort (삽입정렬) - 작동원리 input: sequence of numbers output: permutation (오름차순) pseudocode Insertion_sort(A,n) for j