문제의 표기 방법
문제: 답을 찾고자 던지는 질문
파라미터: 문제에서 특정값이 없는 변수. x,y,,
문제의 사례 (입력): 파라미터에 특정 값을 지정한 것
사례에 대한 해답 (출력): 주어진 사례의 답
c++과 의사코드의 차이점
exchange x and y : x와 y의 값을 바꾸고 싶다
값을 swap 바꿔도 xy가 안바뀌어서
pointer를 씀. 함수에서는 포인터를 바꿔야 제대로 swap가 일어난다
-> 근데 매번 포인터, & 써야해서 reference 참조로 표기
reference에서는 엔퍼센드(&) 사용
순차검색 알고리즘
의사코드(설명&언어 c++)는 c++와 다르게 1부터 시작 (c++은 무조건 0부터 시작. 위 참고)
n=3에 위치하면 while 만족안해서 끝나겠지
array가 n개니까 최악의 경우 마지막 n개까지 다 찾아봐야할 수도.
이분검색 알고리즘
배열 32개까지 정렬되어 있다고 가정해 설명, 가운데부터 찾아본다.
high = n. 배열의 최대 크기
처음에 16을 찾는다.
x가 16보다 크다. ->17~32 이분검색. 24 ->28->31->32,,,
6=lg32+1 => lg= log2
어떤 알고리즘으로 피보나치를 빠르게 구할 수 있을까?
1.재귀적 방법
n=5 일때, f(2)를 세번이나 중복계산
함수 호출 횟수 계산
0.1 제외하고
n이 커질수록 계산하는 항의 개수가 커진다. => t(n-1) >t(n-2)
따라서
t(n-1)+t(n-2) +1 > t(n-2) +t(n-2) +1 > 2* t(n-2)
t(n-2) = t(n-3)+t(n-4) > t(n-4)+ t(n-4) = 2*t(n-4) 를 위에 대입하면.. > 2^2 * t(n-2)
이를 반복하면
호출횟수가 t(n) > 2^n/2 임을 알 수 있다.
이를 귀납법으로 증명가능
