점화식 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현 1. 반복 대치 더 작은 문제에 대한 함수로 반복해서 대치해가는 방법 점근적 복잡도 계산 용의 $$ n = c^k $$ $$ n , \le , c^k , < , cn , 인, c^k이 , 하나 존재한다. $$ $$ 만약,임의의,상수,r에,대해,T(n),=,O(n^r)이라면, $$ $$ T(cn) ,=,O((cn)^r),=,O(c^rn^r),=,O(n^r)이므로,T(cn),=,T(n)이,된다. $$ 입력의 크기가 두배가 되어도 다항식 범위 내에 있는 점근적 복잡도는 변하지 않는다. $$ T(n), \le , T(2^k), \le , T(2n) $$ 2. 추정 후 증명 결론을 추정하고 수학적 귀납법으로 이용하여 증명하는 방법 수학적 귀납..
알고리즘 점근적 표기 https://ko.wikipedia.org/wiki/%EC%9C%84%ED%82%A4%EB%B0%B1%EA%B3%BC:TeX_%EB%AC%B8%EB%B2%95 https://blog.naver.com/aureagenus/120113285536 https://jjycjnmath.tistory.com/117 O - 표기법 O(f(n))은 최고차항의 차수*가 f(n)과 *일치하거나 더 작은 함수의 집합 상한의 개념 포함 $$ f(n) \in , O(g(n))을 , f(n) = O(g(n)) $$ $$ f(n) = O(g(n)) => f는 , g보다 , 빠르게 , 증가하지 , 않는다. $$ $$ ex);5n^2 , + , 4n , = O(n^2) , or , 7n , = O(n^2) $$..
### 이진 탐색 ### : 데이터가 '정렬'된 상태에서 데이터를 반으로 나눠가며 특정 값을 찾는 방법 : 정렬된 데이터 O(logn) : 시작점(start), 끝점(end), 중간점(mid)를 가지고 범위를 좁혀가며 값을 찾는다. data = [1,2,3,4,5,6,7,8,9,10] target = 2 start = 1 end = 10 # 반복 사용 def binarySearch(start, end, target): while (start >= end): mid = (start+end) // 2 if (data[mid] == target): return mid elif (data[mid] < target): start = mid + 1 else: end = ..
### 파라메트릭 서치 ### : 원하는 조건(범위) 내에서 최대,최소 값을 찾는 문제 => 결정 문제 (이분 탐색으로 해결) (ex, ~한 것중에서 최대,최소 인 값을 찾으시오) 1. 위의 개념에 만족 2. 최댓값 -> 최댓값보다 작은 값들이 조건을 모두 만족 최솟값 -> 최솟값보다 큰 값들이 조건을 모두 만족 3. 정확한 값을 구할 수 있어야 한다. (무한대 x) O(조건함수(n) * logn) 1. 최댓/최솟값을 구하는 것을 기준으로 start, end(이분 탐색 기준)를 잡는다. (start = mid + 1, end = mid - 1이 값을 크/작 게 만드는 지 파악하기) 2. 함수를 만들어 범위를 줄여 나가며 답을 구한다. # 최댓..
이번 연도에 DSC라는 모임을 알게 되어서 가입을 하게 되었고 Core member라는 타이틀을 가지고 활동을 하게 되었습니다. (과분하게...) 알고리즘 부분을 맡아서 활동을 하였는데 저 자신의 실력도 많이 부족한 상태였습니다. 그래서 실력을 같이 으쌰으쌰 하기 위해 만든 것이였습니다. 초기에는 많은 사람들이 관심을 보였지만 코로나로인해 비대면으로 인해 참여 의지가 많이 떨어졌습니다. 그래서 의지가 아직 남아있는 분들을 다시 모집하였습니다. 전과 비교하여 많은 수는 아니였지만 알고리즘 문제풀이, 알고리즘관련 정보등을 공유하고 알고리즘 실력을 높이기 위해 일주일 목표를 잡고 스스로 계획을 세워 지키는 방식으로 했습니다. 또한 소소한 일상도 이야기하여 친근감을 높이기도 했습니다. 자신이 정한 계획인 만큼 ..