1. 이진 탐색 알고리즘의 구현 1 - First와 Last가 만났다는 것은 탐색 대상이 하나 남았다는 것을 뜻함! - 따라서 First와 Last가 역전될 때까지 탐색의 과정을 계속해서 진행한다. ※ 이진 탐색의 기본 골격 2. 이진 탐색 알고리즘의 구현 2 * last와 first에 왜 +1, -1을 해주는 것일까? => -1 혹은 +1을 추가하지 않으면 first

※ 이진 탐색 알고리즘의 소개 1 ☞ 이진 탐색 알고리즘의 첫번째 시도 1. 배열 인덱스의 시작과 끝은 각각 0 과 8이다 2. 0과 8을 합하여 그 결과를 2로 나눈다. 3. 2로 나눠서 얻은 결과 4를 인덱스 값으로 하여 arr[4]에 저장된 값이 3인지 확인! arr[] = { 1,2,3,7,9,12,21,23,27 } * 순차 탐색보다 훨씬 좋은 성능을 보이지만, 배열이 정렬되어 있어야 한다는 제약이 따른다. 1 2 3 7 9 (중앙 인덱스) 12 21 23 27 arr0 arr1 arr2 arr3 arr4 arr5 arr6 arr7 arr8 ☞ 이진 탐색 알고리즘의 두번째 시도 1. arr[4]에 저장된 값 9와 탐색 대사인 3의 대소를 비교한다. 2 대소의 비교결과는 arr[4] > 3 이므로..

※ 순차 탐색 평균적 경우 시간 복잡도 가정 1. 탐색 대상이 배열에 존재하지 않을 확률 50% 가정 2. 배열 첫 요소부터 마지막 요소까지 탐색 대상 존재 확률 동일! - 탐색 대상이 존재하지 않는 경우의 연산 횟수는 n - 가정 2에 의해서 탐색 대상이 존재하는 경우의 연산횟수는 n/2 정리. n * 1/2 + n/2 * 1/2 = 3/4n n = 데이터의 갯수 1/2 = 존재하지 않을 확률 50% n/2 = 최악과 최상의 중간 따라서, T(n) = n * 1/2 * n/2 * 1/2

※ 알고리즘의 성능 분석 방법 순차 탐색 알고리즘 적용된 함수 1. 중심이 되는 연산자 ( == ) 2. 주변 연산자 ( T(n) = n -> 최악의 경우를 대상으로 정의한 함수 T(n)

※ 시간 복잡도 & 공간 복잡도 1 - 시간 복잡도(Time Complexity) => 얼마나 빠른가? ( CPU에 얼마나 부담을 주는가?) - 공간 복잡도(Space Complexity) => 얼마나 메모리를 적게 쓰는가? (MEMORY) - 시간 복잡도를 더 중요시 한다. * CPU가 하는일 = 연산 ※ 시간 복잡도의 평가 방법 - 중심이 되는 특정 연산의 횟수를 세어서 평가를 한다. - 데이터의 수에 대한 연산횟수의 함수 T(n)을 구한다. ※ 알고리즘의 수행 속도 비교 기준 - 데이터의 수가 적은 경우에는 수행속도는 큰 의미가 없다. - 데이터의 수에 따른 수행 속도의 변화 정도를 기준으로 한다.

* 이론을 바탕으로 한 구현이 중요하다. - 자료구조(Data Structure)에 있어서 재귀함수는 굉장히 중요하다. - 프로그램이란 데이터를 표현하고 ( 자료구조 ) = 표현에는 저장의 의미가 표현된다. 그렇게 표현된 데이터를 처리 하는 것이다. (알고리즘) 1. 선형구조 - 리스트 - 스택 - 큐 2. 비선형 구조 - 트리 - 그래프 3. 파일구조 - 순차파일 - 색인파일 - 직접파일 4. 단순구조 - 정수 - 실수 - 문자 - 문자열 ex) int main(void) { //배열의 선언 int arr[10] = {1,2,3,4,5,6,7,8,9,10}; >>자료 구조 //배열에 저장된 값의 합 for(idx = 0; idx >알고리즘 } * ..