알고리즘

1단원

• 프로그램 설계 과정
  문제 = >알고리즘 =>만족? => 프로그램
• Analysis(분석)
  -알고리즘을 분석하여 시간(시행되는 횟수)/공간(메모리 차지) 복잡도를 구하는 방법을 학습.

알고리즘

알고리즘이란, 어떤 입력에 모든 사례에 대해서 해답을 찾을 수 있도록 컴퓨터 프로그램을 만들어 내기 위해서 각 사레에 대해 해답을 찾아주는 일반적인 단계별 절차를 명시

• 순차 검색 : 처음부터 순서대로 진행
• 이분 검색 : 있을 만한 곳으로 넘겨본 후 앞뒤로 뒤적여가며 찾는다.
• 알고리즘은 보통 의사코드(Pseudo-code, 슈도코드)로 표현한다.
  (슈도코드는 직접 실행할 수 있는 프로그래밍 언어는 아니지만, 거의 실제 프로그램에 가깝게 계산과정을 표현할 수 있는 언어)

의사코드와 c++의 차이점 1

-의사코드는 배열 인덱스 범위의 제한x (아무 숫자나 시작가능하나 보통 1로 시작)
-c++은 인덱스 0부터 시작

의사코드와 c++의 차이점 2

-c++ 명령문 대신 수학적 표현식 허용

• low <= x && x <= high -> low <= x <= high
• temp =x;
  x = y;
  y = temp -> exchange x and y

의사코드와 c++의 차이점 3

• 표준이아닌 제어 구조를 사용
  -repeat (n times) {...} ----> {...} 이 안에 것을 n번 반복하라는 말
• 프로시저와 함수
  -프로시저 (리턴 x): void pname(...) {...}
  -함수: returntype fname (...) {...return x; }
  => 값을 넘겨주기에 적당한 경우
  => 주소전달 파라미터를 사용하여 결과값을 전달 (배열이 아닌 모든 파라미터는 선언할 때 데이터타입 이름 끝에 &를 붙인다)

파라미터

문제에서 특정값이 주어지지 않은 변수

알고리즘 1.1 순차검색 (의사코드)

void seqsearch(int n,
		const keytype S[],  //여기서 keytype는 아무 타입이나 상관 없다는 의미
        index& location) { // &를 붙여서 출력함
     location = 1;
     while (location <= n && S[location] != x) //이부분이 true라면 loc 1증가
     	location++;
      if(location > n)
      	location = 0;
        //while 문을 돌리고 if 돌리고 조건x 출력으로 리턴함.

1.2 알고리즘 이분검색

void binsearch(int n, //입력 (1)
				const keytype S[], // 입력 (2)
              	keytype x, 	// 입력(3)
                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;
           else if (x < S[mid])
           		high = mid - 1;
           else
           		low = mid + 1 ;
              }
           }

이분검색을 c++로,

int binsearch ( int n, int*s, int x);
void main(){
		int size = 6,loc;
        int array[6] = {2,5,6,7,10,11,12};
        int key;
        
        printf("검색할 데이터 입력 =>");
        scanf("%d", &key);
        loc = binsearch (size, array, key);
        printf("검색한 위치는 =%d 입니다 \n", loc);
        }
        int binsearch(int n, int*s, int x){ // *s 는 배열의 주소를 몰라서 포인터로 받음.
        int low, high, mid, location = -1;
        low=0;
        high=n-1;
        
        while( low <= high && location == -1)
        {
        mid = (low+high)/2;
        
        if(x== s[mid]) //포인터를 배열로 표현
        	location =mid
        else if (x< s[mid])
        	high =mid-1;
        else
        	mid +1;
         } return location; }

• 이분검색 알고리즘으로 키를 찾기 위해서 s에 있는 항목을 몇 개나 검색해야 하는가??
  -while 문을 수행할 때마다 검색 대상의 총 크기가 반 씩 감소하기 때문에 최악의 경우라도 log N + 1 개만 검사하면 된다.
  ex) 데이터 32개 일때, 5 log 2의 2승 +1
• 피보나치 수열의 정의 : 초항은 거의 (0과1이며), 현재항은 이전 두항의 합과 동일하다.

-피보나치 알고리즘

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

참고 : 피보나치인 재귀 알고리즘은 수행속도가 매우 느리다는 단점이 있다.
-fib(n)의 함수 호출 횟수 계산
T(n) = fib(n)

T(0) = 1 // T ==횟수
T(1) = 1 // for n>-2 왜냐하면 T(n-1)>T(n-2)
T(n) = T( n-1) + T(n-2) + 1
'>' 2 x T (n-2) // 큰 차수로 해줘서 성능 올려 식 간단히 함, 큰 차수만으로 계산해서 흐름확인.
'>' 2x2 x T (n-4)
'>' 2x2x2 x T (n-6)
...
'>' 2^(n/2) x T(0)
=2^(n/2)