[알고리즘] 순차 탐색, 이진 탐색, 피보나치 수열

Problem Description(문제 설명)

- Problem(문제)

- Parameters : 문제 해결을 위한 변수 (S, n, x ...)

- Instance : Parameters의 구체적인 변수 ? (ex. S = [10, 2, 4 , 46, 75])

- Algorithm : 문제 해결 방법

---

Pseudo code vs C++

- 문법을 지킬 필요가 없다. // 완벽한 코드로 작성하지 않고 알고리즘만 표현하면 됨

- 수학적 문법도 자유롭게 적을 수 있다 // low <= x <= high

- keytype을 자유롭게 사용할 수 있다

---

Sequential Search(순차 탐색)

- 순서대로 나아가며 탐색

- Problem : 크기가 n인 array S에서 key x는 어디에 있는가?

- Input(parameter) : 양수 n, 1부터 n까지의 값을 갖고 있는 배열 S

- Output : S에서의 x의 위치

//Sequential Search(Pseudo-code)

void seqsearch(int n,
		const keytype S[]
                keytype x, //여기까지가 input
                index& location) //location이 아웃풋	
	location = 1;
    while (location <= n && S[location] != x)
    	location++;
	    //S[location]의 값이 찾는 x가 아니면 x가 나올 때까지 location을 n번 반복
    if (location > n)
    	location = 0;
        //n개의 S[]값을 확인했음에도 x를 찾지 못한 경우
}

Review : sequential search

- worst case라면 n번 탐색, best case라면 1번 탐색

=> but 더 좋은 탐색 방법이 없음!

---

Binary Search(이진 검색)

- 검색 범위를 줄여가며 탐색

- Problem : 크기가 n인 sorted array S에서 key x는 어디에 있는가?

- Input(parameter) : 양수 n, 1부터 n까지의 값을 갖고 있는

정렬된 내림차순이 아닌 배열 S(sorted array)

      + non-decreasing order(비내림차순) : 내림차순이 아니다 != 오름차순

      ex. 1, 5, 6, 5, 10을 정렬하면 5가 있기 때문에 내림차순이 아님

- Output : S에서의 x의 위치(x값이 없으면 0)

//Binary Search(Pseudo-code)

void binsearch(int n,
 		const keytype S[],
                keytupe x,
                index& location) {
    index low, high, mid;
    low = 1; high = n;
    location = 0;
    
    while(low <= high && location == 0) {
    	mid = (low + high) / 2 //중간값
        if(x == S[mid]) location = mid; //찾는 값이 S[mid]인 경우
        else if(x < S[mid]) high = mid - 1; //찾는 값이 S[mid]보다 작은 경우
        else low = mid + 1; //찾는 값이 S[mid]보다 큰 경우
        } //mid값을 기준으로 범위 재정렬

Review : binary search 

- S는 이미 정렬되어 있기 때문에 while문은 반복할 수록 절반의 횟수가 필요함.

- worst case라면 ln(n)+1, best case라면 한 번에 걸리는 경우..?

   in worst case : (e.g.) n = 32. S[16], S[16+8], S[24+4], S[28+2], S[30+1]. S[32]

=> 과연 이 방법이 최선의 방법인가?

좋은 방법인 것 같군!

---

The Fibonacci Sequence(피보나치 수열)

n번째 피보나치 수열 값을 구하기

- Problem : 피보나치 수열

- Input : 양수 n

- Output : n번째 피보나치 수열의 값

Recursive version

//n번째 피보나치 값을 찾기 위한 첫번째 방법(재귀 버전)

int fib (int n) {
	if(n <= 1)
    	return n;
    else
    	return fib(n-1) + fib(n-2);
}

Review - recursive solution

the number of terms in the recursion tree for n

- n번째 값을 얻기 위해 2^(n/2) 번의 계산이 필요함

- worst case와 best case가 동일

- 굉장히 느린 알고리즘(비효율적?)

Iterative version

//n번째 피보나치 값을 찾기 위한 두번째 방법(반복 버전)


int fib2 (int n) {
	index i;
    int f[0..n];
    f[0] = 0;
    if(n > 0) {
    	f[1] = 1;
        for (i = 2; i <= n; n++) //n까지의 피보나치 수열을 계산
        	f[i] = f[i - 1] + f[i - 2];
        }
    return f[n];
}

Review - Interative solution

- 시간복잡도(Time complexity) : T(n) = n + 1

- 재귀 버전보다 반복 버전이 더 빠르다.