해나의 컴공생존기

Array ( 배열 ) 정의 : 연속된 주소, 동일한 Type 장점 : n개 중 k번째 access(Read&Write)가 상수 시간에 가능, Search(어떤 x가 배열안에 있느냐?)가 빠름 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴수 있다. 사용 : 변화가 없거나 드문 자료 배열에서 가장 흔히 쓰이는 search 방법은 linear search 이다. 이는 하나하나 다 읽어보며 찾는 방법이고 모두 다 읽어봐야해서 크게 효율적이지 않다. 또 다른 방법은 Binary Search 이다. 이 방법은 sorting 되어있는 상태에서만 사용가능하다. 기본적인 로직은 절반을 확인하고 그의 절반..절반.. 을 확인하는 방법이다. 코드로 나타내면 int search(int a[], int ..

수학적 귀납법 ( 명제 : P(n)이 있을때 ) 기본형 : p(1)이 참이고, p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 강한 형태 : p(1)이 참이고, p(1)^p(2) ^ ....^p(n-1) -> p(n) 이 참이면 p(n)은 모든 자연수 n에 대하여 참이다. 수학적 귀납법은 크게 Base 와 Step 부분으로 나뉜다. base: p(1) 이 참이다. step : p(n-1) -> p(n) 가 참이라고 보이면, p (n) 은 모든 자연수 n에 대해 참이라고 증명이 가능하다. base 와 step은 서로 독립적이고, 보통 base는 참인것을 금방 알수 있으며, 포인트가 되는 것은 step 부분이 참인 것을 알아내는 것이다. 그런데 step 에서 p(n-1) -..